87

"If the map and the terrain disagree, trust the terrain." It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC dimensions appear not to be very helpful. The matter is hotly debated, see e.g.: H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well? C. ...


69

"Given the inability of Deep Learning to generalize, according to VC dimensional analysis [...]" No, that's not what VC dimensional analysis says. VC dimensional analysis gives some sufficient conditions under which generalization is guaranteed. But the converse ain't necessarily so. Even if you fail to meet those conditions, the ML method still might ...


45

The best explanation I've heard is this: When you're doing machine learning, you assume you're trying to learn from data that follows some probabilistic distribution. This means that in any data set, because of randomness, there will be some noise: data will randomly vary. When you overfit, you end up learning from your noise, and including it in your ...


40

ELI5 Version This is basically how I explained it to my 6 year old. Once there was a girl named Mel ("Get it? ML?" "Dad, you're lame."). And every day Mel played with a different friend, and every day she played it was a sunny, wonderful day. Mel played with Jordan on Monday, Lily on Tuesday, Mimi on Wednesday, Olive on Thursday .. and then on Friday Mel ...


32

Temperature is a hyperparameter of LSTMs (and neural networks generally) used to control the randomness of predictions by scaling the logits before applying softmax. For example, in TensorFlow’s Magenta implementation of LSTMs, temperature represents how much to divide the logits by before computing the softmax. When the temperature is 1, we compute the ...


28

Here are three survey papers that examine the use of machine learning in time series forecasting: "An Empirical Comparison of Machine Learning Models for Time Series Forecasting" by Ahmed, Atiya, El Gayar, and El-shishiny provides an empirical comparison of several machine learning algorithms, including: "...multilayer perceptron, Bayesian neural ...


25

Industry people have no regard for VC dimension, hooligans... On a more serious note, although the PAC model is an elegant way to think about learning (in my opinion at least), and is complex enough to give rise to interesting concepts and questions (such as VC dimension and its connection to sample complexity), it has very little to do with real life ...


21

No. This direction is unlikely to be useful, for two reasons: Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the ...


18

Neural Networks are not magic. If you treat them like they are and just throw data at them without thinking you're going to have a very bad time. You need to stop and ask youself "Is milliseconds since 1970 actually going to be predictive of the event I'm interested in?" The answer you should arrive at immediately is no. Why? For every instance you ...


16

I don't know the actual reason, but it feels intuitive: let's think about what the diploid nature of genes does in RL. In essence it allows the recessive gene to remain in the gene pool even if it's currently at disadvantage to exist, and occasionally resurface, giving two things - first, it doesn't go extinct and can re-multiply if it becomes advantageous; ...


14

Artificial neural networks is a class of algorithms that include a lot of different kinds of algorithms based on graphs, so I won't detail here beyond what you asked because there's too much to say, since there are so many kinds of ANNs. The first kind of artificial neural networks, the famous McCulloch-Pitts neurons, were linear, meaning that they could ...


14

Overfitting implies that your learner won't generalize well. For example, consider a standard supervised learning scenario in which you try to divide points into two classes. Suppose that you are given $N$ training points. You can fit a polynomial of degree $N$ that outputs 1 on training points of the first class and -1 on training points of the second class....


14

The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i. $$ That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them. Another approach, which is not so common, is to normalize the product manually. Instead of keeping just ...


14

Given the inability of Deep Learning to generalize, I don't know where you take that from. Empirically, generalization is seen as the score (e.g. accuracy) on unseen data. The answer why CNNs are used is simple: CNNs work much better than anything else. See ImageNet 2012 for example: CNNs: 15.315% (that was an early example. CNNs are much better now. At ...


14

Put simply, and without any mathematical symbols, prior means initial beliefs about an event in terms of probability distribution. You then set up an experiment and get some data, and then "update" your belief (and hence the probability distribution) according to the outcome of the experiment, (the posteriori probability distribution). Example: Assume we ...


11

Short answer: Strictly speaking, "Deep" and "Spiking" refer to two different aspects of a neural network: "Spiking" refers to the activation of individual neurons, while "Deep" refers to the overall network architecture. Thus in principle there is nothing contradictory about a spiking, deep neural network (in fact, the brain is arguably such a system). ...


11

Not all of AI works on correlation, Bayesian Belief Networks are built around the probability that A causes B. I'm working on a system to estimate the performance of students on questions based on their past performances. I don't think you need causation for this. A past performance does not cause a current performance. Answering on an early question ...


10

Though edron's thought experiment is nice, it assumes that you do not already have both of those features. If you did, then adding the third feature cannot help, because, as you say, it is linearly dependent. Assume features x1 = Year of birth, x2 = Year of death and x3 = Age = x2-x1. Then any linear predictor gives: x1*w1 + x2*w2 + x3*w3 = x1*(w1+w3) + x2*(...


10

artificial neural networks models were generally restricted to only a few layers, say 3, for decades, for various reasons, including a math proof named Kolmogorovs thm that indicated they could theoretically approximate arbitrary functions with low error (but only with many neurons). multilayer networks beyond that were not feasible/effective via prior ...


10

Using Backpropagation with momentum in a network with $n$ different weights $W_k$ the $i$-th correction for weight $W_k$ is given by $\Delta W_k(i) = -\alpha \frac{\partial E}{\partial W_k} + \mu \Delta W_k(i-1)$ where $\frac{\partial E}{\partial W_k} $ is the variation of the loss w.r.t. $W_k$. Introduction of the momentum rate allows the attenuation ...


10

During the training phase, backpropagation informs each neuron how much it should influence each neuron in the next layer. If the activation function isn't monotonic then increasing the neuron's weight might cause it to have less influence, the opposite of what was intended. The result would be choatic behavior during training, with the network unlikely to ...


10

It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would outperform other methods, you only asked if they could be applied to NP complete problems. The answer is yes, with some success and this has been known for decades and there ...


9

One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that ...


9

The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA). This kind of test is very effective{1} but falls under the HIP (Human Interactive Proofs) area: it's not transparent. Typical, "simple" approaches to distinguish human website traffic from Bot are: time it takes to ...


9

The superscript $T$ is the transpose operation. The vector $e$ is probably the constant one vector, though this is not standard notation and so it would be mentioned in the definitions part of the paper. Overall, $e^T\alpha = \langle e,\alpha \rangle = \sum_i \alpha_i$.


9

Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model ...


9

Roughly speaking, over-fitting typically occurs when the ratio is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, ...


9

What is a neural network? Neural networks are algorithms for function approximation. I like to call them a construction kit for functions. Their basic building block is a neuron, commonly visualized like this: You can see the $n$ inputs $x_1, \dots, x_n$ ($x_0$ is typically constant 1), each multiplied with a weight $w_i \in \mathbb{R}$. This gets summed ...


9

There is certainly a lot of research into this problem! It often goes by the name of elaboration. It is an undecidable problem in general, as you may have guessed. The "holes" are often called meta-variables or unification variables. As I explain a bit in this answer, the problem reduces to higher order unification, on which several people have written ...


9

The one word answer is "regularization". The naive VC dimension formula does not really apply here because regularization requires that the weights not be general. Only a tiny (infinitesimal?) proportion of weight combinations have acceptable loss after regularization. The true dimension is many orders of magnitude less as a result, so generalization can ...


Only top voted, non community-wiki answers of a minimum length are eligible