Approximation Theory#

The purpose of studying Approximation Theory is to better understand the Universal Approximation Theorem, which defines the limits (or unbounded potential) of AI and Machine Learning on what Neural Networks can learn to solve real-life problems. Approximation Theory is the foundation of Machine Learning and its usefulness is brought to life by the advancement of contemporary computing power. For example, Approximation Theory says an approximated function exists by Math theorem but does not indicate how to reach that approximation. Artificial Neural Network, trained by Big Data, reaches that optimal function. Approximation theory is the proof of why AI or Machine Learning works.

K-Armed Bandit Problem: Reinforcement Learning as an Example of Approximation

Consider the following learning problem. We are faced repeatedly with a choice among $k$ different options, or actions. After each choice we receive a numerical reward chosen from a stationary probability distribution that depends on the action we selected. Our objective is to maximize the expected total reward over some time period, for example, over 1000 action selections, or time steps. This is the original form of the $k$-armed bandit problem

Mathematically, each of the $k$ actions has an expected or mean reward given that one action is selected; let us call this the value of that action. We denote the action selected on time step $t$ as $A_t$ and the corresponding reward as $R_t$, The value of an arbitrary action $a$, denoted $q_*(a)$, is the expected reward given that $a$ is selected:

$$q_*(a) = \mathbb{E}[R_t|A_t = a]$$

If we know the value of each action, then it would be trivial to solve the $k$-armed bandit problem: we would always select the action with the highest value. We do not know, however, the action values with certainly in reality, although we may have estimates. We denote the estimated value of action $a$ at time step $t$ as $Q_t(a)$. We would like $Q_t(a)$ to be close to $q_*(a)$.

If we maintain estimates of the action values, then at any time step there is at least one action whose estimated value is greatest. We call these the greedy actions. When we select one of these actions, we say that we are exploiting our current knowledge of the values of the actions. If instead we select one of the non-greedy actions, then we say we are exploring, because this enables us to improve our estimate of the non-greedy action’s value. Exploitation is the right thing to do to maximize the expected reward on the one step, but exploration may produce the greater total reward in the long run.

Given that exploring and exploiting is not possible in any single action, systematic methods are used to balance the exploration and exploitation. This is the basic idea behind reinforcement learning.

Defining Machine Learning#

Machine Learning addresses the question of how to build computer programs that improve their performance at some task through experience.

Definition of Learning

A computer program is said to learn from experience $E$ with respect to some class of tasks $T$ and performance measure $P$, it its performance at tasks in $T$, as measured by $P$, improves with experience $E$.

The problem of inducing general functions from specific training examples is central to learning.

Machine Learning v.s. Data Mining

Machine Learning and Data Mining often employ the same methods and overlap significantly, but while machine learning focuses on prediction, based on known properties learned from the training data, data mining focuses on the discovery of (previously) unknown properties in the data (this is the analysis step of knowledge discovery in databases)