Vocabulary & Expressions​

Vocabulary & Expressions​

Knowledge Base​

• TELL, ASKS, TELL
  • TELLs the knowledge base what it preceives
  • ASKs the knowledge base what action it should perform
    • reasoning may be done about the current state of the world
    • about the outcomes of possible action sequences and so on
  • TELLs the knowledge base which action was chosen, and returns the action so that it can be executed
• MAKE-PERCEPT-SENTENCE
  • constructs a sentence asserting that the agent preceived the given percept at the given time.
• MAKE-ACTION-QUERY
  • constructs a sentence that asks what action should be done at the current time.
• MAKE-ACTION-SENTENCE
  • constructs a sentence asserting that the chosen action was executed.

Logical connectives​

BNF (Backus–Naur Form) grammar of sentences Symbols from Logic and Set Theory

• $\neg$ : negation (NOT), $\neg W_{1,3}$
  • A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).
• $\land$ : conjunction (AND), $W_{1,3} \land P_{3, 1}$
  • its parts are the conjuncts.
• $\lor$ : disjunction (OR), $(W_{1,3} \land P_{3,1}) \lor W_{2,2}$
  • its parts are the disjuncts.
• $\implies$ : implication (IMPLIES), $(W_{1,3} \land P_{3,1}) \implies \neg W_{2,2}$
  • its premise or antecedent, and its conclusion or consequent is the part that follows the $\implies$.
  • Implications are also called rules or if-then statements.
  • Sometimes written as $\rightarrow$ or $\supset$.
• $\iff$ : biconditional (IF AND ONLY IF), $W_{1,3} \iff \neg W_{2,2}$

Truth tables​

• Logical equivalence: $P \equiv Q$:
• Validity: a sentence is valid if it is true in all models.
  • Deduction Theorem: For any sentences $\alpha$ and $\beta$, $\alpha \models \beta$ if and only if $(\alpha \implies \beta)$ is valid.
• Satisfiability: a sentence is satisfiable if it is true in, or satisfied by, some model.
• Modus Ponens: $\frac{\alpha \implies \beta, \alpha}{\therefore \beta}$
  • whenever any sentences of the form $\alpha \implies \beta$ and $\alpha$ are given, then the sentence $\beta$ can be inferred.
• And-Elimination: $\frac{\alpha \land \beta}{\therefore \alpha}$
  • from a conjunction, one of the conjuncts can be inferred.
• monotonicity: the set of entailed sentences can only increase as information is added to the knowledge base.
  • inference rules can be applied whenever suitable premises are found in the knowledge base, regardless of what other sentences are present.

NLP​

Tokenization​

The process of dividing a text into a sequence of words.

• Different models uses different tokenization methods.

Corpus​

a large and structured collection of text

• a corpus typically consists of at least a million words of text
• at least tens of thousands of distinct vocabulary words.

Text classification​

• the process of categorizing text into organized groups.
• text classifiers can automatically analyze text and then assign a set of predefined tags or categories based on its content.
• machine learning approach
  • Features
    • BoW
    • TF-IDF
  • Features + classifier
    • Logistic regression
    • SVM
    • Naive Bayes
• Deep learning approach
  • Neural models: CNNs (capture local n-grams)
  • RNNs, LSTMs (sequence-aware)
  • Transformers (e.g. BERT)
    • Contextual embedding
• Modern enhancements
  • Embedding + classifier: Pretrained embeddings (Word2Vec) + classifier
  • Fine-tuned transformers: BERT fine-tuned

Bag of Words, BoW​

• it represents a text as a bag of its words
• we can understand the meaning of a document from its content (words) their multiplicity (frequency, number of occurrences)
• mainly used as a tool of feature extraction.
• limitations
  • ignores syntax and the context
  • disregarding grammar
  • discards word order - words are independent of each other
  • considers only the meanings of the words in the sentence

# examples

Example1 = "He likes to watch movies. Mary likes movies too."
Example2 = "Mary also likes to watch football games."

# Vocabulary
Vocab = {"He", "likes", "to", "watch", "movies", "Mary", "also", "football", "games"}

# BoW representation
BoW1 = {He: 1, likes: 2, to: 1, watch: 1, movies: 2, Mary: 1, also: 0, football: 0, games: 0}
BoW2 = {He: 0, likes: 1, to: 1, watch: 1, movies: 0, Mary: 1, also: 1, football: 1, games: 1}

[[1,2,1,1,2,1,0,0,0], [0,1,1,1,0,1,1,1,1]] 

TF-IDF​

Term Frequency - Inverse Document Frequency

• Model based on the statistics of word counts.
• idea is that key terms and important ideas are likely to repeat.
• includes a scoring function that measure the relevance of a document to a query.
  • the function takes a document with a corpus and a query as input and returns a numeric score.
  • the doucments that have the highest scores are considered as the most relevant documents.
• Term Frequency
  • $TF(q_i, d_j, D)$
• Inverse Document Frequency
  • $IDF(q_i, D) = \log\frac{N}{DF(q_i, D)}$
    • $DF(q_i, D)$: number of documents in the corpus $D$ that contain the term $q_i$
• $N = |D|$: total number of documents in the corpus $D$
• TF-IDF score
  • $TFIDF(q_i, d_j, D) = TF(q_i, d_j) \cdot IDF(q_i, D)$

Examples of TF-IDF​

• Document 1: "John likes to watch movies."
• Document 2: "Mary likes movies too."
• Document 3: "John also likes football."

Naive Bayes​

• naive refers to a very strong simplifying assumption about the features
• Conditional independence assumption
  • Given class $Y$, all the features $X = {X_1, X_2, ..., X_n}$ are assumed mutually independent.
• $P(X | Y) = P(X_1, ..., X_n | Y) = \prod_{i=1}^{n} P(X_i | Y)$
• Bayes rule
  • $P(Y | X) = \frac{P(X | Y) P(Y)}{P(X)} \propto P(Y) P(X | Y)$
  • $P(Y | X_1, ..., X_n) \propto P(Y) \prod_{i=1}^{n} P(X_i | Y)$
• Sentiment Analysis
  • $p(C_k | x_1, ..., x_n) = \frac{1}{Z} p(C_k) \prod_{i=1}^{n} p(x_i | C_k)$
    • $Z = p(x) = \sum_{k} p(C_k) p(x | C_k)$
      • scaling factor for normalization of $p(C_k | x)$
  • maximum a posteriori (MAP) decision rule
    • $\hat{y} = \argmax\limits_{k \in 1, ..., K}p(C_k) \prod_{i=1}^{n} p(x_i | C_k)$

Examples of Naive Bayes​

$P(Class | w_{1:N}) = \alpha \cdot P(Class) \cdot \prod_{j} P(w_j | Class)$

• Analyze the sentiment
  • my grandson loved it
  • $x_1 = \text{my}$, $x_2 = \text{grandson}$, $x_3 = \text{loved}$, $x_4 = \text{it}$
  • $C = {positive, negative}$
  • $\hat{y} = \argmax\limits_{k \in \{positive, negative\}} p(C_k) \cdot p(x_1 | C_k) \cdot p(x_2 | C_k) \cdot p(x_3 | C_k) \cdot p(x_4 | C_k)$
    • positive case
      • $p(positive) = 0.49$
      • $p(my | positive) = 0.30$
      • $p(grandson | positive) = 0.01$
      • $p(loved | positive) = 0.32$
      • $p(it | positive) = 0.30$
      • $p(positive | x) \propto p(positive) \cdot p(my | positive) \cdot p(grandson | positive) \cdot p(loved | positive) \cdot p(it | positive) = 0.49 \times 0.30 \times 0.01 \times 0.32 \times 0.30 = 0.00014256$
    • nagative case
      • $p(negative) = 0.51$
      • $p(my | negative) = 0.20$
      • $p(grandson | negative) = 0.02$
      • $p(loved | negative) = 0.08$
      • $p(it | negative) = 0.4$
      • $p(negative | x) \propto p(negative) \cdot p(my | negative) \cdot p(grandson | negative) \cdot p(loved | negative) \cdot p(it | negative) = 0.51 \times 0.20 \times 0.02 \times 0.08 \times 0.4 = 0.00006528$
    • $Z = p(x) = \sum_{k} p(C_k) p(x | C_k)$
      • $= p(positive) \cdot p(my, grandson, loved, it | positive) + p(negative) \cdot p(my, grandson, loved, it | negative)$
      • $= 0.00014256 + 0.00006528 = 0.00020784$
      • the probability of $x$, obtained by adding up its probabilities under each class.
    • $p(positive | x) = \frac{p(positive) \cdot p(my, grandson, loved, it | positive)}{Z} = \frac{0.00014256}{0.00020784} \approx 0.6867$
    • $p(negative | x) = \frac{p(negative) \cdot p(my, grandson, loved, it | negative)}{Z} = \frac{0.00006528}{0.00020784} \approx 0.3133$
  • Decision
    • $\hat{y} = \argmax\limits_{k \in \{positive, negative\}} \{k = positive : 0.6867, k = negative : 0.3133\}$
    • The sentiment is positive.
• Spam detection
  • Probabilities learned from data:
    • $P(\text{Spam}) = 0.4$, $P(\text{Ham}) = 0.6$
    • $P(\text{free}|\text{Spam}) = 0.8$, $P(\text{free}|\text{Ham}) = 0.1$
    • $P(\text{win}|\text{Spam}) = 0.7$, $P(\text{win}|\text{Ham}) = 0.05$
  • New document: "free win"
    • Spam score: $0.4 \times 0.8 \times 0.7 = 0.224$
    • Ham score: $0.6 \times 0.1 \times 0.05 = 0.003$
      → Classified as Spam.

N-gram model​

• N-gram: a sequence of written symbols of length n
  • unigram, bigram, trigram
• the probability of each symbol is dependent only on the n-1 previous symbols.
• $P(w_j|w_{1:j-1}) = P(w_j|w_{j-n+1:j-1})$
• $P(w_1:N) = \prod_{j=1}^{N} P(w_j|w_{1:j-1}) \approx \prod_{j=1}^{N} P(w_j|w_{j-n+1:j-1})$

Examples of N-gram​

• $W_{1:N}$ is "This article is on NLP"
  • N=5
  • Bigram (n-gram with n=2)

P("This article is on NLP")
/* full chain rule,  */
= P("This") // j = 1
  * P("article" | "This") // j = 2
  * P("is" | "This article") // j = 3
  * P("on" | "This article is") // j = 4
  * P("NLP" | "This article is on") // j = 5
/* bigram approximation */
= P("This") // j =1
  * P("article" | "This") // j = 2
  * P("is" | "article") // j = 3
  * P("on" | "is") // j = 4
  * P("NLP" | "on") // j = 5

Transformer​

• given a set of input vectors (tokens), attention lets each token look at the others and form a weighted average of them.
• The weights are data-dependent.
• The model learns the weights representing which tokens are relevant to which other tokens.

$X = \text{Input Embeddings},\qquad Q = X W_Q,\quad K = X W_K,\quad V = X W_V$

• Scores: $S = \frac{QK^T}{\sqrt{d}}$
  • dot products between every query and every key
  • the scale $\sqrt{d}$ keeps gradients stable
• Weights: $A = Softmax(S)$
  • row-wise softmax
  • each row sums to 1
• Output: $Attention(Q, K, V) = A V$
  • each output token is a weighted sum of the value vectors, with weights determined by the attention scores.(how much to pay attention to each position)
• Query (Q): What am I looking for?
• Key (K): What is the label/address of the information I have?
• Value (V): What is the actual information I want to convey?

Cross-Attention​

• look up relevant information in another sequence.
  • e.g. decoder attending to encoder outputs in translation
• $Q$ from the current sequence, $K$ and $V$ from the other sequence.
  • $Q = X_{\text{target}} W_Q, \quad K = X_{\text{source}} W_K, \quad V = X_{\text{source}} W_V$
• Cross-attention = Which source tokens are relevant to this target token?
• Self-attention = Which other tokens in this sequence are relevant to this token?
• $head_i = Attention(Q W_i^Q, K W_i^K, V W_i^V)$
• $MultiHead(Q, K, V) = Concat(head_1, ..., head_h) W_O$

Word representation​

One-hot representation​

• represents each word as a vector of length N.
• where N is the size of the vocabulary.

vocab = {he, is, singing, she, dancing, stage}

she = [0, 0, 0, 1, 0, 0]
is = [0, 1, 0, 0, 0, 0]
singing = [0, 0, 1, 0, 0, 0]

• limitations
  • incredibly inefficient for large vocabularies
  • not embed any intrinsic meaning of words
  • unable to represent similarity between likely words
  • the representation of documents is sparse vectors
    • can cause challenges in computation

Word Embedding​

• represents individual words as vectors in a low-dimensional continuous space.
• a distributed representation of a word.
• generate a unique value for each word while using smaller vectors compared with one-hot encoding.
• common vector dictionaries
  • word2vec
  • Glove (Global Vectors)

Contextual embedding​

• generates different vectors for the same word based on its context.
• the word "bank" would have different embeddings in the sentences:
  • "He went to the bank to deposit money."
  • "She sat by the river bank and enjoyed the view."
• BERT or GPT use deep neural networks to process a sequence of tokens.
• Each token's embedding is computed by considering the token itself, its position in the sequence and the surrounding tokens, context.
• captures both semantic and syntactic role in that specific context.

Part of Speech (POS) tagging​

• lexical category or tag that indicates the grammatical role of a word in a sentence.
• parts of speech allow language models to capture generalizations such as "adjectives often modify nouns" or "verbs often follow subjects".

From  the start , it  took  a   person
IN    DT  NN    , PRP VBD   DT  NN

with great qualities  to  succeed
IN   JJ    NNS        TO  VB

Example of POS tagging​

• Hidden Markov Model (HMM)
  • takes in a temproral sequence of evidence observations
  • predicts the lexical categories
• Logistic regression
  • build 45 different logistics regression models, one for each part of speech
  • ask each model how probable it is that the example word is a member of that category, given the feature values for that word in its particular context.

Machine translation​

• translate a sentence from a source lnaguae to a trget language.
• train an MT model: a large corpus of source/target sentence paris and hope that the trained MT model can accurately translate new sentences.
• want to generate a target language sentence that corresponds to the source language sentence
• the geneartion of each target word is conditional on the entire source sentence and on all previously generated target words.

Example of machine translation​

• a sequance-to-sequence model
  • use two RNNs (LSTM)
• attentional sequence-to-sequence model
  • use attentino to create a context-based summarization of the source sentence into a fixed-dimension representation
• transformer-based model
  • encoder: reads the source sentence and turns it into a rich, contextual set of vectors.
  • decoder: generates the target sentence one token at a time, using what it has generated so far and the encoder's representations.

Text generation​

• a subfield of NLP
• leverages knowledge in computational linguistics and AI to automatically generate natural language texts
• can satisfy certain communicativa requirements

Example of text generation​

• Classifier based on word embeddings, e.g. RNN and LSTM
  • RNN: each input word is encoded as a word embedding vector $x_i$, a hidden layer $z_t$, the classes are the words of the vocabulary
    • the output $y_t$ will be a softmax probability distribution over the possible values of the next word in the sentence.
  • LSTM: can choose to remember som parts of the input, copying it over to the next time step, and to forget toher parts.
• Pre-trained languaeg model using deep learning
  • BERT
  • GPT-X, Generativ ePre-trained Transformer

Transfer learning​

• experience with one learning task helps an agent learn better on another task.
• pretraining: a form of transfer learning in which we use a large amount of shared general-domain language data to train an initial version of an NLP model.
  • we can use a smaller amount of domain-specific data to refine the model
  • the refined model can learn the vocabulary, idioms, syntactic structure, and other linguistic phenomena that are specific to the new domain.
• For NN, learning consist of adjusting weight, so the most plausible approach for transfer learning is to copy over the weights learned for task A to a network that will be trained for task B.
  • The weights are then updated by gradient descent in the usual way using data for task B.
• the popularity of transfer learning is the availability of high-quality pretrained models.
• will want to freeze the first few layers of the pretrained model
  • these layers serve as feature detectors that will be useful for new model.
  • new data set will be allowed to modify the parameters of the higher levels only
    • these are the layers that identify problem-specific features and do classification.

Linear Separability​

• the data is linearly separable if
  • it can be separated by a point on a single dimension line of data points
  • by a line on a two-dimensional representation of data points
  • by a plane (a two-dimensional surface) in a three-dimensional representation of the data points
• If it is non-linearly separable, look at other options for classification.

Hyperplane​

• the conceptual divide between data
• Weight vector: represented and generated in weight space.
• Choosing the hyperplane
  • Minimum distance between samples
  • Least-squares method
  • Gradient Descent

Artificial Neural Networks, ANN​

• Strength: for high dimensionality problems, the complex relations between variables
• Weaknesses: theoretically complex, computationally intensive, needs large data sets, complicated to implement
• Kinds of ANN
  • Perceptrons, Multilayer Perceptrons
  • Deep learning neural networks
  • Kohonen networks
  • Convolutional neural networks
  • Radial Basis Functions
  • Recurrent neural networks
  • Support Vector Machines
  • Competitive learning
  • Boltzmann machines

Multilayer Perceptrons, MLP​

• Challenges
  • Decide on the network topology.
    • how many hidden layers are needed
    • how many neurons in each of the hidden layers
  • Find values for the weights which make the network produce the correct output values for the given input values.
• Neural networks only accept numeric data.
  • need to convert the categorical into numeric.
  • One-Hot encoding, Thermometer encoding.
• high values may need to be scaled into a similar range as neural networks
  • need to do a log transform to pull the values into a target range.
  • [-1, +1] or [0, 1]
• input neurons should be as small as possible.
  • adding neurons -> more parameters and weights -> amplify any bias. (overtrain the network)
• one categorical attribute may have many attribute values
  • each adding a parameter -> adding risk of overtraining

Resilient Propagation, RProp​

• directly adjust the weight step based on the local gradient information
• introduces a weight update value $u_{ij}$ for each weight $w_{ij}$
• updates it based on the sign of the partial derivative of the error with respect to the weight
• update value $u_{ij}$
  • if sign changes (i.e. jumped over local minima) -> $u_{ij}$ slightly decreased.
  • if sign remains the same -> $u_{ij}$ slightly increased.
• weight $w_{ij}$
  • if derivative is $+ve$ (i.e. error increasing) -> $w_{ij}$ decreased by $u_{ij}$
  • if the derivative is negative (i.e. error decreasing) -> $w_{ij}$ increased by $u_{ij}$
  • if the derivative changes sign, the last weight update is reverted. (backtracks the last weight update)

KNIME​

• RProp MLP Learner + MultiLayerPerceptron Predictor
• MultilayerPerceptron + Weka Predictor (back propagation with momentum)

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​