Machine Learning Notes

These are OCR-assisted transcriptions of handwritten CS 4641 machine learning notes. The scan metadata is from 2026, but the dates visible in the notes begin on 2016/05/25; later pages show 2016/05/26, 2016/05/31, 2016/06/02, and 2016/06/09. One page appears to show 2016/05/24, but the first numbered page in this packet is dated 2016/05/25.

I kept the page images next to the transcription so the original notation remains inspectable. When the handwriting was not reliable, I marked the text with [unclear].

Page 1: Decision Trees

Date read from the page: 2016/05/25.

The notes open with three classes of machine learning problems:

• supervised learning: a set of data and labels allows an inductive bias;
• unsupervised learning: description, summarization, and deciding what to summarize or split on;
• reinforcement learning: learn from delayed reward, such as deciding whether a tic-tac-toe game was good at each step or only at the end.

Supervised learning is divided into classification and regression. Classification separates instances into classes. Regression predicts a continuous output, e.g. y = mx + b.

The simple ML pipeline is:

flowchart LR
    A["Training set"] --> B["Learning model"]
    B --> C["Predictions on training set"]
    C --> D["Analyze results"]

A decision tree is represented as:

• circles: nodes or attributes;
• edges: values;
• squares/leaves: decisions or outputs.

For a restaurant example, the input is the feature vector for a restaurant instance and the output is something like yes, no, or enter.

Construction algorithm:

1. Pick the best attribute.
2. Ask the question.
3. Follow the path.
4. Go to 1 until an answer is reached.

Decision trees can express Boolean functions. The notes sketch trees for A AND B, A OR B, and A XOR B. XOR requires a fuller tree.

A AND B

        A
      T/ \F
      B   F
    T/ \F
    T   F

A OR B

        A
      T/ \F
      T   B
        T/ \F
        T   F

A XOR B

        A
      T/ \F
      B   B
    T/ \F T/ \F
    F   T T   F

For n-XOR, the note says the tree is exponential: O(2^n). The total number of Boolean outputs is written as O(2^(2^n)).

Page 2: ID3 And Entropy

The decision-tree learner is labeled ID3: Iterative Dichotomizer 3. The loop is:

flowchart TD
    A["Choose best attribute A"] --> B["Assign A as decision node"]
    B --> C["For each value of A, create a descendant"]
    C --> D["Sort training examples to leaves"]
    D --> E{"Examples perfectly classified?"}
    E -- "yes" --> F["Stop"]
    E -- "no" --> G["Iterate over leaves and repeat"]
    G --> A

The best attribute selection is written as information gain:

Here S is the training set and A is the current attribute. Entropy is noted as a measure of randomness:

For continuous attributes, the notes say to look at data to get ranges, e.g. split on 20 <= age <= 30. The notes ask whether attributes can repeat along a path; for continuous attributes, the answer is yes.

Stopping and overfitting notes:

• noise can cause an infinite loop;
• prune leaves;
• remove nodes that overfit to noise and employ a voting mechanism;
• vote over leaves.

ID3 bias:

• restriction bias: the hypothesis space is discrete functions;
• preference bias: choose a hypothesis in the space, prefer good splits near the top, prefer correct over incorrect, prefer shorter trees.

For regression, the note says information gain is not directly usable; consider variance and output averages instead.

Page 3: Perceptrons And Neural Networks

Date read from the page: 2016/05/25.

An artificial neuron is introduced as a perceptron:

flowchart LR
    X1["x1"] -- "w1" --> S["sum"]
    X2["x2"] -- "w2" --> S
    X3["x3"] -- "w3" --> S
    S --> T{"sum >= theta?"}
    T -- "yes" --> Y1["y = 1"]
    T -- "no" --> Y0["y = 0"]

The rule is:

The page asks: how powerful is a perceptron? With weights and thresholds, a linear classifier can express AND, OR, and NOT:

Function    w1     w2     theta
AND         1/2    1/2    3/4
OR          1/2    1/2    1/4
NOT        -1      --     0

A single perceptron cannot represent XOR:

x1  x2  XOR
1   1   F
1   0   T
0   1   T
0   0   F

The note says perceptrons can express AND, OR, and NOT, so a network of perceptrons can represent Boolean functions. The warning is that, with enough nodes, there is danger of overfitting.

Restriction bias:

• perceptron: linear planes;
• sigmoid neural network: much less restriction;
• Boolean: network of perceptrons;
• continuous: connected neurons with one hidden layer;
• arbitrary: stitch together with two hidden layers, minimum [unclear].

Preference bias depends on the algorithm and initial weights: small random weights, low complexity, and local minima. Neural networks are hard to understand and parameters are hard to tune, but they are useful when the representation problem is complex.

Page 4: Perceptron Training And Gradient Descent

The perceptron training data is:

where y is the target/label, x is the input, and the model output is either 1 or 0.

The perceptron rule is written using a thresholded prediction hat{y}:

The note rewrites the threshold as a bias term by setting x_0 = 1 and w_0 = -theta:

Update rule:

The algorithm repeats while error is greater than zero:

1. update weights;
2. recompute the prediction;
3. correct the sign/direction of w_i depending on whether the model under- or over-predicted.

The theorem is stated: if the data is linearly separable, then the perceptron rule will find the separating plane in a finite number of steps.

If the data is not linearly separable, the page introduces gradient descent:

Perceptron output is thresholded, while gradient descent uses a non-thresholded output and minimizes:

The derived update is:

Page 5: Comparing Learning Rules

The page asks why gradient descent works. If the error slope at w_1 is positive, move weights down; if the slope at w_2 is negative, move weights up. The notes then compare perceptron learning and gradient descent:

The page states:

• perceptron rule: finite convergence;
• gradient descent: robust to non-linearly separable data.

The thresholded output is not differentiable:

hard threshold

 output
   1 |      ______
     |     |
   0 |_____|
          a

The fix is a soft threshold, such as a sigmoid:

As a -> -infinity, sigma(a) -> 0; as a -> +infinity, sigma(a) -> 1. The derivative is written:

The neural-network note is that differentiability lets us figure out the effect of all weights on the output. Backpropagation efficiently computes all partial derivatives, so any differentiable function can be used. The page also warns that gradient descent can get stuck in local optima; more nodes and larger weights increase complexity and overfitting risk.

Page 6: Feedforward Networks, Recurrent Networks, Autoencoders

Date read from the page: [2016/05/24?].

The page contrasts perceptrons and sigmoid neural networks. A feedforward neural network is drawn as input nodes, hidden nodes, and a single output:

flowchart LR
    X1["x1"] --> H1["h1"]
    X1 --> H2["h2"]
    X2["x2"] --> H1
    X2 --> H2
    X3["x3"] --> H1
    X3 --> H2
    H1 --> Y["y"]
    H2 --> Y

The note says this works when there is a lot of data and time to train.

Recurrent neural networks are drawn as a unit with feedback, then “unfolded” across time. The note says this allows modeling of varying-sized data, like sentences.

Autoencoders are drawn as a network that reproduces its input:

flowchart LR
    X["input x"] --> E["encoder"]
    E --> Z["compact representation"]
    Z --> D["decoder"]
    D --> XH["reproduced input x_hat"]

The loss is written as a reconstruction loss:

The note says the loss is minimized when x^(n) = x_hat^(n), and that an autoencoder can find a more compact representation of the inputs.

Page 7: Support Vector Machines

The SVM section starts by asking which separating line is right. The training data is incomplete, so the model must be flexible for new data and avoid overfitting.

Goal:

1. find a plane that maximizes the margin;
2. classify all points correctly.

Assumption: the data is linearly separable.

The separating plane is:

with margin boundaries:

and

The circled points on the margin are labeled “support vectors”.

       + + +
          /
---------/---------  w^T x + b = 1
        /
-------/-----------  w^T x + b = 0
      /
-----/-------------  w^T x + b = -1
   - -

margin = distance between the support planes

The line equation is generalized:

and in more dimensions:

The goal becomes: find a plane w^T x + b = 0 satisfying the classification and margin constraints.

Page 8: SVM Optimization, Soft Margins, Kernels

The distance from a point to the plane is derived as:

given the scaling condition:

The optimization is:

which is noted as solvable with a quadratic programming problem. In the dual form, the page writes weights as:

The notes say most alpha values are zero; only the margin points matter. These are the support vectors.

For non-linearly separable data, the page introduces a soft-margin SVM:

and minimization:

If the data is too non-linearly separable, try mapping to a higher-dimensional space. The sketch says to “pull out” the center and cut off segments in 3D with a linear classifier.

Page 9: Kernel Trick And Instance-Based Learning

The kernel section transforms x into 3D:

The dot product in transformed space becomes:

This is labeled a polynomial kernel. The page also mentions an exponential/RBF-style kernel:

The note says this simulates a kernel in infinite-dimensional space because it is expandable with a Taylor series, while still using a linear classifier.

Bias notes:

• minimize misclassification from generalization error;
• preference bias is maximum margin;
• restriction bias is open to the kernel used.

Instance-based learning is introduced as fitting only the training data. A lookup table can return the exact training output but gives the wrong answer away from stored instances.

For k-nearest neighbors:

flowchart TD
    A["Query q in X"] --> B["Compute distances d(q, x_i)"]
    B --> C["Select k smallest distances"]
    C --> D{"Task"}
    D -- "classification" --> E["Return majority vote"]
    D -- "regression" --> F["Return weighted average"]

The notes define the model as looking at the k nearest neighbors and using a voting mechanism. Given:

with distance d(x^(n), x^(m)), choose K neighbors and classify by vote or regress by weighted average.

Page 10: Domain Knowledge, k-NN, Bagging

Domain knowledge appears as choices of distance and k, with cross-validation used to choose k. The page notes k-NN is used in spiral sets.

Bias:

• preference bias: locality depends on distance;
• features matter equally, as reflected in the neighbor distance.

Curse of dimensionality:

• to fill the same amount of space in higher dimensions, accuracy decreases;
• autoencoders can help;
• dimension equals features;
• dimensions must be chosen properly.

k-NN notes:

• k = NN: nearest neighbors;
• k = N: all data points;
• using mean learns nothing;
• weighted mean/average can be used;
• very easy to incorporate domain knowledge by defining the distance function;
• very fast for small datasets;
• easy to implement;
• lazy learner;
• lazy learning means the model is learned when classification is requested;
• very time consuming with large datasets.

Ensemble learning combines multiple learners. The note names bagging and boosting. Simple rules do not work on large datasets, so the framework is:

1. learn simple rules over small subsets of data;
2. combine them.

Page 11: Bagging And Boosting

Bagging framework:

1. pick uniformly random elements;
2. average them.

The example is fitting third-order polynomials on random subsets, then averaging the curves. This reduces overfitting by averaging.

Bagging is “aggregate bagging” and helps reduce overfitting. It assumes an unweighted average. The note sketches the zero-order polynomial case as a horizontal average across N disjoint sets.

Boosting combines simpler learners and “boosts” performance:

1. learn over subsets, especially the hardest examples;
2. combine by a mean or weighted mean.

The hardest-example determination involves error:

The learner’s weight is related to how often it occurs or how well it performs. Weak learners classify better than random chance:

The page includes a small table of hypotheses h1, h2, and h3 over examples x1 through x4, and a second table that splits examples into “good” and “bad” proportions.

Page 12: AdaBoost

AdaBoost is described as weak-learner agnostic and able to use any learner.

Given:

For t = 1, ..., T:

1. construct distribution D_t;
2. find a weak classifier h_t(x) with small error;
3. output:

The error is:

The sketch shows decision stumps: axis-aligned thresholds are selected to minimize error. If a point is on the correct side, reduce its weight; otherwise increase its weight.

The weight update is written in the form:

with normalization Z_t. The note says:

The overfitting sketch compares training error and cross-validation error. AdaBoost can keep reducing training error, while the relevant curve is cross-validation error.

Page 13: Regression And Linear Algebra

Date read from the page: 2016/05/31.

The page starts with a recap of AdaBoost:

• combine weak learners;
• agnostic learning;
• connection to max-margin;
• cross-validation error is a simulation of testing error.

Regression deals with continuous outputs.

Linear regression:

Polynomial regression:

The order is chosen using cross-validation.

The page asks how to fit the model and lists:

1. linear algebra;
2. calculus;
3. bias-variance decomposition.

For linear algebra, set x_0 = 1. In matrix form:

with an error vector:

Multiplying by X^T gives:

and therefore:

The note says this is bad when the dimension of X is large because the inverse is expensive: O(N^3).

Page 14: Regression, SGD, Bias-Variance

The calculus method uses:

and:

Batch gradient descent:

It requires full recomputation.

Stochastic gradient descent is usable with online learning:

and updates from a single data point. Mini-batch gradient descent compiles a batch and then adjusts the model.

The notes say gradient descent requires precise setting of the learning parameter eta; linear algebra does not need eta.

Bias-variance decomposition:

The model is w_hat; the real model is w*.

Variance is error from small fluctuations in the data. High variance leads to overfitting. Bias is error from assumptions of the model. High bias leads to underfitting. The notes say increasing bias a little can decrease variance a lot, lowering expected error; the human brain prefers high bias and low variance.

Page 15: Information Theory

The information-theory page asks:

How much information does y get from x_0, x_1, x_2?

The element of surprise is illustrated with fair and biased coins. Entropy is the minimum number of yes/no questions.

The notes compare message encodings:

Case 1: four equally likely events

A 25% -> 00
B 25% -> 01
C 25% -> 10
D 25% -> 11

Expected message size = 2 bits

Case 2: one common event

A 50.0% -> 0
B 12.5% -> 110
C 12.5% -> 111
D 12.5% -> 10

Expected message size = 1.75 bits

Information properties:

For independent events:

The information of an event is:

Total information is:

The page notes: in ML, entropy is a measure of randomness and uncertainty.

Page 16: Entropy, Mutual Information, KL Divergence

Entropy:

Joint entropy:

Conditional entropy:

If X and Y are independent, then H(Y|X) = H(Y).

Mutual information is the reduction in uncertainty of Y when knowledge of X is known. The page points out this is found in the decision-tree information gain:

Relative entropy:

This is labeled KL divergence and described as the difference between two distributions.

The page has a short biology note: evolution is a non-random process involving random mutations. The phrase “max-margin property” appears at the bottom.

Page 17: Computational Learning Theory

Date read from the page: 2016/06/02.

The central question is: how much data is needed to successfully learn?

Two costs are named:

• computational cost: time and space to learn;
• sample complexity: amount of data needed.

Version spaces:

• true hypothesis: c in H;
• candidate hypothesis: h in H;
• training data: S subset X, pairs;
• c(x) for all x in S.

A consistent learner satisfies:

The version space is:

The example uses two Boolean features:

Training data:

x1  x2  h(x)
0   0   0
1   0   1

Target concept c(x):

x1  x2  c(x)
0   0   0
0   1   1
1   0   1
1   1   0

The notes list a hypothesis set with x1, not x1, x2, not x2, T, F, OR, AND, XOR, and EQUIV. The version space for the partial training set is written as {x1, OR, XOR}.

Training error is the fraction of training examples misclassified by h. True error is the fraction of examples that would be misclassified on a sample from the distribution:

The page defines symbols:

• C: concept goal;
• L: learner;
• H: hypothesis space;
• D: distribution over X;
• 0 <= epsilon <= 1/2: error goal;
• 0 <= delta <= 1/2: uncertainty goal.

Page 18: PAC Learning And Haussler Bound

PAC means probably approximately correct. A concept C is PAC-learnable by learner L over hypothesis space H if, with probability at least 1 - delta, the learner outputs h in H where error(h) <= epsilon, in time and space polynomial in:

epsilon-exhausted:

if every h in VS(S) has error less than or equal to epsilon.

Haussler theorem notes:

• bound the true error for a concept class;
• cut down the version space until it is epsilon-exhausted;
• for a finite hypothesis class:

The page asks what happens when |H| = infinity. Examples of infinite hypothesis spaces include:

• linear hyperplanes;
• decision trees with continuous attributes;
• artificial neural networks with weights in R.

The note says the finite bound does not work exactly when H is infinite, such as linear regression where the set of lines is infinite.

Page 19: VC Dimension

The notes define VC dimension as:

What is the largest set of inputs that the hypothesis class can label correctly in all possible ways?

It is marked as equivalent to “shatter” and related to true parameters.

For X in R, intervals have examples:

• VC >= 1: yes;
• VC >= 2: yes;
• VC >= 3: [unclear sketch].

For a decision tree with discrete structure:

• syntactically infinite;
• semantically finite.

Example:

and a threshold hypothesis class:

There are redundant syntactic trees or thresholds because different syntactic choices can have the same semantic labeling on the finite domain.

Page 20: VC Dimension Of Linear Separators

For linear separators in R^2:

The page states:

VC >= 1?  Yes
VC >= 2?  Yes
VC >= 3?  Yes
VC >= 4?  No

So the linear separator VC dimension is 3. More generally:

Dimension D     VC dimension
interval        2
2D              3
3D              4
...
d               d + 1

Sample-complexity notes:

For finite H:

For infinite H, the bound uses VC dimension:

Example: for X in R^2, the class of convex polygons that return true when x is inside or on the polygon has infinite VC dimension, because all points can be shattered. The page also asks about the VC dimension for circles centered at the origin.

Page 21: Bayesian Learning

The page bridges computational learning theory to Bayesian learning:

Bayes theorem is introduced through Thomas Bayes and Richard Price:

Bayesian learning:

Learn the best hypothesis given data and domain knowledge.

The best hypothesis is the most probable one:

and:

The terms are labeled:

• P(D|h): data given hypothesis;
• P(h): prior knowledge over h, induction bias;
• P(D): prior on data.

The page has a disease-test example:

• prior: P(X) = 0.008;
• test returns correct positive: 98%;
• test returns correct negative: 97%.

The important marginal/probability note says: priors matter.

Page 22: MAP, Maximum Likelihood, Least Squares

For each h in H, calculate:

because P(D) is ignored as a constant when maximizing.

Maximum a posteriori:

Maximum likelihood:

Example data:

with:

and Gaussian independent noise:

The derivation shows that maximum likelihood under Gaussian noise leads to least squares:

The page notes this recovers the least-squares result from the linear algebra section.

Page 23: MDL And Bayes-Optimal Classification

The top of the page connects MAP to minimum description length:

and then:

Interpretation:

• -\log_2 P(D|h): length of h fitting the data, or the measure of errors made;
• -\log_2 P(h): size of h, which prefers smaller models and acts as inductive bias;
• minimize both error and size of h.

The note says that for information theory, an event with probability p has length about -log p.

For artificial neural networks, as the weights grow, the number of bits grows, so the size of h grows.

Bayesian classification example:

h(x)   label   P(h | D)
h1       +       0.4
h2       -       0.3
h3       -       0.3

The best hypothesis is h1, but the best label is - because the negative hypotheses have total posterior mass 0.6.

Best label:

Bayes-optimal classifier note:

No other learner using the same H and the same prior knowledge can outperform this method on average.

Page 24: Joint Probability And Belief Networks

Joint probability table:

Storm  Lightning  P(S,L)
T      T           0.25
T      F           0.40
F      T           0.05
F      F           0.30

Marginalization:

Conditional probability:

Three-variable table:

Storm  Lightning  Thunder  P(S,L,Th)
T      T          T        0.20
T      F          T        0.04
F      T          T        0.04
T      T          F        0.05
F      T          F        0.01

Independence:

Conditional independence:

X is conditionally independent of Y given Z if:

The belief network for weather is:

flowchart TD
    S["storm"] --> L["lightning"]
    L --> T["thunder"]

with terms such as P(s), P(l|s), P(l|not s), P(th|l), and P(th|not l).

Page 25: Directed Graphical Models And Naive Bayes

The page gives a directed acyclic graph:

flowchart TD
    A["A"] --> C["C"]
    B["B"] --> C
    B --> D["D"]
    C --> D
    C --> E["E"]
    D --> E

The note says the graph can form generative models. Sample in order:

a ~ P(A)
b ~ P(B)
c ~ P(C | A, B)
d ~ P(D | B, C)
e ~ P(E | C, D)

The joint distribution factorizes as:

The page notes D is conditionally independent of A given B and C.

Inference example:

box 1: G G
       G Y

box 2: B B
       B G

Process:

1. pick box uniformly;
2. draw ball 1 without replacement;
3. draw ball 2.

The inference line computes:

At the bottom, spam classification is represented as a Naive Bayes network:

flowchart TD
    S["Spam?"] --> P["Pill"]
    S --> F["Free"]
    S --> Z["Zvi"]

Assumption: all attributes are independent given the label. This is the “naive” assumption in Naive Bayes.

Page 26: Naive Bayes

Date read from the page: 2016/06/09.

Naive Bayes is written as a belief network:

flowchart TD
    S["Spam?"] --> Free["free"]
    S --> Pill["pill"]
    S --> Zvi["zvi"]

The assumption is:

“free” is independent of “pill” given spam.

Example table:

Pill  Free  Zvi  Spam?
T     T     T    F
T     T     F    T
T     F     T    T

Assume attributes are conditionally independent given Spam?.

The scoring equation is:

and by the Naive Bayes assumption:

The maximum a posteriori classifier is:

The page notes N is a count function:

and:

Benefits:

• few attributes;
• tractable;
• generative;
• can generate examples of spam emails;
• a way to visualize data;
• used by Google.

Downside:

• strong conditional-independence assumption.

Diagram Notes

Mermaid is already vendored by this site through /static/mermaid-v11.14.0/mermaid.css and /static/mermaid-v11.14.0/mermaid.min.js, and initialized by /static/js/main.js. The diagrams above reuse that local integration.