Mearues of performance​

Accuracy​

$A = \frac{TP + TN}{TP + TN + FP + FN}$

• the ratio of correct predictions to all predictions
• it is the number of true positives and true negatives (the correct predictions) divided by the total number of predictions.

Error rate​

$E = \frac{FP + FN}{TP + TN + FP + FN}$

• the ratio of incorrect predictions to all predictions
• It is equivalent to $1 – Accuracy$.
• It is the number of false positives and false negatives divided by the total number of predictions.

True positive rate, Recall, Sensitivity​

$TPR = \frac{TP}{P} = \frac{TP}{TP + FN}$

• the proportion of actual positives for which the test result is positive.
• it shows how sensitive the model is to detecting positive instances.
• the ratio of true positives to all positives
• the data points that were correctly predicted as positive divided by the number of true positives and false negatives.

False positive rate, Fall Out, False Alarm​

$FPR = \frac{FP}{N} = \frac{FP}{FP + TN}$

• the proportion of actual negatives for which the test result is positive.
• It is equivalent to $1 – Specificity$.
  • large values of specificity indicate small false negative rates.

The true negative rate, Specificity​

$SPC = TNR = \frac{TN}{N} = \frac{TN}{FP + TN}$

• the proportion of actual negatives for which the test result is negative
• It shows how well the model does at identifying actual negatives as negative.

The false negative rate, Miss Rate​

$FNR = \frac{FN}{TP+FN}$

• the proportion of the actual positives for which the test result is negative.
• It is equivalent to $1 – Sensitivity$.
  • large values of sensitivity indicate small false positive rates.
• It is a common trick that often change classifiers to bias them towards making type 1 FP versus type 2 FN errors.
  • This can often change classifier to bias towards making FP errors rather than FN errors.
  • It depends on which are worse to make
  • They are biased if there are different numbers of items in each class

Precision, Positive Predictive Value​

• PPV, Positive Predictive Value
• a measure of how accurate and precise the positive predictions are
• It is the ratio of true positives to predicted positives.

Accuracy and Error rate​

• in practice, the previous measures don't always work well
  • they are biased, especially if there are different numbers of items in each class.
• if the data is imbalanced, it's much better to use a true positive rate or true negative rate instead.

F1​

$F = 2 * \frac{Precision * Recall}{Precision + Recall}$

• known as F-score or F-measure
• a measure of the accuracy of the test
• It is the harmonic mean of the recall and precision, where an F1 score reaches its best value at 1 (perfect precision and recall).
• It allows the Recall and Precision to be assessed in the same calculation.

• $Accuracy = \frac{110 + 60}{185} = 0.91$
• $Error Rate = \frac{10 + 5}{185} = 0.08$
• $True Positive Rate (Sensitivity/Recall) = \frac{110}{115} = 0.95$
• $False Positive Rate = \frac{10}{70} = 0.14$
• $True Negative Rate (Specificty) = \frac{60}{70} = 0.85$
• $False Negative Rate = \frac{5}{115} = 0.04$
• $Precision = \frac{110}{120} = 0.91$
• $F1 = (2 * 0.91 * 0.95) / (0.91 + 0.95) = 0.92$

ROC curve​

Receiver Operating Characteristic Curve

• a graphical plot that explains how well a binary classifier system performs as the threshold at which it calls a data point as positive is varied.
• ROC graphs were originally used in the communications area to look at false alarm rates.
• The x-axis is the false positive
• The y-axis is the true positive rate (sensitivity, recall)
• ROC graphs contain all the information in the confusion matrix.
  • TPR(=TP/(TP+FN)), FPR(=FP/(FP+TN))
• a visual tool to compare trade-offs between the ability of a classifier to correctly identify positive cases and the number of negative cases that are incorrectly identified.
• an essential evaluation metric for checking the performance of a classification model.

AUC​

Area Under the ROC Curve

• AUC 0: the model predicts a negative class as a positive class and vice versa.
• AUC 0.5: the model has no discriminative capacity to differentiate between negative class and positive class
  • diagonal line from (0,0) to (1,1)
• AUC 0.7: 70% chance that the model will be able to differentiate between the positive and negative classes.
• AUC 1: the model predicts all positive class as positive class and all negative class as negative class.
• ROC is a probability curve and AUC represents the degree of separability
• It shows how capable the model is of differentiating between the classes.

Training/testing split​

• train-test split procedure is used to estimate the performance of machine learning algorithms
• should not be used
  • when the dataset is small
  • when the dataset is imbalanced
  • where additional configuration is required
  • train_test_split(..., stratify=y)
• most common approach to validate model performance
  • traning data is 80%
  • testing data is 20%

k-fold cross-validation​

• helps select the model which will perform best on unseen data
• overcoming the problem of overfitting and underfitting.
• a parameter called k defines the number of portions that a given data sample will be split into.
• k-fold cross-validation has less bias because it ensures that every single discovery from the main dataset has a chance to appear in both training and test sets.

Iteration of a 5-fold cross-validation

# X = Test set
# T = Train set
1st fold : XXXX TTTTTTTTTTTTT
2nd fold : TTTT XXXX TTTTTTTT
3rd fold : TTTTTT XXXX TTTTTT
4th fold : TTTTTTTT XXXX TTTT
5th fold : TTTTTTTTTTTTT XXXX

k = 3
dataset = [1, 2, 3, 4, 5, 6]

fold1 = [5, 2]
fold2 = [1, 3]
fold3 = [4, 6]

• Model1 will be trained on fold1 and fold2, and tested on fold3
• Model2 will be trained on fold2 and fold3, and tested on fold1
• Model3 will be trained on fold1 and fold3, and tested on fold2
• we can take the accuracy as the average of all rounds to get the final accuracy.

Bias-variance decomposition​

a formal method for understanding the prediction error of a model.

• the average of the distance between the target and model predictions.
• simple model: High bias, Low variance → Underfitting
  • not complex, high error component
• complex model: Low bias, High variance → Overfitting
  • quite sensitive to the specific training set

Bias​

the average of the distance between the target and model predictions.

• how well the model can do for any training set.
• the difference between the expected value and the parameter that we want to estimate
• $\text{Bias} = E[\hat{\theta}] - \theta$
  • If the bias is exactly zero, the estimator is unbiased
  • If the bias is greater than zero, the estimator is positively biased
  • If the bias is less than zero, the estimator is negatively biased

Variance​

the deviation between the average prediction value and the predicted value.

• Classifier error is also affected by variability in the training data because different training sets lead to different decision boundaries.
• High variance: it produces different results for different training sets.
  • sensitive to the particular training set.
  • models with less parameters tend to have lower variance.
• $Var(\hat{\theta}) = E[(\hat{\theta} - E[\hat{\theta}])^2]$

Noise​

changes in the target value

• objects with the same attribute values leading to different class labels.
• these errors are unavoidable even when you know the correct decision boundary.

Evaluating​

Underfitting​

the model did not capture enough patterns in the data

• The model provides poor performance on both the training and the test set.
• Reasons:
  • The training model is not trained as tightly as possible.
  • The model is not able to learn more.
    • model is not suitable for the task.
• Avoid underfitting by:
  • using more training data
  • choosing / training a more complex model
  • increase the number of parameters in the model, the type or complexity of the model, or the traninig time till a cost function is minimized.

Overfitting​

the model captures noise and patterns which do not generalize well to new data.

• The model has extremely good performance on the training set, but poor performance on the test set.
• Reasons:
  • the training data is not a perfect standard
• Avoid overfitting by:
  • regularization
  • pruning (parameters, strucutres of classifiers)
  • reducing the descriptive length (minimize the sum of the model's complexity and the dscription of the traning data)
  • optimization (use a separate subset for validating the model)
  • expansion (use or generate more training data)
    • adding synthetic samples to the dataset.

K-NN​

k-Nearest Neighbors

• a non-parametric technique
  • not involving any assumptions as to the form or parameters of a frequency distribution
• supervised learning classifier
  • uses proximity to make classifications or predictions about the grouping of an individual data point
  • defining new cases based on similarity measures (e.g., distance functions).
  • Euclidean: $d(x, y) = \sqrt{\sum_{} (x_i - y_i)^2}$
  • Minkowski: $d(x, y) = (\sum_{} |x_i - y_i|^p)^{1/p}$
  • Hamming: $d(x, y) = \sum_{} |x_i - y_i|$
• In weighted k-NN, weigh the votes according to distance
  • $w_i = \frac{1}{d^2}$
• If k is too small, it may be sensitive to noise points
• If k is too large, its neighbourhood may include points from other classes
• Choose an odd value for k, to eliminate ties

Industrial Applications of KNN​

• Retail business data analysis: Identify customer patterns and generate business value.
• Security and operational management: Simplify daily operations such as theft prevention.
• Credit card usage monitoring: Detect unusual patterns to identify fraudulent transactions.
• Transaction scrutiny software: Spot unfamiliar patterns and flag suspicious activity.
• Point-of-sale (POS) data analysis: Analyse register data for operational insights.

Computer vision​

• a field of artificial intelligence enabling computers and systems to derive meaningful information from digital images, videos and other visual inputs.
• vision is a perceptual channel that accepts a stimulus and reports soome representation of the world
• computer vision enables intelligent agents to see, observe and understand of environment

Core problems of CV​

• reconstruction: an agent builds a mode lfo the world from an image or a set of images
• recognition: an agent draws distinctions amont the objects it encounters based on visual and other information.
  • image classification
  • object detection
  • image segmentation

Classic approaches to object recognition problems​

• feature-based object recognition approach
  • works well for faces looking directly at the camera.
• pattern-element-based object recognition approach
  • a useful abstraction is to assume that some objects are made up of local patterns which tend to move around with respect to one another.
  • we can model objects with pattern elements.

Modern approaches to object recognition problems​

• deep learning networks
  • to recognition problems enables that features can be automatically learned and extracted from raw image data compares with the manual feature extraction in the classic approaches.
  • AlexNet, VGGNet, GoogleNet, ResNet, DenseNet, EfficientNet, RegNet...
• basic models and derived models
  • YOLO, SSD, RetinaNet, R-CNN...

Evaluation metrics for image classification​

Confusion Matrix​

ROC Curve​

1. Sort predicted probabilities
2. Try multiple thresholds
3. For each threshold, compute predicted labels
4. Compute TPR and FPR
5. Plot ROC curve (FPR vs TPR) i. $TPR = \frac{TP}{TP + FN}$ ii. $FPR = \frac{FP}{FP + TN}$
6. Compute AUC as area under ROC curve

from sklearn.metrics import roc_curve, roc_auc_score
fpr, tpr, thresholds = roc_curve(y_true, y_scores)
auc = roc_auc_score(y_true, y_scores)

Evaluation metric for object detection​

• AP is computed by summing trapezoid areas under the Precision-Recall curve.

Convolutional Neural Network (CNN)​

• contains spatially local connectinos at lest in the early layers
• has patterns of weights that are replicated across the units in each layer.
• use a kernel to detect patterns of weights that is replicated across multiple local regions in an image
• use convolution that applies the kernel to the pixels of the image

Input
   ↓
[Conv → ReLU] → [Pooling]
   ↓
[Conv → ReLU] → [Pooling]
   ↓
Flatten (2D → 1D 벡터)
   ↓
Fully Connected Layer
   ↓
Output Layer (Softmax/Sigmoid)

$z_i = \sum_{j=1}^{l} k_j \cdot x_{j + (i-1)s}$

• $z_i$: the $i$-th output element (convolution result)
• $j$: index inside the kernel (from 1 to $l$)
• $l$: kernel size (number of elements in the kernel)
• $k_j$: the $j$-th kernel weight (filter element)
• $x$: input sequence (the original data)
• $x_{j+(i-1)s}$: the input element aligned with kernel position $j$ when shifted by stride
• $s$: stride (step size of the kernel movement)
• $(i-1)s$: total shift in the input for the $i$-th convolution

Receptive Field​

• the receptive field of a neuron is the portion of the sensory input that can affect aht neuron's activation.
• In CNNs, the receptive field of a unit in the first hidden layer is small.
• just the size of the kernel, e.g., 3x3 or 5x5.
• In the deeper layers of the network, it can be much larger.

$R_{L} = R_{L-1} + (k_{L} - 1) \cdot \prod_{i=1}^{L-1} s_i$

• $R_L$: receptive field size at the $L-th$ layer
• $k_L$: kernel size at the $L-th$ layer
• $s_i$: stride at the $i-th$ layer

Pooling​

• works like a convolutional layer, with a kernel size $l$ and stride $s$, but the operation is applied is fixed rather than learned.
• no activation fucntion is associated with the pooling layer.
• common forms of pooling
  • average pooling
  • max pooling: saying a feature exists somewhere in the unit's receptive field.

Dropout​

• a way to reduce the test-set error of a network to increase its ability of generalization.
• makes a etwork herder to fit the traninig set.
• the network is created by deactivating a randomly chosen subset of the units (dropout rate).
• cannot explain why it works but the results is better

Batch Normalization​

• modern neural networks are almost always trained with some variant of stochastic gradient descent (SGD).
• Batch normlization rescales the values generated at the internal layers of the network from the examples within each minibatch.
  • it standardizes the input to a layer for each mini-batch.
• standardizes the mean and variance of the values.
• maeks it much simpler to train a deep network.

Tranining in a CNN​

$Cross-entropy(y, \hat{y}) = -\sum_{i} y_i \log(\hat{y}_i)$

• Forward pass
• Backward pass
• Parameter update

Variants of CNNs​

AlexNet​

ResNet​

• stands for a residual neural network.
• was designed to enable hundreds or thousands of convolutional layers.
• Residual neural networks do this by utilizing skip connections, or shortcurts to jump over some layers.
• was an innovative solution to the "vanishing gradient" problem.

x ────────────────► (+) ──► y
   │                     ▲
   ▼                     │
 [Conv → ReLU → Conv] = F(x)

VGGNet​

• increases the depth of the network through adding more convolutional layers by using small convolution filters (3x3) while other parameters are fixed.

Derived model for object detection​

YOLO​

1. Split an images to S times S blocks.
2. Apply object classification to each block and get confidence score of different objecxt for each block.
3. Based on the class probability map to locate objects.

Calculation AP and mAP​

1. Gather Detection results
2. Match Predictions to Ground Truth
3. Compute Precision and Recall to generate a set of (recall, precision) points
4. Build the Precision-Recall (PR) Curve (presioin decreases as recall increases)
5. Smooth the Precision-Recall Curve
6. Calculate AP
7. Extend to mAP

OOP Principles​

Encapsulation​

• bundles data attributes (fields) with methods that use the data in a single unit called "Object"
• hides sensitive data attributes by declaring the fields private.
• fields can be declared protected in the parent class, allowing access from the child class.
• exposes the data attributes values only through public getters/setters to allow access or modification of the field values.

Intheritance​

class A:
    pass

class B(A):
    pass

class C(A):
    pass

• Superclass defines common method signatures (with/without implementation) and fields.
• Subclasses provide the implementations for (or override) these method signatures
• private attributes cannot be directly accessed from the child classes.
• to refer to superclass properties (fields, methods) or constructor, use the keyword super()

Polymorphism​

• means many forms.
• permits an object to have multiple types.
• allows object of different types but with a common parent to be stored in the same collection.
• enables inherited methods from the parent to perform different tasks when called by subclasses.

Abstraction​

• the process of hiding the implementation details and exposing only the necessary behavior to the user.
• abstract class must at least contain one abstract method.
• abstract class ccan have concrete methods.
• abtract methods are only prototypes in the parent class, the actual implementation is provided by the subclasses that inherit the abstract class.
• rules
  • if a class contains at least on abstract methods, it should be declared abstract.
  • if another class inherits an abstract class, it must implement all the abstract methods of that class.

from abc import ABC, abstractmethod

class Person(ABC):
    def __init__(self, name):
        self.name = name

    @abstractmethod
    def show(self):
        pass

    def show_name(self):
        print(f"Name: {self.name}")

class Student(Person):
    def __init__(self, name, id):
        self.id = id
        super().__init__(name)

    def show(self):
        super().show_name()
        print(f"ID: {self.id}")

• interfaces are complete abstract classes declared with the interface keyword.
• only contain prototype (abstract) methods with empty body code.
• cannot be instantiated nor inherited as they do not have constructors.
• a class can implement multiple interfaces.
• a class implementinig an interface must provide an implementation for all its abstract methods.
• add an access layer to further hide the methods impelmentation.
• act as a middleware inside the program, allowing human, machines, and other software to interact with the program's functionalities without knowing the implementation details.

# interface A is a fully abstract class
# interface A must inherit ABC
# class B(A) must implement all abstract methods of A
# interface A methods have the @abstractmethod decorator with pass as body-code
from abc import ABC, abstractmethod

class Person(ABC):
    @abstractmethod
    def show_info(self):
        pass

class Student(Person):
    def __init__(self, name, id):
        self.name = name
        self.id = id
    
    def show_info(self):
        print(f"Name: {self.name}, ID: {self.id}")

OOP Design Rules​

• How to split the code into seperate classes and preserve encapsulation
• How to organizae the code into methods to hide the implementation details and expose the behavior
• How the objects interact at runtime
• How to name the class entities

5 Design Rules

• Encapsulation
  • hide fields behind methdos
  • requires fields to be private while allowing methods to be public
  • requires a methods related to a field (such as access, modify, use) be defind in the same class.
• Push code to the right
  • requires the code/methods used by objects of a class be written in the same class.
  • ensures methods are written for reusability and placed in the correct class so they can make use of the class's fields.
  • determines which class is responsible for defining the methods needed to achieve the program's goals.
• Spread plans across classes
  • involves planning the distribution of code across multiple classes from the start.
  • focuses on distributing responsibilities logically among different classes, so that each class has a clear and focused role.
  • by convention, this rule requires using the same method name (for the same goal) across all classes.
• Hide by default
  • hiding implementation details within a class and exposing only the necessary functionality to the outside.
  • helps in achieving encapsulation and abstraction.
  • promotes better design and maintainability.
• Follow naming conventions
  • use nouns to name fiels.
  • use nouns to name functions.
  • use verbs to name procedures.
  • if an entitiy is compsed of two or more words.
    • use camelCase/snake_case for fields and methods.
    • use PascalCase for class names.

Menu Pattern​

• consolidates the action-trieggers of a program into a single method.
• common design choice in applications with user interaction.
• the menu methods is executed in the program's main method.
  • offers users interactive CLI command choices.
• menu() requires a read-function in a while loop, allowing the menu() tor repeatedly read inpus from STDIN.

<condition> = read_choice()

loop (<condition>):
    check (<condition>):
        case 1: do task <action_1()>
        case 2: do task <action_2()>
        ...
        case n: do task <action_n()>
        default: <alternative-action>

menu(self):
    choice = input("Enter choice: (d/w/b/h/x): ").lower()
    while choice != "x":
        match choice:
            case "d":
                self.deposit()
            case "w":
                self.withdraw()
            case "b":
                self.show_balance()
            case "h":
                self.show_history()
            case "x":
                self.exit()
            case _:
                self.show_invalid_choice_message()

        choice = input("Enter choice: (d/w/b/h/x): ").lower()

Classification and Prediction​

Classification​

classifies data based on the training set and the class labels and uses it in classifying new data

• Model construction (learning)
• Model evaluation (accuracy)
• Model use (classification)

Prediction​

predicts categorical class labels based on unseen data

• models continuous-valued functions

Classfication Methods​

• Decision tree induction
• Bayesian classification
• Nearest neighbour classification, case-based reasoning
• Neural networks
• Support Vector Machines
• Ensemble methods

Issues around classification and prediction​

• Predictive accuracy
• Speed and scalability
• Robustness
• Interpretability
• 'Goodness' of classifier

Classification process​

Decision Tree​

• Builds trees to describe data
• Easy to translate into rules
• Robust to niosy data
• able to build disjunctive expressions
• Inductive bias prefers small trees over larger.

Decision Tree Methodologies​

• Itertative Dichotomiser 3 (ID3)
• C4.5
• Classification And Regression Trees (CART)
• Chi-square Automatic Interaction Detection (CHAID)
• Multivariate Adaptive Regression Splines (MARS)

Decision Tree Forms​

• Balanced
  • each branch has the same depth from the root to leaves.
  • all nodes have the same number of splits
• Deep
  • some nodes have different levels, wherein some of them are split into more branches.
• Bushy
  • split into multi-way from the root
  • undesirable because the split may lead to small numbers of instance in each leaf node.

Entropy and Information Gain​

Entropy​

measures the amount of disorder / (im)purity in a collection of things. i.e. the unpredictability of the data.

$Entropy(S) = -p_{+} log_2(p_{+}) - p_{-} log_2(p_{-})$

• Constructing a decision tree is all about finding an attribute that returns the highest information gain and the smallest entropy.
• $S$ stands for total number of samples
• $P_{+}$ denotes the likelihood of a yes (positive) answer.
• $P_{-}$ denotes the likelihood of a no (negative) outcome.

$E(S) = \sum_{i=1}^{c} -p_i log_2(p_i)$

Information Gain​

measures how well a given attribute separates the training examples according to the target classification.

• The larger the information gain is, the stronger the feature will be.

$Gain(S,A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)$

• $S$ = set of training examples
• $A$ = the particular attribute to be tested
• $Values(A)$ = the set of values for the attribute A
• $S_v$ = subset of $S$ with attribute $A$ having value $v$s

Iterative Dichotomiser 3​

• constructs trees in a top-down manner.
• check each instance attribute with a statistical test to see how well it alone classifies (splits) the training examples.
• this becomes the root node.
• descendent is created for each possible value of the attribute and training examples split to the appropriate descendent.
• repeat the procedure for each descendent.
• the algorithm is going to issue recursion on each of the partitions.
• the output of this algorithm is the creation of a Model.

function id3 (examples, target, attrs):
  create root node for tree
  
  if examples all +ve, return root with label=+
  if examples all -ve, return root with label=-
  if attrs is empty
    return root w/ label=most common value of target in examples else
   else
      A ← attribute from attrs that best splits examples
      root ← A for each possible value, vi , in A
        add a new branch below root corresp. to the test A = vi
        examples_v ← the subset of examples with A = vi

        if examples_vi is empty
          add a leaf node below branch w/ label = most common value of target from examples
        else below the branch add the subtree given by
          id3(examples_vi , target, attrs - {A})

      return root

Hypothesis space search​

• ID3 can be seen as a search through a space of hypotheses for one that matches the training data.
• It's a greedy search
• Hypothesis space = all the possible trees
• Simple to complex, hill climbing search
• Complete search = decision tree can represent all possible hypotheses
• Maintains only one current hypothesis
  • cannot find alternative decision trees
• No backtracking, maybe stuck in local optima
• Uses all training data at each step
  • less sensitive to errors in individual examples

Inductive Bias​

• Shorter trees preferred
• High information gain near the root
• cos' simple to complex search

Issues with decision trees​

Overfitting training data​

• occurs when a tree gives higher accuracy on the training data than another tree, but lower accuracy on the unseen data.
• because the training data is noisy or not representative of the unseen data.
• can measure how well the tree generalizes by checking error on test data.

Dividing the data​

• Training set
  • used to build the initial model
  • may need to enrich the data to get enough of the special cases
• Cross validation set
  • used to adjust the initial model
  • used to work out the correct values of parameters in model
  • models can be tweaked to be less dependent on idiosyncrasies in the training data to be a more general model
  • idea is to prevent over-training (i.e. finding patterns where none exist)
• Test set
  • used to evaluate the model performance

Avoiding Overfitting​

• stop growing the tree once the test error decreases
• grow the tree as normal (i.e. wit hoverfitting) then post-prune it.
• use a separate set of data apart from training to test when to prune nodes (training & cross-validation set)
• use all data to train, but apply a statistical test whether to expand/prune a node.
• use an explicit complexity measure (e.g. Minimum Description Length, MDL) to trade off accuracy vs complexity.

Reduced-Error pruning​

• build tree
• consider each node in tree for pruning
• pruning
  • remove subtree
  • make into a leaf
  • assign label as most common class in associated training examples.
• if pruned tree has as good error on the cross validation set as the unpruned tree, do the prune.
• keep pruning until the error on cross validation set increases.

Cross validation set​

• the main difficulty comes when you don't have much data and need it all for training.
• k-fold cross-validation or leave-one-out training can help.

Rule Post-Pruning​

• converts the decision tree to rules
• removes preconditions that do not worsen the accuracy (on the cross validation set or with a statistical test)
• sorts the rules by estimated accuracy and uses this order when classifying new data

Continuous Valued Variables​

• use real valued attributes for tests at nodes.
• Dynamically define new discrete attributes that partition the continuous attribute.
• discrete: $A < v = true$ and $A >= v = false$
• the boundary poins can be estimated from the training data.

The confusion matrix​

• a basic method of evaluation of classifiers
• The columns have numbers associated with the actual number of positive data points in the test set and the actual number of negative data points in the test set

• TP: the number of correct prediction of positive samples.
  • the number of data points in the test set that were positive and the classifier correctly assigned them to the positive group
• TN: the number of correct prediction of negative samples
  • the number of data points in our test set that was actually negative and predicted as negative by the classifiers
• FP: the number of incorrect predictions of positive samples
  • the value of data points in our test set that was actually negative but were predicted by the classifier as positives.
  • These ones are obvious errors, which is called a type 1 error.
  • type I error
• FN: the number of incorrect prediction of negative samples.
  • the number of data points in our test set that was actually positive but were predicted by the classifier as negative
  • usually called the type 2 error, and when we are trying to build a classification.
  • might have a trade-off between the number of the type 1 error or the type 2 error.
  • type II error

Vocabulary & Expressions​

Markov process or Markov chain​

the state sequence satisfies the Markov assumption

• The current state depends on only a finite fixed number of previous states.
• $P(X_t | X_{0:t-1}) = P(X_t | X_{t-1})$

Decision Theory​

• Choosing actions based on the desirability of their immediate outcomes.
• The outcome of taking action $a$ in state $s_0$ is deterministic then $Result(s_0, a)$.
• If the outcome is non-deterministic (stochastic), fully observable, the agent knows the current state $s_0$.
  • It is represented as a random variable whose values are the possible outcome states.
  • The transition model specifies the probabilities of possbile outcome states.
  • $P(s, a, s')$

MEU, Maximum Expected Utility​

A rational agent should choose the action that maximizes its expcted utility.

• The MEU principle could be seen as defining all of AI.
• $action = argmax_a(EU(a|e))$
  • among this set of actions, give the highest expected utility.
• $EU(a|e) = \sum_{s'} (P(Result(a) = s' | a, e) * U(s'))$

Sequential decision problem​

type of problem or scenario where a decision-maker must make a series of choices or decisions over time in order to achieve a desired outcome.

• a sequential decision-making problem or sequential decision-making task

MDP, Markov Decision Process​

a sequential decision problem for a fully observable, stochastic environment environment with a Markovian transition model and additive rewards.

• a formal framework for modeling sequential decision problems.
• including states, actions, transition probabilities, and rewards
• used in reinforcement learning and operations research.

• A set of states: an initial state $S_0$, possible terminal state(s)
• A set of actions in each state: $ACTIONS(s)$
• A stochastic Markov transition model: $P(s' | s, a)$
• A reward function: $R(s)$ or $R(s, a, s')$
• In MDP, Additive Reward is defined as a function that assigns a numerical value to each state-action pair or state-transition pair.
  • represents the immediate benefit or cost associated with taking a specific action in a particular state.
• The solution must specify what the agent should do for any state that the agent might reach.
• Policy: $π(s)$, an action for each state
  • A solution to an MDP.
  • $\pi(s)$ is the action recommended by the policy $\pi$ for state $s$
• Q state: $Q(s, a)$, the expected utility of doing action $a$ in state $s$

RL, Reinforcement Learning​

• an agent interacts with an environment
• takes actions to maximize a cumulative reward signal over time.
• learns a policy that balances exploration and exploitation
  • exploration: trying new actions.
  • exploitation: choosing known good actions.

Sample MDP​

Environment​

• The agent lives in a 4x3 fully observable stochastic environment
• Walls block the agent's path; Begin in the start state, the agent must choose an action at each time step
• Actions available to the agent in each state: Up, Down, Left, or Right
• The interaction with the environment terminates when the agent reaches one of the goal states, marked +1 or -1

4x3 Grid World​

• START: Initial position (1,1)
• 🚫: Wall (impassable)
• +1: Goal state with positive reward
• -1: Goal state with negative reward

Transition Model​

• Stochastic environment with uncertainty
• When agent chooses an action, there's:
  • 0.8 probability of moving in intended direction
  • 0.1 probability of moving perpendicular to intended direction (each side)

Reward Function​

• The agent receives rewards each time step:
  • Small "living" reward each step (-0.04 in all states except the terminal states)
  • Big rewards come at the end (+1 for good and -1 for bad terminal states)

Goal​

• To maximize sum of rewards from the start state to a terminate state

Additive Reward​

• a type of reward structure
• the total reward earned by an agent in an MDP
• calculated by summing up the individual rewards received at each time step as the agent interacts with the environment.

Discounted reward​

• a techinque used to calcluate the expected cumulative reward over time.
• applying a discount factor to future rewards, prioritizing more immediate rewards over distant ones.

Utility​

$U^{\pi}(s) = E\left[\sum_{t=0}^{\infty} \gamma^t R(S_t, \pi(S_t), S_{t+1})\right]$

• The expectation $E$ is with repect to the probability distribution over state sequences determined by $s$ and $\pi$.
• $\gamma$ is the discount factor, $0 \leq \gamma < 1$, which determines the present value of future rewards.
• $R(S_t, \pi(S_t), S_{t+1})$ is the reward received when transitioning from state $S_t$ to state $S_{t+1}$ by taking action $\pi(S_t)$.

Bellman equation​

$U(s) = max_{a \in A(s)} \sum_{s'}P[s'|s,a](R(s,a,s') + \gamma U(s'))$

• In optimal setting, the neighbor state meets the Bellman equation.
• From $s_0$ to termination, each step in the sequence should match the Bellman equation.

$\pi^{*}_s = argmax_{\pi}U^{\pi}(s)$

Q function​

• the expected utility of taking a given action in a given state.
• enables the agent to act optimally simply by choosing
  • $U(s) = max_a Q(s,a)$
• The optimal policy can be extracted from the Q-function.
  • $\pi^{*}(s) = argmax_a Q(s,a)$

$Q(s,a) = \sum_{s'}P[s'|s,a](R(s,a,s') + \gamma U(s')) \\ \space = \sum_{s'}P[s'|s,a](R(s,a,s') + \gamma max_{a'}Q(s',a'))$

Reinforcement Learning​

Key components of RL​

• Agent
• Environment
• State
• Action
• Reward
• Policy

Application of RL​

• Robotics
• Autonomous systems
• Game playing
  • Atari video games from raw visual input
  • Playing poker
  • Alpha Go
• Recommendation systems

RL Algorithms​

• Model-based RL
  • often learns a utility function $U(s)$
  • the sum of rewards from state $s$ onward from observing the effects of its actions on the environment.
• Model-free RL
  • Action-utility learning, such as Q-learning
  • Policy learning
• Passive RL
  • the agent's policy is fixed
  • the task is to learn the utilities of states.
• Active RL
  • the agent must figure out what to do through exploration and exploitation.
    • Exploration: trying new actions to discover their effects.
    • Exploitation: leveraging known actions that yield high rewards.

Direct Utility Estimation​

• the utility of a state is the expected total reward from the state onward.
  • the expecgted reward-to-go from that state.
  • each trial provides a sample of this quantity for state visited.
• end of each sequence, the algorighm calculates the observed reward-to-go for each state and updates the estimated utility for the state accordingly.
• In the limit of infinitly many trials, the sample average will converge to the expectation in teh Bellman equation.
• Ignores the connections between states.
  • misses opportunities to learning, it learns nothing until the end of the trial.
  • often converges very slowly.

Adaptive Dynamic Programming, ADP​

$U_i(s) = \sum_{s'}P(s'|s,\pi_{i}(s))[R(s,\pi_{i}(s),s') + \gamma U_{i}(s')]$

• advantage of the constraints among the utilities of states by learning the transition model
  • that connects them and solves the corresponding MDP
  • using dynamic programming to calculate the utilities of the states.
• These Bellman equations are linear when the policy $\pi_i$ is fixed
  • can be solved using any linear algebra package.

Learning a transition model​

• the environment is fully observable
• the agent can learn the mapping from a state-action pair $(s, a)$ to the resulting state $s'$.
• The transition model $P(s'|s,a)$ is represented as a table and it is estimated directly from the counts that are accumulated in $N_{s'|s,a}$.
• The counts record how often state $s'$ is reached when executing $a$ in $s$.
  • $P(s'|s,a) = \frac{N_{s'|s,a}}{\sum_{s''}N_{s''|s,a}}$

Temporal difference, TD​

$U^{\pi}(s) \leftarrow U^{\pi}(s) + \alpha[R(s,\pi(s),s') + \gamma U^{\pi}(s') - U^{\pi}(s)]$

• when a transition occurs from state $s$ to state $s'$ via action $\pi(s)$
• $\alpha$ is the learning rate, $0 < \alpha \leq 1$
• no need a transition model to perform updates
• the environment is itself supplies the connection between neighboring states in the form of observed transitions.

Q learning​

• model-free reinforcement learning algorithm
• the agent learns a Q-function, $Q(s,a)$
• avoids the need for a model by learning an action-utility function $Q(s,a)$ instead of utility function $U(s)$.
• a model-free Q-learning TD update
  • $Q(s,a) \leftarrow Q(s,a) + \alpha[R(s,a,s') + \gamma max_{a'}Q(s',a') - Q(s,a)]$
  • this update is calculated whenever action $a$ is executed in state $s$ leading to state $s'$
• TD Q-learning agent doesn't need a transition model $P(s'|s,a)$
  • either for learning or for action selection.

Quantitative and Qualitative Methods​

Types of Research Methodology​

• Historical: Qualitative
• Comparative: Qualitative
• Descriptive: Qualitative
• Correlation: Quantitative
• Experimental: Quantitative
• Evaluation: Qualitative
• Action: Qualitative
• Ethnographic: Various (not quantitative)
• Ethnogenic: Various (not quantitative)
• Feminist/Identity Politics: Various (not quantitative)
• Cultural: Various (not quantitative)

Common data collection methods​

Qualitative data collection methods​

• Observations: recording what you have seen, heard, or encountered in detailed field notes
• Interviews: asking people questions in one-on-one conversations
• Focus groups: asking questions and generating discussion among a group of people
• Surveys: distributing questionnaires with open-ended questions
• Secondary research: collecting existing data in the form of texts, images, audio or video recordings, etc.

Quantitative data collection methods​

• Experiments
• Computer Simulation and Agent-Based Models
• Controlled observations
• Surveys: paper, kiosk, mobile, questionnaires
• Longitudinal studies
• Polls and Telephone interviews
• Face-to-face interviews

Unsupervised machine learning​

• most common tasks are clustering, anomaly detection, and neural networks.
• infer underlying patterns without human supervision or intervention and enable us to discover both the differences and similarities in a dataset.
• can be considered ideal solutions for exploratory data mining.

Clustering​

objects (unlabelled data) are organised into groups, where the members of each group are similar in some way to each other and less similar to those in other groups.

• Classification assigns objects/data to the predefined (labelled) classes
• Clustering groups the objects/data based on the similarities between them
• used in pattern recognition, image analysis and bioinformatics.
• different clustering algorithms can produce different results based on their own definition of a cluster
• the parameters (such as the distance function, density threshold and the number of expected clusters) of the clustering algorithm should be set based on the particular characteristics of the dataset and the user’s intention

• Similarity Measure: Numerical measure of how alike two data objects often fall between 0 (no similarity) and 1 (complete similarity)
• Dissimilarity, or Distance Measure: Numerical measure of how different two data objects are range from 0 (objects are alike) to $\infty$ (objects are different)
• Proximity: Refers to a similarity or dissimilarity

Distance measures​

Distance metrics or dissimilarity measures

• basically deal with finding the proximity or distance between data points and determining if they can be clustered together.
• Manhattan distance: distance between two vectors if they could only move right angles.
  • $Dist(A, B) = \sum_{} |a_{i} - b_{i}|$
  • no diagonal movement involved in calculating the distance.
• Euclidean distance: can best be explained as the length of a segment connecting two points.
  • $Dist(A, B) = \sqrt{\sum_{} (a_{i} - b_{i})^{2}}$
  • calculated from the cartesian coordinates of the points using the Pythagorean theorem.
  • Typically, one needs to normalize the data before using this distance measure.
  • the dimensionality increases of your data, the less useful Euclidean distance becomes
• Cosine similarity: the cosine of the angle between two vectors.
  • $Dist(A, B) = \frac{\sum_{} (x_i \cdot y_i)}{\sqrt{\sum_{} x_i^2 \cdot \sum_{} y_i^2}}$
  • a way to counteract Euclidean distance’s problem with high dimensionality.
  • has the same inner product of the vectors if they were normalized to both have length one
  • The magnitude of vectors is not taken into account, merely their direction.
    • In practice, this means that the differences in values are not fully taken into account.
• Single link: the shortest distance between points
• Complete link: the largest distance between points.
• Average link: average distance between points.
• Centroid: the distance between centroids.

Weighted distance measures​

$Dist(A, B) = \sqrt{\sum_{} w_i (a_{i} - b_{i})^{2}}$

• a weight to the attributes as some attributes are more important than others.
• force clustering to pay more attention to higher weight attributes and form clusters that depend more on those heavily weighted attributes.

Dissimilarity​

• Simple matching coefficient, SMC: invariant, if the binary variable is symmetric.
  • $d(i,j) = \frac{b+c}{a+b+c+d}$
    • the proportion of mismatches (b+c) out of all attributes (a+b+c+d).
  • The simple matching coefficient is used when 0 and 1 are equally important, treating matches of both 1s and 0s the same way.
• Jaccard coefficient: non-invariant, if the binary variable is asymmetric.
  • $d(i,j) = \frac{b+c}{a+b+c}$
    • ignores cases where both are 0 (d), and only considers mismatches relative to at least one positive case.
  • The Jaccard coefficient is used when 1 (presence) is more meaningful than 0 (absence).

Similarity Matrix​

• After calculating all distances, we can create a similarity matrix
• containing the distance between each pair of data points.

• Gender: binarized
• Age: normalized
• Salary: normalized

• $dist(ID2, ID3) = \sqrt{(0-0)^2 + (0.6-0)^2 + (0.7-0)^2} = 0.92$
• $dist(ID2, ID4) = \sqrt{(0-1)^2 + (0.6-0.7)^2 + (0.7-0.8)^2} = 1.02$

Clustring methodologies​

• Hierarchical approach: create trees of clusters and sub-clusters
  • Divisive (Top-down): Start with all examples in a single cluster, and decide how to break the cluster into multiple sub-clusters.
  • Agglomerative (Bottom-up): Start with each example in its own separate cluster. Decide which clusters to merge.
• Partitional (K starting points): Start with $K$ random cluster centers, and decide which examples to put in each of the clusters.
  • Adjust the cluster centers after each allocation of examples to clusters.
  • k-means, k-medoids

Choosing a clustering method​

Clustering Terminology​

• Centroid: a point in the middle of a cluster. It may not be an actual point in the dataset.
• Medoid: an actual point in the dataset that is centrally located and is, therefore, representative of the cluster.
• Representative points: are points around the cluster that are representative of the cluster.
• High intra-class similarity: the homogeneity, the closeness of data points within a single cluster
• Low inter-class similarity: The distance between two separate clusters

• A good clustering method will produce high-quality clusters with high intra-class similarity and low inter-class similarity.

Hierarchical clustering​

• Hierarchical approaches lead to the formation of dendrograms
• The top and bottom of a dendrogram represent the two extremes of clustering
  • At the bottom, a leaf is an individual cluste
  • At the top, the root is one cluster

AGNES​

AGgglomerative NESting hierarchical clustering algorithm.

• Agglomerative hierarchical clustering follows a bottom-up approach
  • starting with clusters of single objects and merging them into bigger and bigger clusters
• agglomerative clustering process terminates (or finishes) when a termination condition is satisfied or there is only one cluster containing all objects.
• based on Euclidean distance between two objects
• steps of the algorithm:
  1. Make a cluster with only one object as member for all objects
  2. Calculate the Euclidean distance between each pair of clusters
  3. Choose the cluster pair with the smallest distance and merge them to make one cluster
  4. Repeat step 2 with the new combined cluster and the other, older clusters
  5. Repeat steps 3 and 4 until all the objects are merged into a single cluster.

DIANA​

DIvisive ANAlysis clustering algorithm.

• The top-to-bottom approach is followed in divisive hierarchical clustering
  • starts with a cluster containing all objects.
• This cluster is broken up into smaller clusters, and this process of breaking up clusters continues until each cluster contains one object or a given termination condition is satisfied.
• steps of the algorithm:
  1. The process of starts at the root with all the points as one cluster.
  2. It recursively splits higher-level clusters to build the dendrogram.
  3. It can be considered as a global approach.
  4. It is more efficient when compared with agglomerative clustering.

Single-linkage clustering​

the minimum method, connectedness, or nearest neighbour method

• two clusters are linked by a single element pair
• The distance between clusters is defined as the shortest distance from a member of the first cluster to a member of the second cluster.

Complete-linkage clustering​

the furthest neighbour method, maximum method, or diameter method.

• the distance between two clusters is defined as the greatest distance between any member of the first cluster and any member of second cluster

Average-linkage clustering​

the minimum variance method

• the distance between two clusters is calculated by averaging the distance between each member of first cluster and each member of second cluster

Data visualization​

• Successful visualization requires data be converted into a visual format.
• Motivation is to play to the strengths of people
  • for people to quickly absorb a large mount of informatin and find patterns in it.

Data visualization process​

• a human who looks at the visual and perceives information.
• the human should be able to answer some questions by looking at the visual after perception.

• Driven by Data: Explanatory visualization examples

Descirptive statistics​

• Describe some data through a quantitative summarisation of its behaviour
• Help us summarise data in a meaningful way.
• Highlight things like whether there are any values that are ill defined, or which make no sense.
• measures of central tendency
  • mean
  • median
  • mode
• measures of spread
  • range
  • variance
  • standard deviation
  • interquartile range

Inferential statistics​

• includes more advanced methods such as hypothesis tests, ANOVA, and regression.
• make claims about how general this dataset is.
• we can make inferences from a sample to a population.

Measures of central tendency​

• a quick and easy way to describe a dataset by condensing it down to just one representative value.
• can easily compare one dataset to another.
• Mean: the averge of a dataset.
• Median: the middle value in a dataset.
• Mode: the most commonly occurring value in a dataset.

Measures of spread​

• how similar or varied a set of values are for a particular variable
• summarise the data in a more detailed way that shows how scattered the values are and how much they differ from the central tendency.
• Range: the largest value of a variable and subtracts the smallest.
  • The bigger the range the more spread out a data set is.
• Variance: how far a set of numbers are spread out from their average value.
• Standard deviation: the square root of the variance
  • gives us back a value that has the same units as the mean
• Interquarile range, IQR: the difference between the upper and lower medians.
  • First, find the median of a set of data.
  • Then, find the medians of the upper and lower half of the data.

Frequency distribution​

• Frequency is the number of times a data value occurs or repeats.
• $frequency(v_i) = \frac{\text{number of objects with attribute value}\thinspace v_i}{m}$
• Visual displays that organise and present frequency counts so that the information can be interpreted more easily.
• can show absolute frequencies or relative frequencies, such as proportions or percentages.
• can be shown in a table or graph.
• Some common methods of showing frequency distributions include frequency tables, histograms or bar charts.
• Frequency tables: display the number of occurrences of a particular value or characteristic.
• Histograms: a type of graph in which each column represents a numeric variable
  • useful for describing the shape, centre and spread to better understand the distribution of the dataset.
• Bar charts: a type of graph in which each column represents a categorical variable or a discrete ungrouped numeric variable.

Vocabulary & Expressions​

RL​

$R(S_t,π(S_t),S_{t+1})$

시간 $t$에 상태 $S_t$에 있었고, 정책이 정한 행동 $π(S_t)$을 했더니, 다음 상태 $S_{t+1}$에 도착했다. 그때 받는 보상은 $R(S_t,π(S_t),S_{t+1})$이다.

• 현재 상태에서 정책이 정한 행동을 취해 다음 상태로 갔을 때 받은 보상
• $S_t$: 시간 $t$에 에이전트가 위치한 현재 상태
• $π(S_t)$: 정책 π가 현재 상태 $S_t$에서 선택한 행동 (action)
• $S_{t+1}$: 그 행동을 수행한 뒤 도달한 다음 상태
• $R$: 이 세 가지 (현재 상태, 행동, 다음 상태)에 의해 결정되는 보상 함수

Passive RL​

• Direct Utility Estimation
• ADP (Adaptive Dynamic Programming)
• TD (Temporal Difference Learning)