17
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 ...
10
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 ...
10
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, ...
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_{...
8
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 consistent ...
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
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 ...
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 ...
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
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 ...
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
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 ...
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 ...
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
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
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
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 ...
3
"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 ...
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 ...
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:...
2
In laymen's terms, a non-expansive operator is a function that brings points closer together or at least no further apart.
An example of a non-expansive operator is the function $f(x) = x/2$. The two numbers $0$ and $5$ are a distance of $5$ apart. The two output numbers $f(0) = 0$ and $f(5) = 2.5$ are 2.5 apart (which is smaller than $5$ apart). It is easy ...
2
Welcome to AI.SE @hpr16!
Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given state to a goal state.
Notice that states in the search are not the same as positions on the circle in your problem. A state needs to capture all the ...
2
Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $h_{\max}(n)$ and $h_{\min}(n)$ are, by definition (of $h_{\max}$ and $h_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes $n$, ...
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
The key phrase here is
because heuristics are admissible
In other words, the heuristics never overestimate the path length:
$$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$
And since the frontier is ordered by $\textbf{cost + heuristic}$, when a completed path $p$ is dequeued from the frontier, we know that it must necessarily be $\...
2
See the paper On the Convergence Properties of the Hopfield Model (1990), by Jehoshua Bruck.
In the first section of the paper, J. Bruck describes the Hopfield network (popularized by J. J. Hopfield in 1982 in his paper Neural networks and physical systems with emergent collective computational abilities, hence the name of the network), then he describes ...
Only top voted, non community-wiki answers of a minimum length are eligible
