10

There are several papers related to the topic, because there have been several attempts to show this from slightly different perspectives and using slightly different assumptions (e.g. assuming that certain activation functions are used). The article A visual proof that neural nets can compute any function (by Michael Nielsen) should give you some intuition ...


8

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 ...


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

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, ...


4

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.


4

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 $<$...


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

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

Any supervised learning problem can be cast as an equivalent reinforcement learning 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 predicted ...


3

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 ...


2

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 ...


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

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: ...


2

In my humble opinion, it seems like it is important to have them separated, if having a certain card can influence the result in some way that is not its prime value, instead of not only using the sum. But it depends on the game and its rules. For example: If having 5 cards of hearts in the set of 15 cards makes you win the game, then if you only represent ...


2

By itself, I'm not sure it's possible to know. It's possible the slides were old. Or, the intended purpose was to mention how as sigmoid ranges from 0 to 1. Mostly, it looks like it was intended to bring up gradient descent. But it could also be an entry point to the discussion of other methods such as ReLU. Either that or perhaps some sort of norming ...


2

We usually optimize with respect to something. For example, you can train a neural network to locate cats in an image. This operation of locating cats in an image can be thought of as a function: given an image, a neural network can be trained to return the position of the cat in the image. In this sense, we can optimize a neural network with respect to this ...


1

First part is correct \begin{align} &\sum_{n=1}^{\infty} \alpha(1-\lambda)\lambda^{n-1} (\bar R_t^{(n)} - \theta^T \phi_t)\\ =& \alpha[\sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \bar R_t^{(n)} - \sum_{n=1}^{\infty} (1-\lambda)\lambda^{n-1} \theta^T \phi_t] \end{align} $\sum_{n=1}^{\infty} (1-\lambda)\lambda^{(n-1)}$ sums to $1$ so we have \begin{...


1

Naturally, one might let the MDP run for 1000 periods, and then terminate as an approximation. If we feed these trajectories into a monte carlo update, I imagine that samples for time period t=1,2,...,100 would give very good estimates for the value function due to the discount factor. However, the time periods 997, 998, 999, 1000, we'd have an expected ...


1

Apparently there is an example of non-convergence for semi-gradient sarsa, according to Rich Sutton (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to satisfy certain conditions to proof convergence. Maybe this paper will be useful for you. It seems that they show that constraining your network to have relu ...


1

As far as I know, more than 3 channel is perfectly fine, since, 3 channels are what we use for images and that's enough since we can only see this many colors, but I don't see why more than that wouldn't work Your 2nd question is like asking whether or not you will be good at a sport... Just try it For your 3rd question, I've never seen any language AI ...


1

A network is able to fit to a certain function over several iteration while training. Now you want the model to be able to detect a change in a list of inputs from the function. This is not possible without first training the model on some data. Say you want to use a simple function # Sample function f(x) = x Say you create inputs for function using sets ...


1

The network is the function. A network is a function, that is modeled by terms describing the architecture and coefficients that are learned. Look at a simple model: $$f(x) = ax+b$$ Your solver determines $a$ and $b$, and you substitute them into $f(x)$ and then you're able to calculate $f(42)$. The function is linear by definition, but may not be a good ...


1

Using the book's random walk example, If you have a state space with $1000$ states and you divide them into $10$ groups, each of those groups will have $100$ neighboring states. The function for approximation will be \begin{equation} v(\mathbf w) = x_1w_1 + x_2w_2 + ... + x_{10}w_{10} \end{equation} Now, when you pick a state, the feature vector will be a ...


1

If the concept class specified is $$f(x, y) = k \, \sin(2 \pi f_x x) \, sin(2 \pi f_y y) \\ \land 0 < x < 1 \\ \land 0 < y < 1 \; \text{,}$$ and the optimum fit to example data is expected occur when $k \approx 1 \land f_x \approx 1 \land f_y \approx 1$, then it is not an AI problem. It is a problem that can be solved with a least squares ...


1

For the function you mentioned, There has to be two input and one output neuron representing x and y values. Use the ReLU function at the input and hidden layers. Use linear activation function on the output layer. This will create a regression architecture which will approximate the function as required.


1

Semi gradient methods work well in Reinforcement Learning, but what is the reason of not using the true gradient if it can be computed? Just complexity and extra computation, in many cases for a marginal benefit. I tried it on the cart pole problem with a deep Q-Network and it performed much worse than traditional semi gradient, is there a concrete ...


1

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 ...


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