# Tag Info

## Hot answers tagged function-approximation

19

There are multiple papers on the topic because there have been multiple attempts to prove that neural networks are universal (i.e. they can approximate any continuous function) from slightly different perspectives and using slightly different assumptions (e.g. assuming that certain activation functions are used). Note that these proofs tell you that neural ...

13

Here's an intuitive description answer: Function approximation can be done with any parameterizable function. Consider the problem of a $Q(s,a)$ space where $s$ is the positive reals, $a$ is $0$ or $1$, and the true Q-function is $Q(s, 0) = s^2$, and $Q(s, 1)= 2s^2$, for all states. If your function approximator is $Q(s, a) = m*s + n*a + b$, there exists no ...

9

Any supervised learning (SL) problem can be cast as an equivalent reinforcement learning (RL) one. Suppose you have the training dataset $\mathcal{D} = \{ (x_i, y_i \}_{i=1}^N$, where $x_i$ is an observation and $y_i$ the corresponding label. Then let $x_i$ be a state and let $f(x_i) = \hat{y}_i$, where $f$ is your (current) model, be an action. So, the ...

8

A linear activation would not be able to separate the data like you have shown, no matter how many layers you throw into the network. If we had multiple linearly activated layers, each feeding into each other, the neurons in the previous layer would calculate some weighted sum of the input and send it to the next layer as input, where the next layer's ...

6

As far as I'm aware, it is still somewhat of an open problem to get a really clear, formal understanding of exactly why / when we get a lack of convergence -- or, worse, sometimes a danger of divergence. It is typically attributed to the "deadly triad" (see 11.3 of the second edition of Sutton and Barto's book), the combination of: Function approximation, ...

6

The problem you discuss extends past the machine but to the man behind the machine (or woman). ML can be broken down into 3 components, the model, the data, and the learning procedure. This by the way extends to us as well. The model is our brain, the data is our experience and sensory input, and the learning procedure is there but unknown (for now $<$...

6

Before anything, the function you have wrote for the network lacks the bias variables (I'm sure you used bias to get those beautiful images, otherwise your tanh network had to start from zero). Generally I would say it's impossible to have a good approximation of sinus with just 3 neurons, but if you want to consider one period of sinus, then you can do ...

5

Inherently, no. The MLP is just a data structure. It represents a function, but a standard MLP is just representing an input-output mapping, and there's no recursive structure to it. On the other hand, possibly your source is referring to the common algorithms that operate over MLPs, specifically forward propagation for prediction and back propagation for ...

5

One of the important qualifications of the Universal approximation theorem is that the neural network approximation may be computationally infeasible. "A feedforward network with a single layer is sufficient to represent any function, but the layer may be infeasibly large and may fail to learn and generalize correctly." - Ian Goodfellow, DLB I can't ...

5

Nonlinear relations between input and output can be achieved by using a nonlinear activation function on the value of each neuron, before it's passed on to the neurons in the next layer.

5

"Modern" Guarantees for Feed-Forward Neural Networks My answer will complement nbro's above, which gave a very nice overview of universal approximation theorems for different types of commonly used architectures, by focusing on recent developments specifically for feed-forward networks. I'll try an emphasis depth over breadth (sometimes called ...

5

Let us suppose we have a network without any functions in between. Each layer consists of a linear function. i.e layer_output = Weights.layer_input + bias Consider a 2 layer neural network, the outputs from layer one will be: x2 = W1*x1 + b1 Now we pass the same input to the second layer, which will be x3 = W2x*2 + b2 Also x2 = W1*x1 + b1 Substituting ...

4

First, you need to consider what are the "parameters" of this "optimization algorithm" that you want to "optimize". Let's take the most simple case, a SGD without momentum. The update rule for this optimizer is: $$w_{t+1} \leftarrow w_{t} - a \cdot \nabla_{w_{t}} J(w_t) = w_{t} - a \cdot g_t$$ where $w_t$ are the weights at iteration $t$, $J$ is the cost ...

3

Sure, you can define plenty of things we don't generally need to regard as recursive as so. An MLP is just a series of functions applied to its input. This can be loosely formulated as $$o_n = f(o_{n-1})$$ Where $o_n$ is the output of layer $n$. But this clearly doesn't reveal, much does it?

3

I'm going to assume here that you're using the standard, basic, simple variant of $Q$-learning that can be described as tabular $Q$-learning, where all of your state-action pairs for which you're learning $Q(s, a)$ values are represented in a tabular fashion. For example, if you have 4 actions, your $Q(s, a)$ values are likely represented by 4 matrices (...

3

To answer this, it's helpful to consider the notion of a neural network architecture – in this context, we can think of the architecture as being the network depth (i.e. number of layers), width (i.e. number of nodes in a layer), and some other structural aspects, such as recurrent layers, convolution layers, pool layers, etc. Theory In terms of the ...

3

Of course, it's possible to define a problem where there is no relationship between input $x$ and output $y$. In general, if the mutual information between $x$ and $y$ is zero (i.e. $x$ and $y$ are statistically independent) then the best prediction you can do is independent of $x$. The task of machine learning is to learn a distribution $q(y|x)$ that is as ...

3

You can indeed fit a polynomial to your labelled data, which is known as polynomial regression (which can e.g. be done with the function numpy.polyfit). One apparent limitation of polynomial regression is that, in practice, you need to assume that your data follows some specific polynomial of some degree $n$, i.e. you assume that your data has the form of ...

3

You can choose those states, but is the agent aware of the state it is in? From the text, it seems that the agent cannot distinguish between the three states. Its observation function is completely uninformative. This is why a stochastic policy is what is needed. This is common for POMDPs, whereas for regular MDPs we can always find a deterministic policy ...

3

First I will address the issue of Tabular methods. These do not use SGD at all. Although the updates are very similar to an SGD update there is no gradient here and so we are not using SGD. Many Tabular methods are proven to converge, for instance the paper by Chris Watkins titled "Q-Learning" introduces and proves that Q-learning converges. Also ...

3

The notion of a state in reinforcement learning is (more or less) the same as the notion of a context in contextual bandits. The main difference is that, in reinforcement learning, an action $a_t$ in state $s_t$ not only affects the reward $r_r$ that the agent will get but it will also affect the next state $s_{t+1}$ the agent will end up in, while, in ...

3

Conceptually, in general, how is the context being handled in CB, compared to states in RL? In terms of its place in the description of Contextual Bandits and Reinforcement Learning, context in CB is an exact analog for state in RL. The framework for RL is a strict generalisation of CB, and can be made similar or the same in a few separate ways: If the ...

2

Since I can't comment, there are a few caveats to previous answers. For instance, if you knew beforehand what the expected boundary function for that variable was, then you could transform it first. For instance, if you knew one feature was expected to be sinusoidal, you could transform your data (theta) using $f(x) = a*sin(\theta)$ first then expect the ...

2

There are a variety of possible things that could be wrong, but let me give you some potentially useful information. Neural networks with ReLU activation functions are Turing complete for a computation with on order as many steps as the network contains nodes - for a recurrent network (an RNN), that means the same level of turing completeness as any finite ...

2

A random function cannot be learned efficiently by any algorithm, in particular, neural networks. However, if you are looking for function with (exponentially) smaller description size, I do not know but any function that is conjectured to be average-case hard probably cannot be learned efficiently by neural networks, for example, Any cryptographic hard-...

2

This answer depends very much so on the type of neural network and algorithm used for training. If you are using gradient descent on a neural network of one input layer, one output layer, and no hidden layers there are many functions that you can't learn. One simple one is the XOR function. Due to the fact that XOR is not linearly separable, it can not be ...

2

Andrej Karpathy's blog has a tutorial on getting a neural network to learn pong with reinforcement learning. His commentary on the current state of the field is interesting. He also provides a whole bunch of links (David Silver's course catches my eye). Here is a working link to the lecture videos. Here are demos of DeepMinds game playing. Get links to the ...

2

I have found some clues in Maei's thesis (2011): “Gradient Temporal-Difference Learning Algorithms.” According to the thesis: GTD2 is a method that minimizes the projected Bellman error (MSPBE). GTD2 is convergent in non-linear function approximation case (and off-policy). GTD2 converges to a TD-fixed point (same point as semi-gradient TD). GTD2 is slower ...

2

There are three problems Limited capacity Neural Network (explained by John) Non-stationary Target Non-stationary distribution Non-stationary Target In tabular Q-learning, when we update a Q-value, other Q-values in the table don't get affected by this. But in neural networks, one update to the weights aiming to alter one Q-value ends up affecting other Q-...

2

To check if a function is linear is easy: if you can train one fully connected layer, without activations, of the right dimensions (for a function $\mathbb{R}^n \rightarrow \mathbb{R}^m$ you need $nm$ weights aka the matrix corresponding to the linear application), with enough data, to 100% accuracy... then it is linear. The estimated function is explicit: ...

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