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 ...
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, ...
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 ...
7
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{...
7
Good morning! You're using an extremely general term ("AI") for an extremely specific idea ("something human made that is almost identical to the human mind"). Thus, your question is not what you think it is.
AI, according to John McCarthy (who Wikipedia claims coined the term and is the equivalent of a rockstar in the AI field), is the engineering of ...
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 ...
7
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 ...
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 ...
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 ...
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
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
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
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
Why Humans will NEVER create true existential consciousness in a silicon based Artificial Intelligent System.... the musings of an AI Practitioner / Philosopher.
THE ARGUMENT(s):
⦁ 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" of some ...
4
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 ...
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 $...
3
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 function of n ...
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
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
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
The Bellman optimality equation is given by
$$q_*(s,a) = \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')}q_*(s',a')) \tag{1}\label{1}.$$
If the reward is multiplied by a constant $c > 0 \in \mathbb{R}$, then the new optimal action-value function is given by $cq_*(s, a)$.
To prove this, we just need to ...
2
Definitely, you can find the proof in different resources (for example, in these notes or in the paper that originally proposed PAC learnability, A Theory of the Learnable). However, the intuition behind your question is when the size of the hypothesis increases, if you do not change anything, you can't see more part of the space. Hence, the estimation error ...
2
To prove that the KL divergence does not satisfy the triangle inequality, you just need a counterexample.
Definitions
KL divergence
Let's first recapitulate the definition of KL divergence for discrete probability distributions $p$ and $q$ (for simplicity).
$$
D_{\text{KL}}(p\parallel q)
=
\sum_{x\in {\mathcal {X}}}
p(x)\log
\left(
\frac {p(x)}{q(x)}
\...
2
You can find by yourself a counterexample that, in general, GD is not guaranteed to find the global optimum!
I first advise you to choose a simpler function (than the one you are showing), with 2-3 optima, where one is the global and the other(s) are local. You don't need neural networks or any other ML concept to show this, but only basic calculus (...
2
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 ...
1
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
