Stanford Course Notes

Notes for the Engineering Everywhere Databases, Artificial Intelligence and Machine Learning courses

[skynetcometh]

Stone Temple Consulting are an "Internet Marketing Optimization" consultancy whose news site, stonetemple.com, keeps a close eye on technological trends in social media and search.

Yesterday, they happened to print an interview with one of our profs for #ai-class, Peter Norvig, about his work in applying AI methods as director of research for Google.

[skynetcometh]

Late Assignments

What happens if I do not meet the deadline on an assignment?

This is getting asked a fair bit on G+ so I thought I'd check out the answer and publish it here. 

Depending on which class you are in, it goes like this:

AI-class: You can drop the two lowest-scoring assignments out of the 8 across the whole course. Answers to the homework are published after the due date so late assignments get 0.

ML-class: You can hand in late with a small penalty to your mark based on how late the submission is.

DB-class: Assignments posted after the deadline have a 50% score penalty.

None of the classes can move the exam date, but exams are available for a full 24 hours. Check you have converted the start and end times to your own timezone.

[skynetcometh]

Cocktail Party Algorithm

Cocktail Party Problem

Consider a cocktail party with numbers of people whose voices are all overlapping.

2-person: place 2 microphones at different distances to speakers, record two different combinations of the voices (Microphone 1 closer to speaker 1, microphone 2 closer to speaker 2).

The Cocktail Party Algorithm finds structure in the two microphone recordings. It concludes two sources of sound are being summed, separates them and outputs them individually.

[W,s,v] = svd ((repmat(sum(x.*x,1),size(x,1),1).*x)*x');

Octave

Good programming environment for learning algorithms.

Commonly used to prototype algorithms as code is shorter and simpler in Octave.

[skynetcometh]

Unsupervised Learning

Data has no labels, only correlation between features.

Clustering Algorithm

Algorithm seeks pattern/structure in data set - breaks it into "clusters."

E.g. Google News.

Looks at 10s of 1000s of news stories on the internet, groups them into clusters of the same story from different sources.

Also used in:

Genomics - categorize people according to the degree to which they express certain genes.

Computing clusters - analyse which machines work together and link them for greater efficiency.

Social networks - analyse Friends lists to identify groups that all know each other.

Market segmentation - categorises customers into groups that will like similar products.

[skynetcometh]

Supervised Learning - Classification Problem

A classification problem attempts to predict a discrete-valued output, e.g. benign or malignant, true or false; red, blue or yellow; blood types etc.

Classification problems can be plotted with different symbols for each class rather than a boolean dependent variable.

In a classification problem with more than one attribute (feature) determining the result, learning algorithm will try to fit a line to the graph separating the output categories.

More than two features are also possible, they're just a bitch to draw.

Support Vector Machine (SVM)

Sometimes the best choice is to use infinite features, so algorithm has lots of attributes on which to base predictions.

Mathematical trick required to allow PC (limited memory) to deal with infinite number of features.

Support vector machines tutorial

[skynetcometh]

Supervised Learning - Regression Problem

Consider a set of data (e.g. house price vs. size) plotted on a scattergraph.

One learning algorithm might fit a straight line to that data. A different one might fit a quadratic function to the data.

This is supervised learning because the algorithm was given a data set of “right answers” (real-world values) from which it can infer other values using the function it defined.

A regression problem attempts to predict a continuous-valued output, e.g. house price.

[skynetcometh]

Machine Learning Definitions

Arthur Samuel (1959) - Field of study that gives computers the ability to learn without being explicitly programmed.

Tom Mitchell (1998) - A computer program is said to learn from experience E with respect to some task T and some performance measure P if its performance on T, as measured by P, improves with experience E. 

Types of Machine Learning Algorithm

Supervised learning - "teach" machine a task.

Unsupervised learning - machine learns by itself.

Reinforcement learning

Recommender systems

[skynetcometh]

Introduction to Machine Learning

Learning algorithms try to mimic how the human brain works. 

Machine learning is the most desired skill in the IT job market.

Examples of Learning Algorithms in Use

Page ranking of internet search results.

Recognizing faces from tagged photos.

Identifying spam mails.

Database mining - machine learning is needed to process the huge data sets gathered through automated processes and the internet. E.g:

web click data (aka click stream data) reveals consumer interests,

medical records can be parsed into medical knowledge,

biology uses machine learning to try to understand the human genome.

Applications that are too large/complex to program by hand. E.g:

Autonomous helicopter had to learn to fly by itself,

Handwriting recognition - automatic routing of hand-addressed mail,

Natural Language Processing (NLP),

Computer vision.

Self-customizing programs e.g. Amazon recommendations, Netflix etc. Too many users so software must learn to customize itself to user preferences.

Study of cognition.

[skynetcometh]

Route Finding

Frontier - the furthest points that have been explored. Separates unexplored from explored.

[skynetcometh]

Defining a Problem

Initial state s

Actions(s) -> {a1, a2,a3... an} [1]

Result(s,a) -> s1

GoalTest(s) -> bool [2]

StepCost(s,a,s1) -> n [3]

PathCost(n) -> (nold + n)

[1] In some problems, agent will always have same set of actions available, in others, set of possible actions depends on current state s.

[2] Tests whether goal state is achieved i.e. is problem solved? Returns true or false.

[3] n is a number quantifying the undesirability of a state-action transition. E.g. in a route-finding problem, it might be the number of miles travelled from state/city 1 to state/city 2, where the goal is to find the shortest route from one city to another.

[skynetcometh]

Introduction to Problem Solving

Building intelligent agents that can plan ahead to solve problems.

This unit examines agents for problems where complexity caused by multitude of states. Agent must make series of correct choices to achieve optimal solution.

Problems with partially observable environments will be examined in a later unit.

[skynetcometh]

Readings for Unit 1

Russell & Norvig - Artificial Intelligence: A Modern Approach

1.1 What Is AI? 1.4 The State of the Art 1.5 Summary

2.1 Agents and Environments 2.2 Good Behavior: The Concept of Rationality 2.3 The Nature of Environments

[skynetcometh]

Unit 1 Summary

Key applications of AI

Definition of intelligent agent

Key attributes of agent environments: 

Partial/full observability

Determinism/stochasticism

Discretion/Continuity

Benign/Adversarial

Sources & management of uncertainty

Rationality as optimization views decision making as a fully rational process of finding an optimal choice given the information available.

[skynetcometh]

Examples of AI in Use

Google - machine translation of 50 human languages.

Build translation model

AI is given samples of text where one language is translated into another e.g. bilingual newspapers.

Correlates words into one version into words in the other across large no. of samples, millions of words of text.

Build probability tables of what one word or phrase corresponds to a word or phrase in the other language.

Use translation model

Look up past correlations to find most likely translation.

[skynetcometh]

AI and Uncertainty

AI is a tool for choosing an optimal action when a program does not know what to do.

Reasons for Uncertainty:

Sensor limitations - sensors may not be able to fully describe environment.

Adversaries - deceptive behaviour e.g. concealing hand in poker, bluffing.

Stochastic environment.

"Laziness" - solution could be computed but require excess time/resources.

"Ignorance" - in human system, could know but doesn't care.

[skynetcometh]

[skynetcometh]

Terminology

Environment is fully observable if agent's sensors can detect all information required to make optimal decision at any point in time i.e. Sensors can always perceive entire state of environment. 

If agent requires memory, then environment is only partially observable. The sensors can only perceive fraction of the environment's state at any given moment.

Memory of past measurements provides additional information in a partially observable environment e.g cards that have already been discarded in a game of Blackjack.

Environment is deterministic if agent's actions uniquely determine the outcome e.g. chess - pieces move according to rules, always the same outcome to the same move. 

If environment has random element, is stochastic e.g. dice games. 

Discrete - finite number of possible states / finite number of possible actions. Continuous - infinite number of states / possible actions. 

Benign - environment has no objective of its own to oppose the agent's. Adversarial - environment has own objective e.g. opposed games. Harder to take good actions when opposed.