A Story of Machine Learning

Syllabus:
Decision Tree 18 – 18.3.4
Evaluation 18.4
Model Selection 18.4.1
Regularization 18.4.3
Theory 18.5.0
Regression 18.6 – 18.6.2
Classification 18.6.3 – 18.6.4
Neural Network 18.7 – 18.7.4 (exclude exotic varieties of NN in my slides)
Non-parametric models 18.8 – 18.8.4
SVM basics 18.5
Clustering basics
…

4/2/24 [Link] 1
mation-in-neural-networks-
INFORMATION THEORETIC ENTROPY:

If one were to transmit sequences comprising the 4 characters 'A', 'B', 'C', and 'D', a transmitted message
might be 'ABADDCAB'. Information theory gives a way to calculate the smallest possible amount of
information that will convey this.

If all 4 letters are equally likely (25%) in a text, one can't do better (over a binary channel) than to have 2 bits
encoding for each letter: 'A' might code as '00', 'B' as '01', 'C' as '10', and 'D' as '11‘, i.e., 2 bits per letter.

If 'A' occurs with 70% probability, 'B' with 26%, and 'C' and 'D' with 2% each, and we are allowed to assign
variable length codes, 'A' would be coded as '0' (one bit), 'B' as '10', and 'C' and 'D' as '110' and '111'. It is easy
to see that 70% of the time only one bit needs to be sent, 26% of the time two bits, and only 4% of the time 3
bits. On an average, fewer than 2 bits will be required since the entropy is lower (owing to the high prevalence
of 'A' followed by 'B' – together 96% of characters) than that with equal probability. Overhead of transmitting
the encoding of letters is additional but minimal.

The calculation of the sum of weighted log probabilities measures and captures this effect.

[Link]

4/2/24 [Link] 2
 Decision Tree: Choice of attribute at each level

Entropy of Target Examples (current level):

H(Goal) = P(vk) ∑k log2 (1/P(vk)), k may be {True, False}

Say, 8 positive examples, and 4 negative examples

H(Goal) = B(8/12)= -[(8/12) log2 (12/8) + (4/12) log2 (12/4)]

Now, for attribute A, calculate entropy:

but say, attribute A has three values {some, full, none}
Say, vs, vf, vn are number of examples for these three types, and
(ps, ns) are positive and negative examples for the Target-label attribute (to go to restaurant or
not) corresponding to A=some
such that ps + ns = vs , and so are for (pf, nf) , (pn, nn)

4/2/24 3
 H(goal) or entropy before choosing attributes

Attribute s

Entropy for each value vs

Aggregate entropy= weighted sum for all attribute values

Difference is Information Gain

4/2/24 4
 Decision Tree: Choice of attribute at each level

Calculate Entropy for attribute A:

Say, attribute A has three values {some, full, none}
and, vs, vf, vn are number of examples for these three types, with
(ps, ns) are positive and negative examples for the Target attribute (to go to restaurant
or not)
such that ps + ns = vs , and so are (pf, nf) , (pn, nn)

Weighted Entropy, R(A) = -(vs/m)[(ps/vs)log2(ps/vs)+

(ns/vs)log2(ns/vs)]
- (vf/m)[(pf/vf)log2(ps/vs)+ (nf/vf)log2(nf/vf)]
- the same for (A=“none”)

m = vs + vf + vn

4/2/24 5
 Decision Tree: Choice of attribute at each level

Now, for choosing attribute A, information gain will be

Gain(A) = H(Goal) – R(A)

Compute this gain for each attribute at the current node of the
decision tree,

Best attribute provides highest information gain (or lowest

entropy relative to Goal-entropy)

4/2/24 [Link] 6
 Decision Tree:
Choice of attribute at the root node in the Restaurant example in book
H

H(Goal), for 6 pos and 6 neg examples in total, =1 bit

Gain(Patrons) = 1 – [(2/12)B(0/2) + (4/12)B(4/4) + (6/12)B(2/6)]

= 0.541 bit

Gain(Type) = 1 – [(2/12)B(1/2) + (2/12)B(1/2) + (4/12)B(2/4) +

(4/12)B(2/4)] = 0 bit

B(q) is the entropy for a Boolean variable, with q=positives/total,

B(q) = qlog2(1/q) + (1-q)log2(1/(1-q))

4/2/24 7
 MISCELLENEOUS: Machine Learning has two stages:
Do not forget

Stage 1: Training, with “known” data (in supervised learning:

input and known labels to generate model)

Stage 2: Inferencing (deploying trained ML model to its task:

predict the unknown label given input attribute values)

Stage 2.1: Validating with “unknown” data to quantify how good

the trained model is

4/2/24 8
 MISCELLENEOUS: Evaluation of Algorithm

Training set = Sample of real world

Stationarity assumption: Real world has the same distribution as

that of training data

Non-stationarity: data is changing over time, what you learned

before is no longer useful

Independent and Identically distributed (iid): Each datum,

training or in real world, has equal probability of appearing

Non-iid: Some data are more important than other

4/2/24 9
 MISCELLENEOUS: Evaluation of Algorithm
Cross-validation: divide data set into two groups - training and
validation,
for computing the rate of successful classification of test data.

Measurement of validation: error rate on the validation set

An ML algorithm has many parameters: e.g., hypothesis (order of

polynomial), learning rate, etc.

Fine-tune those parameters using a WRAPPER algorithm, by

repeated validation:
need to repeat cross-validation by randomly splitting the available
data set.

4/2/24 10
 MISCELLENEOUS: Evaluation of Algorithm

k-fold Cross validation: 1/k part of data set is a validation set,

repeat x-number of times by randomly splitting 1/k

k=n, for data set size n, is leave-one-out cross-validation

Peaking: After k-fold cross-validation, ML algorithm may overfit

known training data (if validation is over part of the training set) ,
but may not be as good for real life use (note: that may mean iid is
not true)

ML competitions hold out real “test data,” but still groups may
"cheat" by repeatedly submitting fine-tuned code.

4/2/24 11
 MISCELLENEOUS: Hypothesis Selection

Finding best hypothesis: two step process

1) Find best hypothesis space

2) Optimization to find the best hypothesis

E.g., 1) Which order of polynomial, y=ax+b, or, y = ax2 +bx +c?

2) Find a, b, c parameters’ values

4/2/24 12
 REGULARIZATION
Optimization function may embed simplicity of the model, or any
other relevant knowledge

E.g., Cost(h) = Error + λ*(complexity)

Cost(h) = (y – [… ax +b])2 + λ*(a penalty function to minimize),
e.g., Cost(h) = (y – [axn +bxn-1 +cxn-2 +…])2 + λ*(a+b+..), the
parameter themselves
[actually, abs(a) + abs(b) + …, WHY?]
• h is the hypothesis, which is the polynomial
• Cost(h) is the error to be minimized
• Polynomial may NOW be of arbitrary order
• λ is tunable regularization constant or hyper-parameter
• (abs(a)+abs(b)+…) regularization term, lower the better

h* = argmin{a,b, …} Cost(h), is to find parameters a, b, …

4/2/24 13
 Computational Learning Theory

PAC learning – quality of an algorithm:

• Any seriously wrong hypothesis may be quickly found out with

only a few examples

• Conversely, any hypothesis that survives training after many

examples is likely to be correct

Probably Approximately Correct (PAC) learning algorithm

4/2/24 14
 Computational Learning Theory

CLT provides a measure on PAC learning

#examples versus accuracy?

If you want ε–accurate you need f(ε) number of samples, as CLT

tries to find the function f(.)

4/2/24 15
 Problem II: Linear Regression
Output is Continuous valued

4/2/24 16
 Linear Regression
(Still supervised learning)

Regression: Predicting a continuous value (e.g., y) out of input x values

Least Square Error or L2-norm minimization

Linear model, y = mx +b: Has closed form solution Eq 18.3

4/2/24 17
 Linear Regression

Loss(hw) = ∑j (yj – (w1xj + w0))2 , j goes over N data points

Take partial derivatives over wi and equate each to zero, i runs over parameters.
wi’s are parameters that the algorithm learns.

Analytical solution (by equating partial derivatives to 0):

w1 = [N(∑jxjyj) – (∑jxj)(∑jyj)] / [N(∑jxj2) - (∑jxj)2 ]

w0 = [∑jyj – w1(∑jxj)]] / N
for two parameters
4/2/24 18
 Linear Regression

Sometimes no analytical solution is found in closed form (e.g., non-linear regression)

Gradient Descent gets iteratively closer to the solution:

determine the direction in each iteration and update w parameters above
step-size may be updated in each iteration, a constant, or a fixed schedule

Note: "direction" gets determined by the sign of error: +ve or -ve

(useful in understanding classifier later)

4/2/24 19
 Multivariate Linear Regression

Hypothesis is: y = w0 +w1x1 +w2x2 +..., for x1, x2, ...xn variables in n-dimension

Closed form solution is a matrix formulation with partial differential equations equated to 0

Gradient descent is:

w ß start with arbitrary point in the parameter space (w vector); Optimizes on parameter-space
loop until convergence
for each parameter wi in w do
wi ß wi – α* ∂/∂wi (Loss(w) );

α is the step size or learning rate

4/2/24 20
 Multivariate Linear Regression

Hypothesis: y = w0 +w1x1 +w2x2 +..., for x1, x2, ...xn variables

Gradient descent update is:

wi ß wi – α* ∂/∂wi (Loss(w) );

Loss function may be summed over all training examples

For example, with 2 parameters:

w0 ß w0 + α* ∑j(yj – hw(xj)); // sign changes for derivative
w1 ß w1 + α* ∑j(yj – hw(xj))*xj
… for all wi’s

where hw(xj) is the predicted value for y

4/2/24 21
 Multivariate Linear Regression

Loss function may be summed over all training examples

For example, with 2 parameters:

w0 ß w0 – α* ∑j(yj – hw(xj));
w1 ß w1 – α* ∑j(yj – hw(xj))*xj
….
Above update procedure is called batch-gradient descent:
Update each wi going over i’s
For all training samples
……..

Stochastic-gradient descent:
For each training example j
update all wis
....

Typically, one uses a mix of the two: e.g., a fixed batch size

4/2/24 22
 Three nested loops in gradient descent optimization:
Iterations
Parameters
Training data

… in any order

4/2/24 23
 Multivariate Linear Regression

Loss function may be summed over all training examples

For example, with 2 parameters for one variable data (yj = w0 + w1*xj):
w0 ß w0 + α* ∑j(yj – hw(xj));
w1 ß w1 + α* ∑j(yj – hw(xj))*xj

Note, in multi-variate case, element of x is xij

y = w0 +w1x1 +w2x2 +..., for i running over variables or parameters
and,

j running over training examples

Update rule is Eq 18.6

w* = argminw ∑j L2(yj, [Link]), as in L2-norm
or,
wi ß wi + α* ∑j(yj – hwi(xj))*xj , h is the hypothesis or model-formula, e.g. ax+b

4/2/24 24
 Multivariate Linear Regression

Note: some dimensions may be irrelevant or of low importance:

wi ~0 for some xi

Attempt to eliminate irrelevant dimensions or dimensions with low w values:

use a penalty term in error function for "complexity"
Loss(hw) = L2(hw) + λ∑i |wi|

L1-norm (absolute sum) is better for this second term on complexity of the model:
"sparse model": minimizes #of “dimensions” (Fig 18.14 p722)
sometimes called Lasso regrerssion

4/2/24 25
 Problem III: LINEAR CLASSIFIER 18.6.3

4/2/24 26
 Problem III: LINEAR CLASSIFIER 18.6.3

• Predicting y is the objective for regression, but classifiers predicts “type” or “class”

• Target function here is Boolean, y = 1 or 0 (as in Decision tree)

• The objective is to learn a Boolean function such that: hw(x) = 1 or 0:

data point x is in the class or not

• Training problem:
set of (x, y) is given, x are data points and now, y =1 or 0,
find hw(x) that models y

• Test by inferencing:
a data point x is given, predict if it is in the class or not (compute hw(x) )

4/2/24 27
 LINEAR CLASSIFIER 18.6.3
• No longer hw(x) is the line expected to pass through (or close to) the data samples
as in regression,
but to separate or classify them into two sides of the line – in class or out of class

• Model: w0 + w1x1 +w2x2 + ... ≥0, and hw(x) =1 if so, =0 otherwise

• Finding the line is very similar as in regression: optimize for (w0, w1, …)

4/2/24 28
 LINEAR CLASSIFIER 18.6.3

• Rewrite the model: (w0, w1, w2, ...)T * (x0, x1, x2, ...) ≥0, a vector product
where (…) is a column vector, (.)T stands for matrix transpose, and x0 = 1

• Consider two vectors, w= (w0, w1, w2, ...)T and x= (x0, x1, x2, ...)T
• hw(x) = 1 when (w.x)≥0, otherwise hw(x) = 0

• Gradient descent (for linear separator) works as before. It is called:

• Perceptron Learning rule:
• wi ß wi +α*(y - hw(x) ) * xi, 0 ≤ i ≤ n, updates from iteration to iteration

• One can do Batch gradient descent (for-each w, inside loop for-each-datum) or

• Stochastic gradient descent (for-each datum, inside for-each w) here

• Note: y here is also Boolean: 1 or 0 in the "training" set

4/2/24 29
 LINEAR CLASSIFIER 18.6.3

• Training:

• (1) w stays same for correct prediction y= hw(x)

• (2) False negative: y=1, but hw(x) =0, increase wi for each positive?(xi), decrease otherwise

• (3) False positive: y=0, but hw(x) =1, decrease wi for each positive?(xi), increase otherwise

4/2/24 30
 LINEAR CLASSIFIER 18.6.3

• Logistic regression:
use sigmoid hw(x) rather than Boolean function (step function) as abov
hw(x) = Logistic(w.x) = 1 / [1 + e-w.x]

4/2/24 31
 LINEAR CLASSIFIER 18.6.3

• Logistic regression:
use sigmoid hw(x) rather than Boolean function (step function) as above
hw(x) = Logistic(w.x) = 1 / [1 + e-w.x]

• Update rule with above logistic regression model: Eq 18.8 p727

wi ß wi +α*(y - hw(x) ) * hw(x) * (1- hw(x) ) * xi

• Continuous valued hw(x) may be interpreted as probability of being in the class

4/2/24 32
 Problem IV: ARTIFICIAL NEURAL NETWORK Ch 18.7

• Single Perceptron, only a linear classifier, a neuron in the network

1
x1 w0
w1
x2 w2
∑i=0n wixi ∫ 0 or 1

xn wn

4/2/24 33
 ARTIFICIAL NEURAL NETWORK Ch 18.7

• A single layer perceptron network CANNOT "learn" xor function or Boolean sum,
• Fig 18.21 p 730

4/2/24 34
 ARTIFICIAL NEURAL NETWORK Ch 18.7

4/2/24 [Link] 35
 ARTIFICIAL NEURAL NETWORK Ch 18.7

• Layers of perceptrons: Input à Hidden à Hidden à ... à Output classifying layer

• Two essential components: Architecture, and Weights updating algorithm

• Crucial details: Loss function for the algorithm, Activation function

• Perceptron output fed to multiple other perceptrons, Fig 18.19 p728

• Different types of hw(x) may be used as activation function

4/2/24 [Link] 36
 ARTIFICIAL NEURAL NETWORK Ch 18.7
• A single layer perceptron network CANNOT "learn" xor function or Boolean sum
• Multi-layer Feed Forward Network:
• Multiple layers can coordinate to create complex multi-linear classification space,
• Fig 18.23 p732

4/2/24 37
 ARTIFICIAL NEURAL NETWORK Ch 18.7

• Types of architectures:

• Feed-forward Network: simple Directed Acyclic Graph

• Recurrent Network: feedback loop

• Transformer

4/2/24 38
 ARTIFICIAL NEURAL NETWORK Ch 18.7.4

• Back-propagation, draw how error propagates backward

• get total error del_E, weighted distribution over each backward nodes,
• each node now knows its "errors“ or E’s, propagate that error recursively
backward
• all the way through input layer,
• update weights or w’s

4/2/24 [Link] 39
 ARTIFICIAL NEURAL NETWORK Ch 18.7.4

• Total loss function at the output layer, k neurons:

Loss(w) = ∑k (yk – hw)2 = ∑k (yk – ak)2 , ak being the output produced

• This is to be minimized

• Gradient of this loss function is to iteratively lower:

∑k (del/del_w) (yk – ak)2

• Weight updates:
wij ß wij + α * aj * Delj

• aj is output of the neuron, Delj weighted modified error incorporating

the activation function’s effect (see Eq 18.8)

• Error propagation
Delj = g’(inj) ∑k (wjk Delk), where g’() derivative of activation, k is over next layer neurons
(previous layer in backward direction)
• An iteration of backpropagation learning:
Propagate errors then update weight, layer by layer backwards
4/2/24 40
 GENERATIVE NEURAL NETWORK
Not only classification…

Transformations: say, (x,y) goes to (2x,y) – a linear transformation that we want to learn

Neural Net:

4/2/24 [Link]
 GENERATIVE NEURAL NETWORK

• Add translations (Affine transformation):

Neural Net:

4/2/24 [Link]
 NEURAL NETWORK

• For non-linear transformations use non-linear activation function:

4/2/24 43
 NEURAL NETWORK

• Multi-layer generative network for non-linear transformation:

4/2/24 [Link]
 CONVOLUTIONAL NEURAL NETWORK

• Running window weighted mean = convolution

• Weights are learned

• Pooling: Pick up a value (e,g., max) from a window – reduce size

[Link]
4/2/24 45
 RECURRENT NEURAL NETWORK

• Feed back loops are provided in the network

• Independent from error propagation (backprop learning, weight update) algorithm:

[Link]
4/2/24 46
 DEEP LEARNING / NEURAL NETWORK
ISSUES TO WATCH FOR

• Classification / Regression / Generative

• Balance in data
• Augmentation for training data generation
• Validation / Test dataset size

• Network architecture
• Skip connections
• Activation function (more next slide)
• Loss function
• Optimization algorithm
• Epochs for training
• Learning rate
• Drop out

• Model saving / model size / number of parameters / FLOP

4/2/24 47
 DEEP LEARNING / NEURAL NETWORK
ACTIVATION FUNCTIONS

• Binary step function

• Linear
• ReLU
• Tanh
• Sigmoid/Logistic
• Leaky ReLU
• Parametric ReLU
• Softmax

[Link]

4/2/24 48
 NON-PARAMETRIC MODELS Ch 18.8

4/2/24 49
 NON-PARAMETRIC MODELS Ch 18.8

• Parametric learning: hw has w as parameters

• Non-parametric: no “global data fitting”

• Non-parametric: Query-time processing, minimal or no training

• Simplest: Table look up (Problem V)

For a query find a closest data point and return

• We still need a sense of “distance” between data points, e.g., Lp-norm

Lp (xj, xq) = (∑ki (xji – xqi)p )1/p , i runs over dimension of space,
xj are data points and xq is a query point in that space

4/2/24 [Link] 50
 NON-PARAMETRIC MODELS Ch 18.8
• K-nearest neighbor look up -kNN (Problem VI):
find k nearest neighboring example data instead of one,
and vote by their attribute values (pure counting for Boolean attributes)
• k is typically odd integer for this reason
• Fig. 18.26 p738, shows the “query-space”,
• Runs query for every point in the 2D space to check what the prediction will return for that point
• Gray areas indicate prediction=dark circle; and white areas indicate prediction=open circle

4/2/24 51
 NON-PARAMETRIC MODELS Ch 18.8

• (Problem VII) A different version of kNN: fix a distance value d and

vote by ALL data points within d

• Advantage: faster search, conventional kNN may need very expensive data organization
(Note: this is a search problem, before the query gets answered)

• Disadvantage: there may be too few data points within range d,

e.g. zero data point or no datum

• Curse of dimensionality: number of dimensions (attributes) >> number of data

– Sparsely distributed data points
– Search is slow

4/2/24 52
 NON-PARAMETRIC MODELS Ch 18.8

• An efficient data organization: k-d tree

• k is dimension here

• Balanced binary search tree over k-dimension, with median (on each dimension) as the
splitting boundary

4/2/24 53
 NON-PARAMETRIC MODELS Ch 18.8
• Another efficient data organization: LSH or locality sensitive hashing (Problem VIII)

• Hashing typically distributes data randomly, but we want nearer points together in memory

• A few concepts are combined:

o Approximate near-neighbors: find points that have “high” probability

to be within distance cr , radius r (fixed), c indicating “high” probability – these are
parameters

o Two close points have always close projections on any dimension(s), although the reverse is
unlikely to be true

o Create multiple hash functions on multiple subset of dimensions (random), [ideal: on all
dimensions] e.g., x1x3x4, x5x2x9,…

o Retrieve all points close to the query point in any of the hash function (union of points with
same hash value in each hash function)

o Do full kNN search over those points only

4/2/24 54
 Points actual distances in space

Points in the hash table

[Link]

4/2/24 55
 NON-PARAMETRIC MODELS Ch 18.8
• Back to regression: NON-PARAMETRIC REGRESSION (Problem IX)

• Philosophy: Only near-query data point should influence regression result

more than distant points
• Find k-nearest neighbors and perform regression on them
• Fig 18.28 p742: k=1, 3-average, 3 linear-regression, 10 with quadratic Kernel

4/2/24 56
 NON-PARAMETRIC MODELS Ch 18.8

• Find k-nearest neighbors and perform regression on them

• Kernel-regression: Locally weighted regression
– provide more weights to closer points to the query

• Weights may be computed (“learned”), given a parametrized function

4/2/24 57
 NON-PARAMETRIC MODELS Ch 18.8

• Kernel-regression: Locally weighted regression

• Alternative to fixed weights:

• Weights may be estimated, given a parametrized function

w^ = argminw ∑j K(Distance(xq, xj))* (yj – [Link])2

K is the kernel functional form with w as parameters,

xq is the query point,
(remember) yj is the actual output (“training labels”)

• Then, inference is the regressed output of query point xq is, h(xq) = w^ . xq

4/2/24 58
 NON-PARAMETRIC MODELS Ch 18.9
• SUPPORT VECTOR MACHINE (SVM) – basics, the best ML algorithm so far (Problem X)

• A few concepts come together:

• Support vector: Data points separating the boundary between + and – labels
(Classification or decision boundary)

• But with, two parallel lines, one passing through +ve support vectors, one through –ve ones
The gap between these two lines that must be maximized, Fig 18.31 p747

4/2/24 59
 H1 does not separate the classes.
H2 does, but only with a small margin.
H3 separates them with the maximal margin.

-- Wiki on SVM

Maximum-margin hyperplane and margins for an

SVM trained with samples from two classes.
Samples on the margin are called the support
vectors.

Note: expects clean, not noisy, separation

4/2/24 60
 NON-PARAMETRIC MODELS Ch 18.9
• SUPPORT VECTOR MACHINE (SVM) – basics [few concepts come together]

• Concept-1. Support vector

• 2) Non-linear space transformation to linearize decision plane: Kernelization

• Resulting space may have more dimensions than the original space

• 3) Very fast primal-dual optimization

4/2/24 61
 NON-PARAMETRIC MODELS Ch 18.9

• SUPPORT VECTOR MACHINE (SVM) – basics

• Query on SVM runs very fast – like kNN algorithm

- using only support vectors, selected at training time

• Stores Only Support Vectors – huge space saving too!

4/2/24 62
 TYPES OF LEARNING

• Supervised (Regression or Classification)

• Unsupervised / Clustering:
• Only data, no label to predict.
• So, group or cluster data by their “proximity”

• Semi-supervised learning:
• Predict (hypothesis h) and include the prediction as training data (!!) if actual predicted
value (y) was not available
• Follows the “trajectory” of incoming data

• Reinforcement Learning (Policy=Multi-dimensional label?):

• Occasional reward/penalty as the agent keeps behaving in real world (input data)
• Online / Interactive / Robotics

4/2/24 63
 UNSUPERVISED LEARNING / CLUSTERING

• No target output value to predict, i.e., no label, only a set of data points

• Machine Learning: Group them by their "proximity"

• Needs a distance function d(x1, x2) between data points x1 and x2

4/2/24 64
 TYPES OF CLUSTERING
• Centroid models: for example, the k-means algorithm represents each cluster by a
single mean vector.
• Connectivity models: for example, hierarchical clustering builds models based on
distance-based connectivity or topology. Mapper algo creates maps of data space.
• Distribution models: clusters are modeled using statistical distributions, such as
multivariate normal distributions used by the expectation-maximization algorithm.
• Density models: for example, DBSCAN and OPTICS defines clusters as connected
dense regions in the data space. ToMato for topological clustering uses this.
• Subspace models: in bi-clustering (also known as co-clustering or two-mode-clustering),
clusters are modeled with both cluster members and relevant attributes.
• Group models: some algorithms do not provide a refined model for their results and
just provide the grouping information of data space.
• Graph-based models: a clique, that is, a subset of nodes in a graph such that every
two nodes in the subset are connected by an edge that can be considered as a
prototypical form of cluster.

• Neural models: the most well known unsupervised neural network is the
self-organizing map (SOM) and these models can usually be characterized as similar
to one or more of the above models: learns local manifolds in data space
• Topological data analysis (e.g., Mapper or ToMato algorithm): visualize topology of data
points on space
4/2/24 65
 K-MEANS CLUSTERING
(Problem XII)

• Start with arbitrary k cluster-center points in data space

• Do two-steps while not converged:

• Group data points by their proximity to each of those k cluster-center points
• Find each group's mean (or median) and assign it as the new cluster-center

• [Link]

4/2/24 66
 HIERARCHICAL CLUSTERING
(Problem XIII)
• [Link]

• Two different ways to build:

• Start with all points as one cluster and keep splitting (top-down)
• Each point as a cluster and keep merging (bottom-up)

4/2/24 67
 HIERARCHICAL CLUSTERING
• Needs a measure for inter-cluster distance, for splitting or merging

• UPGMA algorithm’s (bottom up) inter-cluster distance: [1/|A|*|B|] * ∑xÎA ∑xÎB d(x,y)

where |A| is the size of cluster A, and so for B, and

x and y are two points in clusters A and B, respectively,
d(x,y) is the distance between those two points

Genetic base pair distances translated

to evolution time distance

4/2/24 68
 DENSITY-BASED CLUSTERING
(Problem XIV)
• Given a set of points in some space, it groups points that are closely packed together
(points with many nearby neighbors), marking as outlier data points
that lie alone in low-density regions (whose nearest neighbors are too far away).

• [Link]

• p is a core point if at least minPts #points are within distance ε

of it (including p). Those points are said to be directly reachable from p
• q is directly reachable from p if point q is within distance ε from point p
where p is a core point.
• q is reachable from p if there is a path from p to q, via directly reachable points,
with the possible exception of q itself.
• All points not reachable from any other point are outliers.
• Core points constitute a cluster core with reachable outliers as cluster edge

4/2/24 69
 ADVANTAGES: DBSCAN

• No need for cluster number k as input (k = #clusters) as opposed to that in k-means

clustering

• Arbitrarily shaped clusters.

It can even find one cluster surrounded by a different cluster

• Understands noise, and is robust to outliers

• Requires two parameters minPts and ε, can be set by expert by pre-analyzing data

• It is mostly insensitive to the ordering of the points in the database.

(However, points on an edge between two different clusters might swap cluster membership)

4/2/24 70
 DISADVANTAGES: DBSCAN

• DBSCAN is non-deterministic: border points that are reachable from more than one cluster

• DBSCAN* is a variation that treats border points as noise, and not included in clusters

• Quality of DBSCAN depends on minPts and ε

• DBSCAN cannot cluster data sets well with large differences in densities,
since the minPts and ε combination cannot then be chosen appropriately for all clusters

• If the data and scale are not well understood, choosing a meaningful ε can be difficult.

4/2/24 71
RESOURCE (IGNORE IN SYLLABUS)
A group of data scientists tested some popular chatbots on tasks
including formal and casual writing, text and tone editing, and
programming. Here are some of their impressions:

Bard: good for making your writing more approachable to lay

audiences
Claude: reliably suggests titles or acronyms that make sense, and
good at summarizing text
ChatGPT: offers context, which helps with planning a project or
document
Phind: excels at answering software-development questions

4/2/24 72
 IGNORE FOR NOW: SELF-SUPERVISED LEARNING

4/2/24 73
 SELF-SUPERVISED LEARNING

Based on Autoencoder-Decoder

4/2/24 74