Machine Learning

Artificial intelligence aims to build systems capable of performing useful tasks. Rather than manually specifying how the system should solve the task, machine learning approaches a problem by specifying a parameterized model \(f_\theta(x)\) and using data to find parameters \(\theta\) that make it perform well. The process of adjusting these parameters based on data is called training or optimization. Deep learning is machine learning using neural networks with many layers, typically trained using gradient descent and backpropagation.

¹ The three possible settings are: supervised (human/external labels), self-supervised (targets constructed from data), and reinforcement (rewards generated through interaction).

Supervised Learning

Different machine learning settings differ primarily in what information is available for learning. In supervised learning, we have examples paired with desired outputs:

The model learns to predict \(y\) from \(x\). If \(y\) belongs to a discrete set, such as the object contained in an image, this is classification. If \(y\) is continuous, such as a numerical rating, this is regression. The difficulty is that obtaining labels often requires humans to produce them. Large quantities of raw data may be readily available even when corresponding human labels are expensive.

Self-Supervised Learning

Self-supervised learning avoids requiring humans to explicitly label every example by constructing the learning target from the data itself. For text, for example, any sequence \(x_1,x_2,\ldots,x_t\) automatically provides many training examples of the form \((x_1,\ldots,x_t)\rightarrow x_{t+1}\).

The text therefore supplies both the input and the target without someone manually annotating what each passage means. This makes it possible to learn from enormous quantities of otherwise unlabeled data.

Reinforcement Learning

Supervised and self-supervised learning can be understood as learning from datasets. In reinforcement learning, the model instead interacts with an environment. At time \(t\), an agent takes an action \(a_t\), receives an observation of what happens next, and receives a numerical reward \(r_t\).

The goal is to learn behaviour that produces high cumulative reward.

This however creates a difficulty: an action may affect rewards much later. Determining which earlier actions deserve credit or blame for later outcomes is the credit assignment problem.

There are a few constraints: first, training data are finite. A model therefore encounters situations after training that it has never seen before. If it is able to perform well on new examples of the same kind, it is said to generalize. Second, the real world may differ more substantially from the training setting. A system may need to apply capabilities learned in one setting to a meaningfully different one. This is often described as transfer. We do not, however, have a clear boundary between generalizing within a task and transferring to a new task.

This means that in order to design a machine learning system, we must (1) choose an optimization algorithm, and further (2) decide what data or environment the model learns from and what objective it is trained to optimize.

Self-Supervised Learning

Suppose we want a model to distinguish images of cats from images of dogs. In supervised learning, we provide examples together with their correct labels:

The model makes a prediction, compares it with the supplied label, and adjusts its parameters to reduce the error. The problem is that obtaining large labelled datasets can be expensive.

² Although enormous quantities of images, text and other data already exist, humans would have to manually provide the desired output for each example.

In self-supervised learning, the supervision is instead obtained from the data itself. We take an unlabelled example \(x\) and construct a prediction problem for which some part of \(x\) provides the target. For example, given an image, we might hide part of it and ask the model to predict the missing portion:

The same idea applies naturally to language. Given a sequence of tokens \(x_1,x_2,\ldots,x_t\), we can use the preceding tokens as the input and the next token as the target: \((x_1,\ldots,x_t)\rightarrow x_{t+1}\).

The target does not need to be manually labelled because it already occurs in the original text. This is the next-token prediction objective used to pretrain GPT-style language models. Predicting missing image regions or the next token forces the model to learn regularities that help it make those predictions. The resulting internal representations can then be useful for other tasks.

The advantage is therefore not that learning occurs without an objective or without feedback. Rather, we can manufacture the learning signal automatically from raw data, allowing training to scale to datasets that would be impractical to label manually.

Reinforcement Learning

Agents and Environments

In supervised learning, a model learns from a dataset containing examples of desired behaviour. Many problems instead involve an actor repeatedly interacting with a world, where its actions affect what happens next. Reinforcement learning (RL) studies how an agent can learn behaviour through this interaction.

At time \(t\), the environment is in some state \(s_t\), describing everything relevant about the world. The agent takes an action \(a_t\), after which the environment changes:

³ \(P(\cdot\mid s_t,a_t)\) shows the entire distribution of \(P(s_1\mid s_t,a_t), P(s_2\mid s_t,a_t), P(s_3\mid s_t,a_t)\), and so on, for possible future states.

Here \(P\) is the transition model: it specifies how the current state and action determine a distribution over possible next states. In a deterministic environment this instead reduces to

⁴ Unlike a stochastic environment where probability is used to sample future states, here the current state and action completely determine the next state.

The agent does not always observe the complete state. An observation \(o_t\) contains the information about the state that is actually available to the agent. If the observation contains the complete state, the environment is fully observed; otherwise it is partially observed.

Policies

Knowing what the agent observes does not yet tell us what it will do. We therefore need a rule mapping the information available to the agent to actions. This is called a policy.

A deterministic policy selects one action for each state:

while a stochastic policy specifies a probability distribution over possible actions, where the agent does not have to always choose a particular action for an observation. We sample an action \(a_t\) from the probability distribution over all actions given state \(s_t\):

In practice, if the agent only receives an observation, the policy acts on that observation rather than the inaccessible true state. In that case, for an observation \(o_t\):

For complicated environments, we cannot define a mapping to an action for every state. We may therefore let the policy be a neural network with parameters \(\theta\):

Changing \(\theta\) changes the probabilities with which the agent chooses actions.

Trajectories

Because actions change the environment, we care about sequences of interaction rather than isolated predictions. A trajectory is a sequence

where the initial state is drawn from some starting distribution

actions are produced by the policy, and subsequent states are produced by the transition model. For stochastic policies and transitions, the probability of a trajectory is therefore determined jointly by the environment and the agent:

Reward and Return

The environment also produces a numerical reward describing the desirability of what happened:

An action that gives a small immediate reward may nevertheless lead to much better outcomes later, so the agent should not generally maximize \(r_t\) independently at every timestep. Instead, we care about the reward accumulated across the trajectory, known as the return.

For a finite task,

For an indefinitely continuing task, future rewards are often discounted:

where \(\gamma\) is the discount factor. Larger \(\gamma\) makes distant rewards matter more, while smaller \(\gamma\) places greater weight on immediate outcomes.

⁵ Discounting also ensures that the infinite sum converges under suitable conditions.

Since both the policy and environment may be stochastic, the same policy can generate different trajectories and therefore different returns. We consequently evaluate a policy by its expected return

The central RL problem is then

Value Functions

To choose actions well, it is useful to estimate not merely the reward available now but what a situation is likely to lead to later. The value function \(V^\pi(s)\) is the expected return obtained by starting in state \(s\) and subsequently following policy \(\pi\):

Sometimes we instead want to evaluate a particular action. The action-value function \(Q^\pi(s,a)\) is the expected return from starting in \(s\), first taking action \(a\), and then following \(\pi\):

⁶ Intuitively, \(V^\pi(s)\) asks "how good is it to be here?", while \(Q^\pi(s,a)\) asks "how good is it to take this action here?".

If we knew the optimal action-value function \(Q^*\), choosing the optimal action would simply require

← Writing