Machine Learning Fall, 2007 Course Information

Course Information Instructor: 유석인 교수 - Office: 302 동 321 호 - E-mail: [email_address] Text: Machine Learning (by Tom Mitchell) Reference: Pattern Recognition and Machine Learning (by Christopher Bishop) Prerequisite: 이산수학 , 확률이론 , 인공지능개론

Grading Policy 5 Equally Weighted Exams + Class Attendance Grading Policy: Based on grade evaluated from 5 exams, - Up to 2 classes not attended: Grade Not Changed - 3-4 classes not attended: 1 Step Lower Grade - 5-6 classes not attended: 2 Step Lower Grade - More than 6 classes not attended: Grade of F

Types of Learning Supervised Learning: Given training data comprising examples of input vectors along with their corresponding target vectors, goal is either (1) to assign each input vector to one of a finite number of discrete categories (classification) or (2) to assign each input vector to one or more continuous variables (regression). Unsupervised Learning: Given training data consists of a set of input vector without any corresponding target values, goal is to either (1) to discover groups of similar examples within data, called clustering , or (2) to determine the distribution of data within the input space, known as density estimation , or (3) to project the data from a high-dimensional space down to two or three dimensions for the purpose of visualization . Reinforcement Learning: Given an agent having a set of sensors to observe the state of its environment and a set of actions it can performs to alter this state, goal is to find suitable actions to take in a given situation in order to maximize the accumulated reward where each action resulting in certain state is given a reward (exploration and expoitation).

Schedule Introduction of Machine Learning Concept Learning Decision Tree Learning Artificial Neural Networks Learning Evaluating Hypotheses Bayesian Learning Instance-based Learning Learning Sets of Rules Analytical Learning Combining Inductive and Analytical Learning Reinforcement Learning

Introduction Machine Learning, Fall 2007

Well-Posed Learning Problems Definition : 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.

Well-Posed Learning Problems : Examples A checkers learning problem Task T : playing checkers Performance measure P : percent of games won against opponents Training experience E : playing practice games against itself A handwriting recognition learning problem Task T : recognizing and classifying handwritten words within images Performance measure P : percent of words correctly classified Training experience E : a database of handwritten words with given classifications

Well-Posed Learning Problems : Examples A robot driving learning problem Task T : driving on public four-lane highways using vision sensors Performance measure P : average distance traveled before an error (as judged by human overseer) Training experience E : a sequence of images and steering commands recorded while observing a human driver

Designing a Learning System Choosing the Training Experience Choosing the Target Function Choosing a Representation for the Target Function Choosing a Function Approximation Algorithm The Final Design

Choosing the Training Experience Whether the training experience provides direct or indirect feedback regarding the choices made by the performance system: Example : Direct training examples in learning to play checkers consist of individual checkers board states and the correct move for each. Indirect training examples in the same game consist of the move sequences and final outcomes of various games played in which information about the correctness of specific moves early in the game must be inferred indirectly from the fact that the game was eventually won or lost – credit assignment problem.

Choosing the Training Experience The degree to which the learner controls the sequence of training examples: Example : The learner might rely on the teacher to select informative board states and to provide the correct move for each The learner might itself propose board states that it finds particularly confusing and ask the teacher for the correct move. Or the learner may have complete control over the board states and (indirect) classifications, as it does when it learns by playing against itself with no teacher present.

Choosing the Training Experience How well it represents the distribution of examples over which the final system performance P must be measured: In general learning is most reliable when the training examples follow a distribution similar to that of future test examples. Example : If the training experience in play checkers consists only of games played against itself, the learner might never encounter certain crucial board states that are very likely to be played by the human checkers champion. (Note however that the most current theory of machine learning rests on the crucial assumption that the distribution of training examples is identical to the distribution of test examples)

Choosing the Target Function To determine what type of knowledge will be learned and how this will be used by the performance program: Example : In play checkers, it needs to learn to choose the best move among those legal moves: ChooseMove: B  M , which accepts as input any board from the set of legal board states B and produces as output some move from the set of legal moves M .

Choosing the Target Function Since the target function such as ChooseMove turns out to be very difficult to learn given the kind of indirect training experience available to the system, an alternative target function is then an evaluation function that assigns a numerical score to any given board state, V: B  R .

Choosing a Representation for the Target Function Given the ideal target function V , we choose a representation that the learning system will use to describe V’ that it will learn: Example : In play checkers, V’(b) = w 0 + w 1 x 1 + w 2 x 2 + w 3 x 3 + w 4 x 4 + w 5 x 5 + w 6 x 6 where w i is the numerical coefficient or weight to determine the relative importance of the various board features and xi is the number of i-th objects on the board.

Each training example is given by <b, V train (b)> where V train (b) is the training value for a board b . Estimating Training Values: V train (b)  V’(Successor(b )). Adjusting the Weights: To specify the learning algorithm for choosing the weights w i to best fit the set of training examples { <b, V train (b)> }, which minimizes the squared error E between the training values and the values predicted by the hypothesis V’ E   <b,V train (b)>  training examples (V train (b) – V’(b)) 2 Choosing a Function Approximation Algorithm

E   <b,V train (b)>  training examples (V train (b) – V’(b)) 2 To minimize E, the following rule is used: LMS weight update rule Choosing a Function Approximation Algorithm For each training example <b, V train (b)> Use the current weights to calculate V’(b) For each weight w i , update it as w i  w i +  (V train (b) – V’(b)) x i

The Final Design Performance System : To solve the given performance task by using the learned target function(s). It takes an instance of a new problem (new game) as input and a trace of its solution (game history) as output. Critic : To take as input the history or trace of the game and produce as output a set of training examples of the target function.

The Final Design Generalizer : To take as input the training examples and produce an output hypothesis that is its estimate of the target function. It generalizes from the specific training examples, hypothesizing a general function that covers these examples and other cases beyond the training examples.

The Final Design Experiment Generator : To take as input the current hypothesis (currently learned function) and outputs a new problem (i.e., initial board state) for Performance System to explore. Its role is to pick new practice problems that will maximize the learning rate of the overall system.

The Final Design Experiment Generator New problem (initial game board) Hypothesis Training examples Solution trace (game history) Figure 1.1 Final design of the checkers learning program Performance System Critic Generalizer { <b 1 ,V train (b 1 )> , <b 2 ,V train (b 2 )> …}

Choices in designing the checkers learning problem Linear programming Polynomial Linear function of six features Table of correct moves Games against self Games against experts Determine Type of Training Experience Determine Target Function Determine Representation of Learned Function Completed Design Determine Learning Algorithm … … … … Board  move Board  value Artificial neural network Gradient descent

Issues in Machine Learning What algorithms exist for learning general target functions from specific training examples ? How does the number of training examples influence accuracy ? When and how can prior knowledge held by the learner guide the process of generalizing from examples ?

Issues in Machine Learning What is the best strategy for choosing a useful next training experience, and how does the choice of this strategy alter the complexity of the learning problem ? What is the best way to reduce the learning task to one or more function approximation problems ? How can the learner automatically alter its representation to improve its ability to represent and learn the target function ?

Machine Learning Fall, 2007 Course Information

Recommended

More Related Content

What's hot (19)

Similar to Machine Learning Fall, 2007 Course Information (20)

More from butest (20)

Machine Learning Fall, 2007 Course Information