CSDS 440 Machine learning

Random Variable (R.V.)

A variable that refers to an uncertain fact

– Has a domain that can be discrete or continuous

For each value (or set of values), we can

specify a degree of belief that shows how

much we believe the stated fact---this is the

probability associated with the fact

– Denoted Pr(.)

Atomic Event

If the state of the world is described by n r.v.’s

and we assign values to all of them, this

defines an atomic event

What are the characteristics of atomic events?

Atomic events are mutually exclusive and

exhaustive

– At most one can be the true state of affairs

– The true state of affairs must be one of them

An “event” is a collection of atomic events

– Example: the event {x=2} is the collection of atomic

events {(x=2, y=1), (x=2, y=2), (x=2, y=3),…}

Sample Space

The “sample space” is the collection of all

possible atomic events ( )

Axioms of Probability

Probability Density Function

A function that maps every value of an r.v. to a

probability is called a probability density

function (p.d.f.)

Joint PDF

Conditional Probability

Marginalization

Conditioning

Bayes’ Rule

Bayes’ Rule therefore allows us to reason

backwards over uncertain events---

fundamental to learning

Statistical Independence

Conditional Independence

I.I.D. random variables

A collection of r.v.’s is I.I.D. if they are

– independent and

– identically distributed (the density functions are

the same)

Expectation of r.v.

Variance of r.v.

What is a “machine” in the context of ML?

“Machine”=autonomous system

– No (or limited) human intervention

– Robots, software agents, etc.

What is “learning” in the context of ML?

“Learning denotes changes in the

system that enable the system to

do the same task more effectively

the next time.”

—Herbert Simon (1916-2001)

– Also, how to do related tasks

more effectively

A Specification for a Learning System

Given:

– Learning task (e.g. learn to play chess)

– Task examples E (e.g. games played/sequences of moves until win/loss)

– Performance measure P (e.g. games won/lost)

Do: Produce a concept that is good with

respect to P on all examples of the task

– Measured by proxy on E
(e.g. concept: Some function mapping current state of game to

suitable moves to play)

Identify and describe the “Two Phases of Learning”

“Learning” or “Training” phase

– Reason about the examples E

– Formulate a concept that does well w.r.t. P on E

– Could also use any prior knowledge

“Evaluation” or “Testing” phase

– Use learned concept on future, novel examples

Online vs Batch (Offline) Learning

Batch/Offline Learning: one learning phase,

with a large set of examples, followed by a

testing phase

Online learning: Examples arrive one at a time

(or in small groups); learning and evaluation

phases are iterated

Inductive Generalization

Specific → general

Reasoning from specific examples to a general case

Deduction/ deductive reasoning

General → specific

A type of reasoning that moves from general principles to specific conclusions

Abduction

Most likely cause

A type of reasoning that infers the most likely cause or explanation for a set of observations

Target Concept

The unknown underlying concept or rule that solves the learning task

• E.g., “has-fur” and “long-teeth” and “looks-scary” → “lion”

Typically, P will be a measure of difference

between the learner’s concept and the target

concept, with respect to E

Hypothesis Space

The set of all general concepts or candidate rules that the learning system will consider

Difference between memorization and learning

Memorization involves storing specific training examples, whereas learning involves generalizing to unseen instances

No “Tabula Rasa” Learning

The principle that a learning algorithm cannot learn effectively from a completely blank slate without prior constraints or assumptions

Problems with an unrestricted hypothesis space

It contains overly complex concepts, includes memorization concepts indistinguishable from the target, and may be too big to search feasibly

Inductive Bias

The set of assumptions used by a learning system to restrict its hypothesis space

Supervised learning

A learning setting where examples E are annotated with target concept outputs by an oracle, and the system must find a matching concept

Oracle

An oracle is an idealized, hypothetical entity (or "black box") that can instantly and perfectly answer any question or solve any problem put to it, regardless of how computationally hard or resource-intensive it is.

(A theoretical machine with unlimited computational power, perfect knowledge, or infinite resources)

Feature vector representation

Examples are represented as attribute-value pairs (features = attributes) with a fixed number of attributes, written as an n-by-m matrix where each row is an example and each column is an attribute.

Types of features

Machine learning features can be discrete/nominal (unordered categories, e.g. color), continuous (e.g. height), discrete/ordered (ordered categories, e.g. size: small/medium/large), or hierarchical (nested categories, e.g. shape: closed vs. continuous, with closed further split into polygon vs. circle/ellipse, and polygon further split into square/triangle).

Feature space

Examples can be thought of as points embedded in an n-dimensional vector space, where each dimension corresponds to a feature (e.g. size, shape, weight).

Other example representations

Besides feature vectors, examples can also be represented relationally, as multiple instances, sequentially, or with multiple views.

Binary classification problem

The simplest supervised learning problem, where a target concept assigns one of two labels ("positive" or "negative") -- the class label -- to every example. Can be extended to multiclass, regression, and multi-label problems.

The learning problem

Given a binary classification problem, the goal is to produce a "classifier" (concept) that assigns a label to a new, unseen example.

Binary classifier concept geometry

A binary classifier can be thought of geometrically as a union of N-dimensional volume(s) in feature space (possibly disjoint), separated from the rest of the space by a decision boundary (separating surface).

What is a decision tree?

A tree is a directed acyclic graph where each node has at most one parent. In a decision tree, internal nodes are tests on attributes, and leaves are class labels.

Classification with a decision tree

Starting at the root, check each attribute test to identify a path through the tree, following it until reaching a leaf, then assign the class label found at that leaf.

Decision tree induction (recursive partitioning)

Given a set of examples, the algorithm chooses an attribute test at each step to partition the examples into disjoint groups, then recursively repeats on each partition until a partition contains only one class (a pure node) or the algorithm runs out of attributes. If no attribute test looks good, the algorithm returns.

Choosing an attribute (decision trees)

When building a decision tree, the attribute chosen to test first should ideally be the one that is "most predictive" of the class label -- i.e., the one that gives the "most information" about what the label should be. This idea is captured by entropy.

Entropy (intuitive definition)

A measure of the "information content" in a distribution. If a random variable X has n values with distribution p(X=x), the shortest lossless description takes -log2(p(x)) bits for each x, so entropy is the expected length of the shortest lossless description of the random variable (Shannon's Source Coding Theorem, 1948).

Information gain (concept)

The reduction in entropy of the class label that results from partitioning the data using a given attribute X. Choosing the attribute that maximizes information gain identifies the most useful attribute to test.

Example decision tree logic (Lion classifier)

Test Long-Teeth: if False, classify Not-Lion. If True, test Scary: if False, classify Not-Lion. If True, test Has-fur: if False, classify Not-Lion; if True, classify Lion.