Machine Learning: Supervised and Unsupervised Learning

Machine Learning

• Machine Learning sits within Artificial Intelligence
• Supervised learning and unsupervised learning are types of machine learning
• Deep learning is a type of machine learning, and uses neural networks

Foundation for Supervised and Unsupervised Machine Learning

• Introduction
• Numerical Vectors
• Data Encoding
• Simple Machine Learning algorithms

Supervised Machine Learning

• Instance-Based Learning
• Probabilistic Learning
• Decision Tree
• Support Vector Machine

Unsupervised Machine Learning

• Simple Clustering Algorithms
• K-Means Algorithm
• EM Algorithm
• Advanced Clustering

Advanced Topics

• Ensemble Learning
• Semi-Supervised Learning
• Temporal Learning
• Reinforcement Learning

Supervised Learning

• An environment provides examples to a teacher
• The teacher provides desired labels
• The machine learning algorithm classifies labels and sends it for correction
• Errors from the machine learning are used for future classifications

Classification

• Logistic Regression
• SVM
• Neural Network
• Decision Tree
• Random Forest
• GBDT
• KNN
• Naive Bayes

Regression

• Linear Regression
• SVM
• Neural Network
• Decision Tree
• Random Forest
• GBDT

Clustering

• K-Means
• Hierarchical Clustering
• Density-Based Clustering

Other Machine Learning Methods

• Correlation Rule
• Principal Component Analysis (PCA)
• Gaussian Mixture Model (GMM)

Binary Classification

• Data is classified as positive or negative

Multiple Classification

• Data is put into Class 1, Class 2, up to Class M

Decomposition Into Binary Classifications

• Can be broken down into multiple classifications and decisions

How Unsupervised Learning Works

• An environment gives examples to machine learning algortithm
• The Machine learning algorithm then puts the data into clusters
• A cluster prototype is then developed using similarity

Univariate Regression

• An input vector goes into a regression model
• The result is a continuous output value

Multivariate Regression

• An input vector goes into a regression model
• The result is multiple continuous output values, from 1 to M

Binary Clustering

• Data is broken into two clusters

Multiple Clustering

• Clusters have many different subsets

Data Structures

• Data can be structured or unstructured

Structured Data

• Organized in rows and columns
• Usually from relational databases
• The most common source of data

Unstructured Data

• Examples: text, images, audio, video
• Can be sourced from Facebook posts, tweets, complaints, reviews, photos, phone calls, blogs, etc.
• In general, deep learning is used for unstructured data.

Text Categorization

• Text categorization assigns a category, from a predefined list, to a document automatically
• Text categorization is a pattern classification task for text mining
• Text categorization is necessary for efficient management of textual information systems

Tokenization

• Divides the assignment into a number of tokens

Primitive Instance Based Learning

• Look-up table gives the Input Vectors the Labels, with + and -

Classification Rules

• If A = v1, then C1
• If A = v2, then C2
• If A = vk, then Ck

Instance Based Learning

• Classify by Rule List classifies the item example
• It checks if the rule matches the value, and categorizes it, otherwise set to "unclassified"

Euclidean Distance

• Calculated as the square root of the sum of the squared differences between a new point (x) and an existing point (y)
• Formula: √Σ(xi − yi)^2

Manhattan Distance

• Distance between real vectors using the sum of their absolute difference
• Formula: Σ|xi − yi|

Binary-Valued Features

• Uses Hamming distance defined as: d(xi, xj) = Σ Ⅱ(xim ≠ xjm)
• Hamming distance counts the number of features where the two examples disagree

Machine Learning with Mixed Feature Types

• Can use mixed distance measures

Machine Learning With Assigned Weights

• Defined as: d(xi, xj) = Σ wmd(xim, xjm)

Similarity Computation

• Formula: Euclidean Distance = √Σ(xi − yi)^2 where x = x₁,x₂....x(d) and y = Y₁,Y₂....y(d)
• Formula: Cosine Similarity = 2Σ xi yi / ||x|| + ||y||

K-Nearest Neighbor (K-NN)

• Given training data D = {(x1, y1),..., (xN, yN)} and a test point
• Look at the K most similar training examples

KNN for Classification

• Assigns the majority class label of K-Nearest

KNN for Regression

• Assigns the average response of K-Nearest

KNN Algorithm Requirements

• Requires Parameter K, the number of nearest neighbors to look for

Calculating the Test Point's Distance

• Compute the test point's distance from each training point
• Sort the distances in ascending (or descending) order
• Use the sorted distances to select the K nearest neighbors
• Use majority rule (for classification) or averaging (for regression)

K-Nearest Neighbors

• K-Nearest Neighbors is a non-parametric method
• K-Nearest Neighbors doesn't learn an explicit mapping from the training data
• K-Nearest Neighbors simply uses the training data at the test time to make predictions

Small K

• Creates many small regions for each class
• Can lead to non-smooth decision boundaries and overfit

Large K

• Creates fewer larger regions
• Usually leads to smoother decision boundaries
• Boundary can underfit

Choosing K

• Often data-dependent and heuristic-based
• Or using cross-validation (using some held-out data)
• A K too small or too big is not ideal

K-Nearest Neighbor Advantages

• Simple and intuitive, easily implementable
• K-NN approaches the best possible classifier (Bayes optimal)

K-Nearest Neighbor Disadvantages

• Needs to store all the training data in memory at test time
• Can be memory intensive for large training datasets
• An example of non-parametric, or memory/instance-based methods
• Different from parametric, model-based learning models
• Expensive at test time, O(ND) computations for each test point
• Have to search through all training data to find nearest neighbors
• Distance computations with N training points (D features each)
• Sensitive to noisy features
• May perform badly in high dimensions (curse of dimensionality)

The KNN Algorithm steps

• Load the Data
• Initialize K to your chosen number of neighbors
• For each example in the data: Calculate the distance between the query example and the current example from the data
• Add the distance and the index of the example to an ordered collection
• Sort the ordered collection of distances and indices from smallest to largest (in ascending order) by the distances
• Pick the first K entries from the sorted collection
• Get the labels of the selected K entries
• If there is Regression, Return the mean of the K labels
• If there is classification, return the mode of the K labels