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 ...
12
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 ...
12
This is a really common reaction after first encountering the No Free Lunch theorems (NFLs). The one for machine learning is especially unintuitive, because it flies in the face of everything that's discussed in the ML community. That said, the theorem is true, but what it means is open to some debate.
To restate the theorem for people who don't know it, ...
11
This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details.
First, let's review the definitions:
Your definitions of admissible and consistent are correct.
An admissible heuristic is basically just "optimistic". It never overestimates a distance.
A ...
9
Let's start by looking at:
$$\max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert.$$
We can rewrite this by plugging in the definition of $G_{t:t+n}$:
\begin{aligned}
& \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\
%
=& \max_s \Bigl\lvert \mathbb{...
8
Using the law of iterated expectations one has:
$\triangledown _\theta \sum_{t=1}^T \mathbb{E}_{(s_t,a_t) \sim p(s_t,a_t)} [b(s_t)] = \nabla_\theta \sum_{t=1}^T \mathbb{E}_{s_t \sim p(s_t)} \left[ \mathbb{E}_{a_t \sim \pi_\theta(a_t | s_t)}
\left[ b(s_t) \right]\right] =$
written with integrals and moving the gradient inside (linearity) you get
$= \sum_{...
7
In general the different reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ are not equivalent mathematically, so you will not find any formal proof.
It is possible for the functions to resolve to the same value in a specific MDP, if, for instance, you use $R(s, a, s')$ and the value returned only depends on $s$, then $R(s, a, s') = R(s)$. This is not true ...
7
There is stuff like the Universal Approximation Theorem.
There are also investigations into the loss surface of neural networks.
And classics like this explanation of the vanishing gradient problem.
But I'm afraid the mathematical theory of neural networks only exists in bits and pieces in many different papers. And many of the most important questions ...
6
A strong reason why people think the mind can be implemented on a Turing Machine stems from the Computational Theory of Mind (CTOM), which is the leading theory of mind for now.
There are lots of reasons for supporting the CTOM, one of which being that the language of belief/desire psychology (propositional attitudes over mental representations) seems to fit ...
6
Yes, UCS is a special case of A*.
UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...
6
The convergence and optimality proofs of (linear) temporal-difference methods (under batch training, so not online learning) can be found in the paper Learning to predict by the methods of temporal differences (1988) by Richard Sutton, specifically section 4 (p. 23). In this paper, Sutton uses a different notation than the notation used in the famous book ...
6
First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also ...
5
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, ...
5
We can start with equation (30):
$$
\bar{A}(s) = P(a \neq \tilde{a}) \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]
$$
Taking the absolute value of both sides, the equality remains true. We can pull the probability term out of the absolute value since it is guaranteed to be nonnegative.
$$
|\bar{A}(s)| = ...
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
No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.
s --1-- g
Assume that $h_0$ and $h_1$ are perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an ...
5
This is the analytical form of the KL divergence between two multivariate Gaussian densities with diagonal covariance matrices (i.e. we assume independence). More precisely, it's the KL divergence between the variational distribution
$$
q_{\boldsymbol{\phi}}(\mathbf{z})
=
\mathcal{N}\left(\mathbf{z} ; \boldsymbol{\mu}, \mathbf{\Sigma} = \boldsymbol{\sigma}^...
4
What is Proven
The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems.
The 1989 proof stated that the network, made of activations that were required to be, "Of continuous sigmoidal non-linearity," could, "Uniformly approximate any continuous ...
4
Consciousness is not well-understood
As an AI practitioner and philosopher, I don't think that humans will be able to create a truly conscious silicon-based AGI.
Humans are incapable of creating some "thing" from fiat (a decree). It's never happened in human history. The innovation cycle must begin with some "thing" (some "stuff&...
4
Let $R(s)$ denote a probability distribution over rewards that our agent may get in some MDP as a reward for entering a state $s$. The easiest case is to demonstrate that we can also choose to write this as $R(s, a)$ or $R(s, a, s')$: simply take $\forall a: R(s, a) = R(s)$, or $\forall a \forall s': R(s, a, s') = R(s)$, as also described in Neil's answer.
...
4
This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another and vice-versa. Think of it as a game of rock paper scissors.
Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $...
4
The code is correct. Since OP asked for a proof, one follows.
The usage in the code is straightforward if you observe that the authors are using the symbols unconventionally: sigma is the natural logarithm of the variance, where usually a normal distribution is characterized in terms of a mean $\mu$ and variance. Some of the functions in OP's link even have ...
3
Here is my take.
The larger the $\lambda$, the more the corresponding regularization term for a coefficient will be big, so when minimizing the cost function, the coefficient will be reduced by a bigger factor, you can see this effect in the derivation of the update rule for gradient descent for example:
\begin{align*} \theta_j := \theta_j - \alpha\ \left[ \...
3
I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with $r(s,a,s')$ rewards would look like this:
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\} $$
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') + \gamma \sum_{s'} p(s'|a,s) \cdot V(s') \right\} $$
Now, ...
3
There are programming languages that allow you to verify a proof by induction. For example, I used Coq, but I'm sure there are also others.
3
The reason you are confused is because this is not the full derivation of the Policy Gradient Theorem. You are correct in thinking that $\mu(s)$ depends on the policy $\pi$ which in turn depends on the policy parameters $\theta$, and so there should be a derivative of $\mu$ wrt $\theta$, however the Policy Gradient Theorem doesn't require you to take this ...
3
In essence, your question is about convergence of infinite series. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "hardware architecture".
A basic example of an infinite series is the geometric series:
$$ S = 1 + \gamma + \gamma^2 + \gamma^3 + \dots$$
Note that the series is ...
2
The expectation is over the policy $\pi'$ because the action at the state $S_t = s$ is taken according to $\pi'$, and, for the proof, the book text (2nd edition, paragraph below Equation 4.8) defines $\pi'$ to be a policy that is identical to $\pi$ except that $\pi'(s) = a \neq \pi(s)$, where $s$ is one particular state.
So, essential, the book text tries ...
2
Regarding Artificial General Intelligence, which does not currently exist and is still highly theoretical, this cannot be determined at this time.
What I would say is that "strong narrow AI" has already proven the ability to become "smarter" than it's creators in specific tasks. (See Alphago, etc.)
Under the idea that some form of AGI might come out of an ...
2
I'm going to go out on a limb and suggest that this is a matter of evolution, that humans are in no way exceptional in the grand scheme, and that AGI will manifest so long as technology advances, because human consciousness is simply a matter of complexity of the system.
The idea comes out of emergent complexity in Conway's Game of Life. In Conway's words:...
Only top voted, non community-wiki answers of a minimum length are eligible