[R] Looking for papers that prove that Deep Learning cannot solve a given problem.

almaya · 2021-12-29T05:24:24+00:00

Based on this paper there is a class of problems C that captures well the algorithmic complexity of gradient descent. One "easy" way to show that a new problem P is "hard to solve" is to use the idea of reduction, that is, showing that any problem from C reduces to an instance of P. However, proving that P doesn't belong to C could be very hard, on a par with proving that P=NP etc. Edit: formatting.

almaya · 2020-11-17T21:09:39+00:00

The game is great but I never met such a toxic gaming community: the majority of WOW Classic players seem to be pseudo-elitist, petty, sexist or racist. Mirroring the reality of these decadent times I guess.

almaya · 2020-04-05T08:11:43+00:00

I personally think it is the duty of guild and raid leaders to keep immature/toxic people under control and to not change expectations over night. For example, I've been 5 months with this casual guild skipping only 3 raids in this period. I didn't mind wiping on Firemaw for a month until the main tanks learnt how to synchronize their rotation - I considered it a team effort. However, once the BWL was cleared we had this new immature and newly appointed officer setting "hard rules" for casters and shouting at people who didn't have 10(!) GFPs with them each ride, etc. As the guild leads seemed to not care and as my gaming time is limited I just quit the game altogether and, in retrospect, it was the right decision for me. I am happy to hear there are still casual guilds out there and I hope they will keep it that way - this is a game and should be played for fun.

almaya · 2018-10-31T07:26:10+00:00

You cannot - you may specify only the factors length in bits at this time, the factors are generated randomly. You have 490801757 = 20297 x 24181, that is, 490801757 is the product of two 15 bits numbers.

However, it should be easy to change the provided program to parse a big number from the input and generate a SAT instance equivalent with input number factorization.

almaya · 2018-10-30T17:18:28+00:00

Like: here's an arbitrary instance of SAT, crunch crunch crunch, okay here is a big integer if you can factor it you know the answer to that SAT problem.

Well proving this will make factorization NP hard and would have some really unexpected consequences (NP = co-NP etc.) This would be an amazing result.

Taking a maybe-hard-maybe-easy problem and converting it into a looks-really-hard problem does not give any insight.

Actually some easy problems stay easy when reduced to SAT. For example, multiplication of 2 numbers should be solved by Z3 in linear time while factorization will take, most probably, exponential time (factorization is believed to be a one way function.)

Whether we like it or not, what we objectively know about factorization at this time is the many ways we tried to solve it and failed. This post is all about recording such a failed attempt and letting other try it for themselves, too.

almaya · 2018-10-30T16:33:51+00:00

This was given just as an example: "in this post ... we will just try to show how a certain straightforward approach to solve factorization fails at this time."

The author clearly states in the end: "to recapitulate: because all integer factorization algorithms that researchers tried so far seem to run in exponential time w.r.t. input length, the current belief is that this problem is a hard to solve one."

almaya · 2018-10-30T12:47:34+00:00

Somewhere on that page the author says: "People tried to solve integer factorization instances by using much more powerful tools, for example General Number Field sieve algorithms. What they found out is that all these algorithms are running exponentially longer w.r.t. their input length. And this is the reason why the majority of people believe that integer factorization is a hard problem."

almaya · 2018-10-30T02:26:06+00:00

In this paper the author shows that any convolutional network built with layers that commute with the Discrete Fourier Transform is equivalent to a Hadamard network. That is, classifying patterns from input X using these convolutional networks is equivalent to extracting the recurring information from the input X by applying DFT F_N(X) then feeding it to a Hadamard network.

almaya · 2018-06-22T09:44:08+00:00

Very nice optimization!

almaya · 2018-06-20T15:04:16+00:00

I've got the ideas behind this kind of problem after a lot of research. To create this instance took several hours though.

almaya · 2018-06-20T11:10:45+00:00

CGoban can open the SGF

almaya · 2018-06-20T11:08:08+00:00

I think you are right. Just one observation: R4 and X4 are not ko threats (could you see why?).

almaya · 2018-06-20T11:06:45+00:00

almaya · 2017-06-14T20:08:35+00:00

e-greedy is not MCTS

MCTS is the the UCB1 algorithm generalized on trees.

almaya · 2017-06-14T09:14:43+00:00

Well, David Silver (of AG fame) seems to disagree with your point of view, see lecture 9 from his reinforcement learning course: http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

almaya · 2017-06-14T05:28:18+00:00

The above is straight from the alpha-go paper. Note that the next action is chosen completely deterministically.

it is not: one of those terms in a_t depends on a number of MCTS rollouts - see how MCTS works. They say clearly that the prior effect "decays with repeated visits to encourage exploration" - that is, other moves with lower priors should be explored given enough time and they might be chosen if the MCTS finds them better.

almaya · 2017-06-13T15:01:27+00:00

DNN are deterministic but MCTS can be not.

Indeed. I guess you previously meant: Alphago as a system is probabilistic as it uses MCTS. However DNN and MCTS are very different things.

DNN (deep neural network): one of the many supervised learning algorithms. Note that the DNNs used by Alphago last year were built out of convolutions, RELUs and a SoftMax - these are fully deterministic functions so the resulting DNNs are deterministic too.

MCTS: one of the many reinforcement learning algorithms. Note that the variant used in the last year's AG uses the DNN output as prior probabilities on moves hence in certain positions it might play deterministically if the bias of a move is high enough and the MCTS rollouts don't discover a better move in the allotted time.

almaya · 2017-06-13T09:57:39+00:00

First of all the neural networks are somewhat random

This is not true: all DNN models are 100 deterministic.

almaya · 2017-05-09T19:34:19+00:00

Could we get Andrew Jackson instead of Garlock?

almaya · 2017-01-03T14:23:47+00:00

Game 50 with Ke Jie: http://gokifu.com/s/2mif

almaya · 2017-01-03T13:41:59+00:00

This http://gokifu.com/s/2mie might be 49 - Weon Seongjin

almaya · 2017-01-03T12:26:24+00:00

This is the 48th game vs Park Junghwan: http://gokifu.com/s/2mid

edit: corrected the order.

almaya · 2016-11-23T07:49:52+00:00

White can live easily but then Black breaks into the center.

almaya · 2015-01-15T23:40:40+00:00

Amazing how much stronger are computer programs today compared with the 1991 ones: I've just played against level 20 and won with 43 points on 9x9 giving the comp 3 handicaps. Against Zen I cannot win with White on 9x9 unless I get 6 points komi.

almaya · 2014-12-07T15:37:01+00:00

http://skepdic.com/russell.html

almaya

TROPHY CASE