DS161 Introduction to Data Science & Artificial Intelligence

Lecture 5

Introduction to AI Subfields

Krishnendu Ghosh

Machine Learning

What is machine learning?

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

What is machine learning?

Examples of the task, T

1. Classification: to learn a function 𝒇ℝ𝒏 → {𝟏, … , 𝒌}
2. Classification with missing inputs
3. Regression: to learn a function 𝒇𝒇: ℝ𝒏 → ℝ (prediction of temperature, stock market)
4. Transcription: for example, learning speech to text or image to text conversion
5. Machine translation: for example, learning to translate English to German
6. Structured output: for example, learning to mark the roads in a map
7. Anomaly detection
8. Denoising
9. Density estimation: to learn a function 𝒑model: ℝ𝒏 → ℝ where 𝒑model 𝒙 can be interpreted as a probability density function

What is machine learning?

​

​

Performance measure, P

1. For tasks like transcription and classification we measure the model accuracy
1. Accuracy = the proportion of examples for which the model produces the correct output
2. Error rate = the proportion of examples for which the model produces incorrect output
2. Data = { Training set, Test set }
• The model is trained using the training set
• Performance is assessed using the test set
3. Deciding the performance measure is not always very straight forward
4. For example, when performing a regression task, should we penalize the system more if it frequently makes medium sized mistakes or if it rarely makes very large mistakes

What is machine learning?

​

​

The Experience, E

1. Unsupervised Learning Algorithms experience a dataset containing many features, then learn useful properties of the structure of the dataset (such as anomaly detection, denoising, etc)
1. Learning the probability distribution p(x) by observing several examples of a random vector x.
2. Supervised Learning Algorithms experience a dataset containing features, but each example is also associated with a label or target
• Observing several examples of a random vector x and an associated value or vector y, and then estimating p( y | x )

Unsupervised and Supervised Learning are same

The chain rule of probability states that for a vector 𝒙 ∈ ℝ𝒏 , the joint probability distribution can be decomposed as:

​

The decomposition means that we can solve the problem of learning p( x ) by splitting it into n supervised learning problems

Alternatively we can solve the supervised learning problem p( y | x ) by using the traditional unsupervised learning technologies to learn the joint distribution p( x, y ), then inferring:

​

​

​

Why would one want machine learning?

• Static, pre-programmed rules might give poor performance
• Difficulties in analytically specifying the system
• Dimensionality of the problem is prohibitive
• ….

​

​

It is one tool that might or might not be able to solve the problem at hand!

​

​

Linear Regression

Given a training data set where:

The output is a linear function of the input which predicts the value of a scalar 𝒘∈ℝ:

𝒚’ = 𝒘^𝑻𝒙

where 𝒘 ∈ ℝ𝒏 is a vector of parameters. We can think of w as a set of weights.

Task T: Predict y from x by outputting 𝒚’ = 𝒘^𝑻𝒙

Performance: The mean squared error on the test data (which is different from the training data)

​

​

Linear Regression – a first cut approach

​

​

Linear Regression example

Capacity, Overfitting and Underfitting

​

​

• The ability of a machine learning algorithm to perform well on previously unobserved inputs is called generalization.
• Machine learning aims for low generalization error (also called test error)
• This depends on:
• Accurate choice of the model
• Quality of the training data
• A model’s capacity is its ability to fit a wide variety of functions
• For example, linear regression models cannot fit a sine function
• Low capacity leads to underfitting – the model is unable to obtain a sufficiently low error on the training data
• High capacity leads to overfitting – the model learns fictitious functions which results in high test error

Capacity, Overfitting and Underfitting

​

​

Capacity, Overfitting and Underfitting

​

​

The representational capacity of a model family is the set of functions that we are allowed to select

The effective capacity of a learning algorithm may be less than the representational capacity of the model family because the algorithm may restrict the hypothesis space

Occam’s razor: Among competing hypotheses that explain known observations equally well, we should choose the “simplest” one. We will therefore choose the quadratic one in the above.

​

​

Capacity vs Generalization Error

The No Free Lunch Theorem

How well can a machine learning algorithm generalize from a finite training set of examples?

The no free lunch theorem for machine learning [Wolper 1996] states:

Averaged over all possible data-generating distributions, every classification algorithm has the same error rate when classifying previously unobserved points.

Therefore in the absence of domain knowledge, no machine learning algorithm is universally any better than any other.

It is therefore important to understand the distributions relevant to the domain for choosing the model family and the learning algorithm.

​

​

Effect of Training Set

​

​

The quadratic model has inadequate capacity, hence training error increases with number of training examples. Also the test error asymptotes to a high value.

​

The optimal capacity plateaus after reaching sufficient complexity to solve the task.

​

​

​

Hyper-parameters and Validation Sets

​

​

• Most machine learning algorithms have hyper-parameters or settings that we can tune to control the algorithm’s behavior
• For example, in regression the degree of the polynomial acts as a capacity hyper-parameter
• Hyper-parameters should not be learned from the entire training set (why?)
• If learned on the training set, such hyper-parameters would always choose the maximum possible model capacity
• The test set must also not be used to learn the hyper-parameters
• Typically one uses about 80% of the training data for training and 20% for validation. This subset is called the validation set.

Machine Learning Process

​

​

How to do Machine Learning

​

​

For (supervised) classification and regression (the most common tasks):

1. Algorithm selection: Choose an algorithm
2. Feature selection: Choose features that capture the important characteristics of the system
3. Training/model building: Use part of the labeled set to build the model
4. Parameter optimization (cross-validation): Optimize the parameters using a second part of the labeled set to minimize the error rate
5. Test: Use the remainder of the dataset to validate and assess the performance of the tuned model
6. Apply