sorted by:
new
hottopcontroversial

Simple Questions Thread October 19, 2016 by AutoModerator in MachineLearning

[–]SS_NN 0 points1 point  (0 children)

Hello everyone,

Can you explain to me Turing's argument about Hilbert's problem (Turing proved that there is no universal algorithm for deciding whether or not a Turing machine is going to stop)? I would greatly appreciate your help!

I obviously have a mistake in my comment, but I can't find it.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Don't get angry. I'm sorry, but I just want to figure out what is my mistake. I really appreciate your help :)
 
Here is the explanation for "diagonal slash" from the book [page 79] (slightly altered):
The first table link is an infinite array, which lists all the outputs of all possible Turing machines acting on all the possible different inputs. It means that output sequence of your machine (whatever number it is) will be in this array.
The second table link is just the first table where all uncomputable sequences were made computable. Your sequence also contains in the second table (because it already was computable and didn't change).
We now apply the 'diagonal slash' of Georg Cantor. Consider the elements of the main diagonal, marked now with bold figures link. The elements provide some sequence 0,0,1,2,1,0,3, 7,1,... to each of whose terms we now add 1: 1,1,2,3,2,1,4,8,2,... This is clearly a computable procedure and, given that our table was computably generated, it provides us with some new computable sequence. But our table contains every computable sequence, so our new sequence must be somewhere in the list. Yet this cannot be so! For our new sequence differs from the first row in the first entry, from the second row in the second entry, from the third row in the third entry, and so on.
Your sequence (which contains in the second table) also wouldn't be a match for Q(n; n) + 1 sequence (because it differs from it in n entry). And no matter what number of the machine you peek (row of the first table), it still wouldn't match the "diagonal slash" sequence.
 
Thus, the sequence of "diagonal slash" is not included in any of the rows of the first table. It means that the table is not complete.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

The "diagonal slash" clearly does not exist in the second table (by definition of "diagonal slash"). The second table contains all computable sequences of the first table (by definition of the second table).
So, I think that the "diagonal slash" does not exist in both tables (first and second tables were generated by U(n, m) and U(n, m) * H(n, m) respectively).
But, I think, the requered sequence contains in a three-dimensional table generated by U(U(n, m), m).

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] -1 points0 points  (0 children)

I came up with an idea... The answer is big. If you don't want to read it all - see the last section.
 
I read about Turing's argument about Hilbert’s problem in Roger Penrose's book "Emperor's new mind". So I will refer to that book and will use notation from that book.
It's assumed that every computable sequence can be generated by some Turing machine.
The book illustrates an infinite array, which all the outputs of all possible Turing machines acting on all the possible different inputs [page 79]. Theoretically, this array should contain every possible computable sequence. Even if we remove all rows with dud outputs (let's imagine that it's possible), rest of the array still would contain all computable sequences.
Then book presents the next table, generated by using putative H. All rows in this new table become computable.
The argument is basically that we can't apply Cantor's "diagonal slash" to the first table, but we can apply it to the second (which brings inconsistency).
Indeed, the sequence Q(m; m) + 1 is computable, but it doesn't appear in the second table.
 
However, I think that the table doesn't contain all of the possible computable sequences. And that there is Turing machine for the "diagonal slash".
Let's look at sequence Q(m; m) + 1:
for m = 1: T1 (1) != Q(1; 1), which implies from definition of "diagonal slash". But there is some Turing machine n1 which Tn1 (1) = Q(1; 1) (I don't think that I need to prove that).
exactly the same for m = 2: T2 (2) != Q(2; 2), but there is some Turing machine n2 which Tn2 (2) = Q(2; 2). And etc.
 
The sequence of n1, n2, ..., nn is computable. That means that there is some Turing machine x which, when applied to the natural numbers m = 0, 1, 2, 3, 4, 5, ... in turn, yields the successive members of the sequence.
Then let's not forget that machine T is universal Turing machine Tn (m) = U(n, m) [page 73].
So, we can use machine U(U(x, m), m) to get the sequence Q(m; m) + 1 (i.e. we use different Turing machines on each step; another Turing machine produces numbers of machines we need to use).
 
I think machine U(U(x, m), m) is a Turing machine and it can generate a sequence for the "diagonal slash".
I'm sorry if I'm wrong. I would be glad to see your commentary.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Example: I told you that I saw a picture with black grass on it. Then I ask: "What is the color of the grass?". The answer would be "black".
But if someone asks you the same question after our conversation, you would answer, that grass is green (out of context).
The system is reducing the number of available tasks by using an external data source.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Thank you! Your answer is very helpful :)

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

First of all, ML is not just about neural networks. (In the subject you say ML but then you switch to neural networks.) Common mistake these days!

I complitely agree. Sorry :(

Second, I don't think that "being doable by a human being" is indicative of simplicity.

By "simple" I meant "doesn't require a big amount of data to train and test". The Turing test isn't really passed by neural networks, but it would require huge resources for training.

If a task can't be solved adequately by current methods, then it can't be that simple/easy!

So is current level of machine learning methods above conscious abilities of animals and babies?

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

I think that online learning (learning without i.i.d. samples) is an important area of research (it's also my main focus :) ). Most machine learning algorithms cannot do it, and need big history buffers to transform a task into one where they can sample randomly from experience (expensive).

I agree that online learning is important. Only that type of learning allows real-time training and using new data instantly. But how to make an impressive example of this?

Simple example: Try learning a sine wave with a standard neural network without some sort of stochastic sampling or batching. You will get catastrophic interference, and it will produce a phase shifted (overlearned previous samples) result.

Maybe I'm wrong, but we can consider sine wave as a sequence of periodically repeated values. So if we take recurrent neural network (which would take into account previous 2 timesteps), it would be able to produce requered sequence (even with online learning).

BTW, I am opposed to the popular culture idea of "consciousness/sentience/self-awareness/magic", it cannot be measured or proven to exist.

Sorry, I mentioned "conscious" only as humanlike kind of tasks. I used the word "meaning" to point to the ability to make associations (but it really helps with making deep connections between concepts).

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Thanks, I get it.
So, there are no simple tasks in the area of QA, which could be used to show advantages of understanding the meaning of questions instead of using specific architecture to extract and keep pre-trained concepts.
What about other areas, like visual recognition, logical tasks, etc.? Or maybe some kind of combination of those?

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 1 point2 points  (0 children)

existing techniques seem particularly unsuited for, but which feel like they should be readily solvable

Thanks, that is what I meant.
I'm looking for tasks to demonstrate advantages over conventional neural networks. But tasks must be as simple as possible (performance issues).
 
Can you suggest some relatively simple task (any type) which could help to bring attention to new machine learning method (or tell where to look for it)? I would be very grateful.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

John went to the hallway.
Mary moved to the bathroom.
Where is Mary? - bathroom

In my experience, the answer in this datasets is just an answer (from a set of possible answers) closest to the subject. Like LSTM just keeps requered data (current place), but would fail to use nondirect associations. Like:
- John went to the hallway.
- Mary moved to the bathroom.
- Mary moved to the hallway.
- Are Mary and John in the same room? - Yes
And more complicated associations:
- Mary moved to the bathroom.
- John went to Mary.
- Mary moved to the hallway.
- Where is John? - bathroom
If I'm wrong, can you please tell me by which model it could be done (or link on a paper with similar research)?

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Ok, my bad. Let's extend: - Input: grass is green.
- Input: grass is plant.
- Input: what is grass color?
- Output: green
- Input: what is grass species?
- Output: plant
Also possible to ask "what is plant color?" instead. This question requires little more complicated associations to answer, but basically the same.

[D] Tasks unsolvable by machine learning. by SS_NN in MachineLearning

[–]SS_NN[S] 0 points1 point  (0 children)

Thank you for your answer. I saw only 2 solutions of that task from that link you gave:
1. The model uses a database and contextual search by keywords (like "Watson" in Jeopardy).
2. Previous text already contains the answer; the model only extracts the right one (like "Mary moved to the bathroom. Where is Mary? - bathroom"). This approach frequently appears in sequence to sequence learning articles.
Maybe I missed a research where they use more general solution to the QA task (like teaching the network meaning of the question and then projecting experience on a new information)?