Table of content:
- What is XYZ?
- Basic terms
- What is loss, cost, objective function?
- Loss function
- Cost function
- Objective function
- What is the loss function of linear regression?
- What is the loss function of logistic regression?
- Optimization of model
- What is imbalance data?
- What are metrics to evaluate a model for imbalance data
- Cost function based approaches
- Sampling based approaches
- Hybrid approach
- What is Anomaly Detection?
- What is Receiver Operating Characteristics (ROC) curve?
- What is the area under the curve (AUC)?
- What is p value?
- What is TF-IDF?
- What is Bias?
- What is Variance?
- What is Bias-Variance tradeoff?
- What is Recurrent Neural Networkn (RNN)?
- What are main gates in Long Short-Term Memory (LSTM)?
- What is (Support Vector Machine) SVM?
- What is Entropy in discrete?
- What is Cross Entropy in discrete?
- What is the difference between Cross Entropy and Entropy?
- What is Post-of-Speech (POS) Tagging in NLP?
- What is Conditional Random Field?
- What is Viterbi algorithm
- What is Jaccard Similarity
- What is MinHash
- What is Locality Sensitive Hashing(LSH)
- What is Shingling
What is XYZ?
Understand some foundational terms in machine learning area will help you to speed up the communication with experts. There are some famous terms you have to know.
What is loss, cost, objective function?
These are not very strict terms and they are highly related. However: In short, a loss function is a part of a cost function which is a type of an objective function.
From section 4.3 in “Deep Learning” - Ian Goodfellow, Yoshua Bengio, Aaron Courville http://www.deeplearningbook.org/ The function we want to minimize or maximize is called the objective function, or criterion. When we are minimizing it, we may also call it the cost function, loss function, or error function.
A loss function is a way to map the performance of our model into a real number. It measures how well the model is performing its task.
It is usually a function defined on a data point, prediction and label, and measures the penalty. For example: square loss , used in linear regression hinge loss , used in SVM 0/1 loss , used in theoretical analysis and definition of accuracy
It is usually more general. It might be a sum of loss functions over your training set plus some model complexity penalty (regularization). For example: Mean Squared Error SVM cost function (there are additional constraints connecting ξi with C and with training set)
It is the most general term for any function that you optimize during training. For example, a probability of generating training set in maximum likelihood approach is a well defined objective function, but it is not a loss function nor cost function (however you could define an equivalent cost function). For example: MLE is a type of objective function (which you maximize) Divergence between classes can be an objective function but it is barely a cost function, unless you define something artificial, like 1-Divergence, and name it a cost
What is the loss function of linear regression?
Mean Squared Error, or L2 loss. Given our simple linear equation y=mx+b, we can calculate MSE as:
N is the total number of data
is the actual data
is our prediction
def MSE(yHat, y): return np.sum((yHat - y)**2) / y.size
What is the loss function of logistic regression?
In binary classification, where the number of classes M equals 2, cross-entropy can be calculated as:
M - number of classes (dog, cat, fish)
log - the natural log
y - binary indicator (0 or 1) if class label
c is the correct classification for observation o
p - predicted probability observation o is of class c
def CrossEntropy(yHat, y): if y == 1: return -log(yHat) else: return -log(1 - yHat)
Optimization of model
What is L1 regularizer?
A regression model that uses L1 regularization technique is called Lasso Regression.
Lasso Regression (Least Absolute Shrinkage and Selection Operator) adds “absolute value of magnitude” of coefficient as penalty term to the loss function. Lasso shrinks the less important feature’s coefficient to zero thus, removing some feature altogether. So, this works well for feature selection in case we have a huge number of features.
What is L2 regularizer?
A regression model which uses L2 is called Ridge Regression.
Ridge regression adds “squared magnitude” of coefficient as penalty term to the loss function.
What is imbalance data?
Reference: imbalanced data
Imbalanced data typically refers to a classification problem where the number of observations per class is not equally distributed; often you’ll have a large amount of data/observations for one class (referred to as the majority class), and much fewer observations for one or more other classes (referred to as the minority classes)
Two common ways we’ll train a model: tree-based logical rules developed according to some splitting criterion, and parameterized models updated by gradient descent.
It’s worth noting that not all datasets are affected equally by class imbalance. Generally, for easy classification problems in which there’s a clear separation in the data, class imbalance doesn’t impede on the model’s ability to learn effectively. However, datasets that are inherently more difficult to learn from see an amplification in the learning challenge when a class imbalance is introduced.
What are metrics to evaluate a model for imbalance data
Accuracy is not a good metrics for imbalance data. The model always predict the negative (majority) cases will get high accuracy.
Below are better metrics:
TP (True Positive), FP (False Positive), TN (True Negative), FN
Precision and recall
We can roughly classify the approaches into three major categories: cost function based approaches, sampling based approaches and turning the task to Anomaly detections.
Cost function based approaches
One of the simplest ways to address the class imbalance is to simply “provide a weight for each class” which places more emphasis on the minority classes such that the end result is a classifier which can learn equally from all classes.
The intuition behind cost function based approaches is that if we think one false negative is worse than one false positive, we will count that one false negative as, e.g., 100 false negatives instead. For example, if 1 false negative is as costly as 100 false positives, then the machine learning algorithm will try to make fewer false negatives compared to false positives (since it is cheaper).
Sampling based approaches
Another approach towards dealing with a class imbalance is to simply alter the dataset to remove such an imbalance.
This can be roughly classified into three categories:
Oversampling, by adding more of the minority class so it has more effect on the machine learning algorithm
Undersampling, by removing some of the majority class so it has less effect on the machine learning algorithm
Hybrid, a mix of oversampling and undersampling
Oversampling the minority classes to increase the number of minority observations until we’ve reached a balanced dataset.
The most naive method of oversampling is to randomly sample the minority classes and simply duplicate the sampled observations. With this technique, it’s important to note that you’re artificially “reducing the variance” of the dataset.
Synthetic Minority Over-sampling Technique (SMOTE)
SMOTE is a technique that generates new observations by interpolating between observations in the original dataset.
For a given observation , a new (synthetic) observation is generated by interpolating between one of the k-nearest neighbors, .
where λ is a random number in the range [0,1]. This interpolation will create a sample on the line between and .
This algorithm has three options for selecting which observations, , to use in generating new data points.
regular: No selection rules, randomly sample all possible .
borderline: Separates all possible into three classes using the k nearest neighbors of each point.
a. noise: all nearest-neighbors are from a different class than
b. in danger: at least half of the nearest neighbors are of the same class as
c. safe: all nearest neighbors are from the same class as
svm: Uses an SVM classifier to identify the support vectors (samples close to the decision boundary) and samples from these points.
Adaptive Synthetic (ADASYN)
Adaptive Synthetic (ADASYN) sampling works in a similar manner as SMOTE, however, the number of samples generated for a given is proportional to the number of nearby samples which “do not” belong to the same class as . Thus, ADASYN tends to focus solely on outliers when generating new synthetic training examples.
To achieve class balance by undersampling the majority class - essentially throwing away data to make it easier to learn characteristics about the minority classes.
A naive implementation would be to simply sample the majority class at random until reaching a similar number of observations as the minority classes.
For example, if your majority class has 1,000 observations and you have a minority class with 20 observations, you would collect your training data for the majority class by randomly sampling 20 observations from the original 1,000. As you might expect, this could potentially result in removing key characteristics of the majority class.
The general idea behind near miss is to only the sample the points from the majority class necessary to distinguish between other classes.
Select samples from the majority class for which the average distance of the N closest samples of a minority class is smallest.
Select samples from the majority class for which the average distance of the N farthest samples of a minority class is smallest.
NearMiss-3 is a 2-steps algorithm. First, for each negative sample, their M nearest-neighbors will be kept. Then, the positive samples selected are the one for which the average distance to the N nearest-neighbors is the largest.
Tomek’s link exists if two observations of different classes are the nearest neighbors of each other.
We’ll remove any observations from the majority class for which a Tomek’s link is identified
Depending on the dataset, this technique won’t actually achieve a balance among the classes - it will simply “clean” the dataset by removing some noisy observations, which may result in an easier classification problem.
Most classifiers will still perform adequately for imbalanced datasets as long as there’s a clear separation between the classifiers. Thus, by focusing on removing noisy examples of the majority class, we can improve the performance of our classifier even if we don’t necessarily balance the classes.
Edited nearest neighbors
Edited Nearest Neighbors applies a nearest-neighbors algorithm and “edit” the dataset by removing samples which do not agree “enough” with their neighborhood.
For each sample in the class to be under-sampled, the nearest-neighbors are computed and if the selection criterion is not fulfilled, the sample is removed.
This is a similar approach as Tomek’s links in the respect that we’re not necessarily focused on actually achieving a class balance, we’re simply looking to remove noisy observations in an attempt to make for an easier classification problem.
By combining undersampling and oversampling approaches, we get the advantages but also drawbacks of both approaches as illustrated above, which is still a tradeoff.
What is Anomaly Detection?
When you positive data is extremely small (2~20 or less than 50), throw away minority examples and switch to an anomaly detection framework. Assume you have 10000 data, only 20 positive data. You can select 6000 negative data to form a training set. Leverage gaussian distribution on each feature to form a probability model. Then set up an error probability = e, then P() < e will be an anomaly case. Assume each feature are independent and its values fellow gaussian distribution.
P(X) = P(; ; ) * P(; ; ) * … * P(; ; )
We can plot histogram for each feature to verify its distribution. If it does not follow gaussian distribution, we need to transform the feature to new feature.
What is Receiver Operating Characteristics (ROC) curve?
Reference: imbalanced data
An ROC curve visualizes an algorithm’s ability to discriminate the positive class from the rest of the data. We’ll do this by plotting the True Positive Rate against the False Positive Rate for varying prediction thresholds.
What is the area under the curve (AUC)?
Reference: imbalanced data
The area under the curve (AUC) is a single-value metric for which attempts to summarize an ROC curve to evaluate the quality of a classifier. This metric approximates the area under the ROC curve for a given classifier. The ideal curve hugs the upper left hand corner as closely as possible, giving us the ability to identify all true positives while avoiding false positives; this ideal model would have an AUC of 1. On the flipside, if your model was no better than a random guess, your TPR and FPR would increase in parallel to one another, corresponding with an AUC of 0.5.
What is p value?
The P value, or calculated probability, is the probability of finding the observed, or more extreme, results when the null hypothesis () of a study question is true – the definition of ‘extreme’ depends on how the hypothesis is being tested. P is also described in terms of rejecting when it is actually true, however, it is not a direct probability of this state.
What is TF-IDF?
Term Frequency–Inverse Document Frequency
Term Frequency also known as TF measures the number of times a term (word) occurs in a document.
The inverse document frequency is a measure of how much information the word provides, that is, whether the term is common or rare across all documents.
- N: total number of documents in the corpus N = |D|
- : number of documents where the term t appears. if the term is not in the corpus, this will lead to a division-by-zero. It is therefore common to adjust the denominator to 1+
What is Bias?
The bias of an estimator to a statistic model is:
is the true underlying value of used to define the data generating distribution.
is the expectation over the data (seen as samples from a random variable) by an estimator .
In a simulation experiment concerning the properties of an estimator, the bias of the estimator may be assessed using the mean signed difference (ignore the noise for estimation purpose).
Mean Signed Difference, Deviation or Error (MSD)
The bias is an error from erroneous assumptions in the learning algorithm. High bias can cause an algorithm to miss the relevant relations between features and target outputs (underfitting).
Bias occurs when an algorithm has limited flexibility or is not complex enough produce underfit model that can’t learn the true signal from a dataset.
High bias, low variance algorithms train models that are consistent, but inaccurate on average. Small gap between training and test error but unacceptable high training error in high bias cases.
Try a larger set of features, less regularization, unpruned trees, small-k KNN to fix high bias/small variance issue.
What is Variance?
The variance is an error from sensitivity to small fluctuations in the training set. High variance can cause an algorithm to model the random noise in the training data, rather than the intended outputs (overfitting).
The variance of an estimator is simply the variance
(Machine Learning usually uses biased Variance)
(Statistic usually uses unbiased Variance)
Alternately, the square root of the variance is called the standard error, denoted .
Variance refers to an algorithm’s sensitivity to specific sets of training data. Algorithms are too complex produce overfit models that memorize the noise instead of the signal.
High variance, low bias algorithms train models that are accurate on average, but inconsistent. Test error still decreasing as training set size increase but large gap between training and test error. Suggests larger training set will help.
Try to get more training examples, highly regularized, highly pruned decision, large K KNN or try a smaller set of features to fix high variance/small bias issue.
What is Bias-Variance tradeoff?
To get good predictions, you’ll need to find a balance of bias and variance that minimizes “total error”.
What is Bias-Variance decomposition of error?
Assume that where and , we can derive an expression for the expected prediction error of a regression fit at an input point , using squared-error loss:
Irreducible error is “noise” that can’t be reduced by algorithm. It can sometimes be reduced by better data cleaning.
Low variance algorithms tend to be less complex, with simple or rigid underlying structure.
Regression, Naive Bayes, Linear algorithms, parametric algorithms.
Low bias algorithms tend to be more complex, with flexible underlying structure.
Decision trees, nearest neighbors, non-linear algorithms, non-parametric algorithms.
A proper machine learning workflow finds that optimal balance.
- Separate training and test sets.
- Trying appropriate algorithms
- Fitting model parameters
- Tunning impactful hyperparameters
- Proper performance metrics
- Systematic cross-validation
–Variance: Training error will be much lower than test error.
–Bias: Training error will also be high.
What is Recurrent Neural Networkn (RNN)?
A recurrent neural network (RNN) is a class of artificial neural network where connections between nodes form a directed graph along a sequence. This allows it to exhibit dynamic temporal behavior for a time sequence. This allows it to exhibit dynamic temporal behavior for a time sequence. RNNs can use their internal state (memory) to process sequences of inputs.
In other neural networks, all the inputs are independent of each other. But in RNN, all the inputs are related to each other. RNNs are called recurrent because they perform the prediction task for every element of a sequence, with the output being depended on the previous computations.
What are main gates in Long Short-Term Memory (LSTM)?
Long short-term memory (LSTM) units are units of a recurrent neural network (RNN). An RNN composed of LSTM units is often called an LSTM network. A common LSTM unit is composed of a cell, an input gate, an output gate and a forget gate. The cell remembers values over arbitrary time intervals and the three gates regulate the flow of information into and out of the cell.
What is (Support Vector Machine) SVM?
SVM is supervised learning models with associated learning algorithms that analyze data used for classification and regression analysis.
If the training data is linearly separable, we can select two parallel hyperplanes that separate the two classes of data, so that the distance between them is as large as possible. The region bounded by these two hyperplanes is called the “margin”, and the maximum-margin hyperplane is the hyperplane that lies halfway between them.
An important consequence of this geometric description is that the max-margin hyperplane is completely determined by those which lie nearest to it. These are called support vectors.
To extend SVM to cases in which the data are not linearly separable, we introduce the hinge loss function:
is the current output.
If lies on the correct side of the margin, the loss function is zero.
Note that $y_i$ is the ith target(i.e., in this case, 1 or -1), and
We then wish to minimize
where the parameter determines the tradeoff between increasing the margin-size and ensuring that the lie on the correct side of the margin.
What is Entropy in discrete?
What is Cross Entropy in discrete?
or by definition:
What is the difference between Cross Entropy and Entropy?
The KL divergence from (or Q, your observation) to y (or P, ground truth) is simply the difference between cross entropy and entropy:
What is Post-of-Speech (POS) Tagging in NLP?
How to do the POS tagging?
Use of hidden Markov models
Dynamic programming methods
Other taggers and methods
include the Viterbi algorithm, Brill tagger, Constraint Grammar, and the Baum-Welch algorithm (also known as the forward-backward algorithm)
Hidden Markov model and visible Markov model taggers can both be implemented using the Viterbi algorithm.
What is the loss function in mathematics?
What is Conditional Random Field?
Reference: Overview of Conditional Random Fields