Learnability of machine learning is provably an undecidable?—part 1

Update on 23 January 2019, 17:55 IST:

In this series of posts, which was just a step further from the initial, brain-storming kind of a stage, I had come to the conclusion that based on certain epistemological (and metaphysical) considerations, Ben-David et al.’s conclusion (that learnability can be an undecidable) is logically untenable.

However, now, as explained here [^], I find that this particular conclusion which I drew, was erroneous. I now stand corrected, i.e., I now consider Ben-David et al.’s result to be plausible. Obviously, it merits a further, deeper, study.

However, even as acknowledging the above-mentioned mistake, let me also hasten to clarify that I still stick to my other positions, especially the central theme in this series of posts. The central theme here was that there are certain core features of the set theory which make implications such as Godel’s incompleteness theorems possible. These features (of the set theory) demonstrably carry a glaring epistemological flaw such that applying Godel’s theorem outside of its narrow technical scope in mathematics or computer science is not permissible. In particular, Godel’s incompleteness theorem does not apply to knowledge or its validation in the more general sense of these terms. This theme, I believe, continues to hold as is.

Update over.


This one news story has been lying around for about a week on my Desktop:

Lev Reyzin, “Unprovability comes to machine learning,” Nature, vol. 65, pp. 166–167, 10 January 2019 [^]. PDF here: [^]

(I’ve forgotten how I came to know about it though.) The story talks about the following recent research paper:

Ben-David et al., “Learnability can be undecidable,” Nature Machine Intelligence, vol. 1, pp. 44–48, January 2019 [^]. PDF here: [^]

I don’t have the requisite background in the theory of the research paper itself, and so didn’t even try to read through it. However, I did give Reyzin’s news article a try. It was not very successful; I have not yet been able to finish this story yet. However, here are a few notings which I made as I tried to progress through this news story. The quotations here all come from from Reyzin’s news story.

Before we begin, take a moment to notice that the publisher here is arguably the most reputed one in science, viz., the Nature publishing group. As to the undecidability of learnability, its apparent implications for practical machine learning, artificial intelligence, etc., are too obvious to be pointed out separately.


“During the twentieth century, discoveries in mathematical logic revolutionized our understanding of the very foundations of mathematics. In 1931, the logician Kurt Godel showed that, in any system of axioms that is expressive enough to model arithmetic, some true statements will be unprovable.”

Is it because Godel [^] assumed that any system of axioms (which is expressive enough to model arithmetic) would be based on the standard (i.e. mathematical) set theory? If so, his conclusion would not be all that paradoxical, because the standard set theory carries, from an epistemological angle, certain ill-conceived notions at its core. [BTW, throughout this (short) series of posts, I use Ayn Rand’s epistemological theory; see ITOE, 2e [^][^].]


To understand my position (that the set theory is not epistemologically sound), start with a simple concept like “table”.

According to Ayn Rand’s ITOE, the concept “table” subsumes all possible concrete instances of tables, i.e., all the tables that conceivably exist, might have ever existed, and might ever exist in future, i.e., a potentially infinite number of concrete instances of them. Ditto, for any other concept, e.g., “chair.” Concepts are mental abstractions that stand for an infinite concretes of a given kind.

Now, let’s try to run away from philosophy, and thereby come to rest in the arms of, say, a mathematical logician like Kurt Godel [^], or preferably, his predecessors, those who designed the mathematical set theory [^].

The one (utterly obvious) way to capture the fact that there exist tables, but only using the actual terms of the set theory, is to say that there is a set called “tables,” and that its elements consist of all possible tables (i.e., all the tables that might have existed, might conceivably exist, and would ever conceivably exist in future). Thus, the notion again refers to an infinity of concretes. Put into the terms of the set theory, the set of tables is an infinite set.

OK, that seems to work. How about chairs? Once again, you set up a set, now called “chairs,” and proceed to dump within its braces every possible or conceivable chair.

So far, so good. No trouble until now.


The trouble begins when you start applying operators to the sets, say by combining them via unions, or by taking their intersections, and so on—all that Venn’s diagram business [^]. But what is the trouble with the good old Venn diagrams, you ask? Well, the trouble is not so much to the Venn diagrams as it is to the basic set theory itself:

The set theory makes the notion of the set so broad that it allows you to combine any sets in any which way you like, and still be able to call the result a meaningful set—meaningful, as seen strictly from within the set theory.

Here is an example. You can not only combine (take union of) “tables” and “chairs” into a broader set called “furniture,” you are also equally well allowed, by the formalism of the set theory, to absorb into the same set all unemployed but competent programmers, Indian HR managers, and venture capitalists from the San Francisco Bay Area. The set theory does not by itself have anything in its theoretical structure, formalism or even mathematical application repertoire, using which it could possibly so much as raise a finger in such matters. This is a fact. If in doubt, refer to the actual set theory ([^] and links therein), take it strictly on its own terms, in particular, desist mixing into it any extra interpretations brought in by you.

Epistemology, on the other hand, does have theoretical considerations, including explicitly formulated rules at its core, which together allow us to distinguish between proper and improper formulations of concepts. For example, there is a rule that the concrete instances being subsumed under a concept must themselves be conceptually commensurate, i.e., they must possess the same defining characteristics, even if possibly to differing degrees. Epistemology prevents the venture capitalists from the San Francisco Bay Area from being called pieces of furniture because it clarifies that they are people, whereas pieces of furniture are inanimate objects, and for this crucial reason, the two are conceptually incommensurate—they cannot be integrated together into a common concept.

To come back to the set theory, it, however, easily allows for every abstractly conceivable “combination” for every possible operand set(s). Whether the operation has any cognitive merit to it or not, whether it results into any meaningful at all or not, is not at all a consideration—not by the design of the set theory itself (which, many people suppose, is more fundamental to every other theory).

So—and get this right—calling the collection of QC scientists as either politicians or scoundrels is not at all an abuse of the mathematical structure, content, and meaning of the set theory. The ability to take an intersection of the set of all mathematicians who publish papers and the set of all morons is not a bug, it is very much a basic and core feature of the set theory. There is absolutely nothing in the theory itself which says that the intersection operator cannot be applied here, or that the resulting set has to be an empty set. None.

Set theory very much neglects the considerations of the kind of a label there is to a set, and the kind of elements which can be added to it.

More on this, later. (This post has already gone past 1000 words.)


The songs section will come at the conclusion of this (short) series of posts, to be completed soon enough; stay tuned…

Wanna try this one? (Even if not on QM, it does involve complex numbers, randomness, …)

So, you know all there is to know about QM, I mean things like complex numbers, randomness, and all that, don’t you?

Or at least, you have read all there is to read about, say, QM, complex numbers, their amplitudes, probability, randomness, and all that, haven’t you?

If so, I have a question for you. Let me see how you approach it. …

… As far as this question is concerned, it doesn’t matter whether the answer is right or wrong. Not for this question, and not to me anyway. It’s the approach you take that would be really interesting—at least to me, and at least for this question…

So, ok? Ready? Here we go:

The question is:

What is meant by randomness? Can you give me an example of a random (or at least a pseudo-random) sequence of complex numbers? How would you convince me that it in fact is random (or at least pseudo-random), whatever you mean by that term?


I will wait for a while for answers to come in [less likely], or for people to post entries on their blogs, or for the media to post articles dealing with this aspect [more likely], but without mentioning anything about me, of course [certainly]! … As to me: I will run any answers you try here. … Further, as to others’ blogs/media articles: If I find them OK, or even just plain interesting, then I will even copy-paste those answers (or at least excerpts) here, and provide links to them.

Then, I will come back and give you my answer, after a while.

… One of the reasons it might take at least a week for me to come back (on this question) is: we once again are set to get busy at work. (Yes, we will be working on this week-end.)

The other reason is: I would really like to wait for a while, and let you try the question.

When I come back with my answer, I will also add the usual songs-section.

Bye for now, and take care…

 

“The spiritual heritage of India”

I wrote a few comments at Prof. Scott Aaronson’s blog, in response to his post of the title: “30 of my favorite books”, here [^].

Let me give you the links to my comments: [^], [^], [^] and [^].


Let me reproduce the last one of my four comments, with just so slight bit of editing. [You know I couldn’t have resisted the opportunity, right?]:

Since I mentioned the “upnishad”s above (i.e. here [ ^]), and as far as this topic is concerned, since the ‘net is so full of the reading material on this topic which isn’t so suitable for this audience, let me leave you with a right kind of a reco.

If it has to be just one short book, then the one which I would pick up is this:

Swami Prabhavananda (with assistance of Frederick Manchester), “The Spiritual Heritage of India,” Doubleday, New York, 1963.

A few notes:

1. The usual qualifications apply. For instance, I of course don’t agree with everything that has been said in the book. And, more. I may not even agree that a summary of something provided here is, in fact, a good summary thereof.

2. I read it very late in life, when I was already past my 50. Wish I had laid my hands on it, say, in my late 20s, early 30s, or so. I simply didn’t happen to know about it, or run into a copy, back then.

3. Just one more thing: a tip on how to read the above book:

First, read the Preface. Go through it real fast. (Reading it faster than you read the newspapers would be perfectly OK—by me).

Then, if you are an American who has at least a smattering of a knowledge about Buddhism, then jump directly on to the chapter on Jainism. (Don’t worry, they both advocate not eating meat!) And, vice-versa!!

If you are not an American, or,  if you have never come across any deeper treatment on any Indian tradition before, then: still jump on to the chapter on Jainism. (It really is a very good summary of this tradition, IMHO.)

Then, browse through some more material.

Then, take a moment and think: if you have appreciated what you’ve just read, think of continuing with the rest of the text.

Else, simple: just call it a book! (It’s very inexpensive.)

 


No need to add anything, but looking at the tone of the comments (referring to the string “Ayn Rand”) that got generated on this above-mentioned thread, I find myself thinking that, may be, given my visitor-ship pattern (there are more Americans hits today to my blog than either Indian or British), I should explain a bit of a word-play which I attempted in that comment (and evidently, very poorly—i.e. non-noticeably). It comes near the end of my above-quoted reply.

“Let’s call it a day” is a very neat British expression. In case you don’t know its meaning, please look it up on the ‘net. Here’s my take on it (without looking it up):

Softly folding away a day, with a shade of an anticipation that a day even better might be about to arrive tomorrow, and so, softly reminding yourself that you better leave the party or the function for now, so as to be able to get ready for yet another party, yet another function, some other day, later…

A sense of something like that, is implied by that expression.

I just attempted a word-play, and so, substituted “book” for the “day”.

Anyway, good night. Do read my last post, the document attached to it, and the links therefrom.

Bye for now.


Oh, yes! There is a song that’s been playing off-and-on at the back of my mind for some time. Let me share it with you.


A Song I Like:

(Hindi) “dil kaa diyaa jala ke gayaa…”
Lyrics: Majrooh Sultaanpuri
Singer: Lata Mangeshkar
Music: Chitragupt

[PS: The order of the listing of the credits, once again, is completely immaterial here.]


Anyway, enjoy the song, and the book mentioned in the quotes (and hopefully, also my past few posts and their attachments)… I should come back soon, with a maths-related puzzle/teaser/question. … Until then, take care and bye!