Discriminative model

Machine learning and data mining
Problems Classification Clustering Regression Anomaly detection AutoML Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Expectation–maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection k-NN Local outlier factor
Artificial neural networks Autoencoder Deep learning DeepDream Multilayer perceptron RNN LSTM GRU) Restricted Boltzmann machine SOM Convolutional neural network U-Net
Reinforcement learning Q-learning SARSA Temporal difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues NIPS ICML ML JMLR ArXiv:cs.LG
Glossary of artificial intelligence Glossary of artificial intelligence
Related articles List of datasets for machine-learning research Outline of machine learning
Machine learning portal

Discriminative models, also referred to as conditional models, are a class of models used in statistical classification, especially in supervised machine learning. A discriminative classifier tries to model by just depending on the observed data while learning how to do the classification from the given statistics. The approaches used in supervised learning can be categorized into discriminative models or generative models. Comparing with the generative models, discriminative model makes fewer assumptions on the distributions but depends heavily on the quality of the data. For example, given a set of labeled pictures of dog and rabbit, discriminative models will be matching a new, unlabeled picture to a most similar labeled picture and then give out the label class, a dog or a rabbit. However, generative will develop a model which should be able to output a class label to the unlabeled picture from the assumption they made, like all rabbits have red eyes.The typical discriminative learning approaches include Logistic Regression(LR), Support Vector Machine(SVM), conditional random fields(CRFs) (specified over an undirected graph), and others. The typical generative model approaches contain Naive Bayes, Gaussian Mixture Model, and others.

Definition

Unlike the generative modelling, which studies from the joint probability $P(x,y)$, the discriminative modeling studies the $P(y|x)$or the direct maps the given unobserved variable (target) $x$ a class label $y$ depended on the observed variables (training samples). In practical field of object recognition, $x$is likely to be a vector (i.e. raw pixels, features extracted from image or so). Within a probabilistic framework, this is done by modeling the conditional probability distribution $P(y|x)$, which can be used for predicting $y$ from $x$. Note that there is still distinction between the conditional model and the discriminative model, though more often they are simply categorised as discriminative model.

Pure Discriminative Model vs. Conditional Model

Conditional Model models the conditional probability distribution while the traditional discriminative model aims to optimize on mapping the input around the most similar trained samples.

Typical Discriminative Modelling Approaches

The following approach is based on the assumption that it is given the training data-set $D=\{(x_{i};y_{i})|i\leq N\in \mathbb {Z} \}$, where $y_{i}$is the corresponding output for the input $x_{i}$.

Linear Classifier

We intend to use the function $f(x)$to simulate the behavior of what we observed from the training data-set by the Linear Classifier method. Using the joint feature vector $\phi (x,y)$, the decision function is defined as:

$f(x,w)=\arg max_{y}w^{T}\phi (x,y)$

According to Memisevic's interpretation, $w^{T}\phi (x,y)$, which is also $c(x,y;w)$, computes a score which measures the computability of the input $x$with the potential output $y$. Then the $\arg max$determines the class with the highest score.

Logistic Regression (LR)

Since the 0-1 loss function is a commonly used one in the decision theory, the conditional probability distribution $P(y|x;w)$, where $w$is a parameter vector for optimizing the training data, could be reconsidered as following for the logistics regression model:

$P(y|x;w)={\frac {1}{Z(x;w)}}\exp(w^{T}\phi (x,y))$, with

$Z(x;w)=\textstyle \sum _{y}\displaystyle \exp(w^{T}\phi (x,y))$

The equation above is the Logistic Regression. Notice that a major distinction between models is their way of introducing posterior probability. Posterior probability is inferred from the parametric model. We then can maximize the parameter by following equation:

$L(w)=\textstyle \sum _{i}\displaystyle \log p(y^{i}|x^{i};w)$

It could also be replaced by the log-loss equation below:

$l^{\log(}x^{i},y^{i},c(x^{i};w))=-\log p(y^{i}|x^{i};w)=\log Z(x^{i};w)-w^{T}\phi (x^{i},y^{i})$

Since the log-loss is differentiable, gradient-based method is a possible way to optimize the model. Global optimum is guaranteed because the objective function is convex. Gradient of log likelihood is represented by:

${\frac {\partial L(w)}{\partial w}}=\textstyle \sum _{i}\displaystyle \phi (x^{i},y^{i})-E_{p(y|x^{i};w)}\phi (x^{i},y)$

where $E_{p(y|x^{i};w)}$is the expectation of $p(y|x^{i};w)$.

The above method will provide efficient computation for the relative small number of classification.

Support Vector Machine

Another continuous (but not differentiable) alternative to the 0/1-loss is the ’hinge-loss’, which can be defined as the following equation

$l^{hinge}(x^{i},y^{i},c(x^{i},y^{i},w))=max_{y}(w^{T}\phi (x^{i}+y)+l^{0/1}(x^{i},y^{i},c(x^{i};w)))-w^{T}\phi (x^{i},y^{i}).$

The hinge loss measures the difference between the maximal confidence that the classifier has over all classes and the confidence it has in the correct class. In computing this maximum, all wrong classes get a ’head start’ by adding 1 to the confidence. As a result, the hinge loss is 0 if the confidence in the correct class is by at least 1 greater than the confidence in the closest follow-up. Even though the hinge-loss is not differentiable, it can also give rise to a tractable variant of the 0/1- loss based learning problem, since the hinge-loss allows it to recast to the equivalent constrained optimization problem.

Contrast with Generative Model

Contrast in Approaches

Let's say we are given the $m$ class labels(classification) and $n$feature variables, $Y:\{y_{1},y_{2},\ldots ,y_{m}\},X:\{x_{1},x_{2},\ldots ,x_{n}\}$, as the training samples.

Generative model takes the joint probability $P(x,y)$, where $x$ is the input and $y$ is the label, and predicts the most possible known label ${\widetilde {y}}\in Y$ for the unknown variable ${\widetilde {x}}$ using Bayes Rules.

Discriminative models, as opposed to generative models, do not allow one to generate samples from the joint distribution of observed and target variables. However, for tasks such as classification and regression that do not require the joint distribution, discriminative models can yield superior performance (in part because they have fewer variables to compute). On the other hand, generative models are typically more flexible than discriminative models in expressing dependencies in complex learning tasks. In addition, most discriminative models are inherently supervised and cannot easily support unsupervised learning. Application-specific details ultimately dictate the suitability of selecting a discriminative versus generative model.

Discriminative models and generative models also differ in introducing the posterior possibility. To maintain the least expected loss, the minimization of result's misclassification should be acquired. In the discriminative model, the posterior probabilities, $P(y|x)$, is inferred from a parametric model, where the parameters come from the training data. Points of estimation of the parameters are obtained from the maximization of likelihood or distribution computation over the parameters. On the other hand, considering that the generative models focus on the joint probability, the class posterior possibility $P(k)$ is considered in Bayes' Theorem, which is $P(y|x)={\frac {p(x|y)p(y)}{\textstyle \sum _{i}p(x|i)p(i)\displaystyle }}={\frac {p(x|y)p(y)}{p(x)}}$.

Advantages vs. Disadvantages in Application

In the repeated experiments, Logistics Regression and Naive Bayes are applied here for different models on binary classification task, discriminative learning results lower asymptotic errors, while generative one results in higher asymptotic errors faster. However, in Ulusoy and Bishop's joint work, Comparison of Generative and Discriminative Techniques for Object Detection and Classification, they state that the above statement is true only when the model is the appropriate one for data (i.e.the data distribution is correctly modeled by the generative model).

Advantages

Significant advantages of using discriminative modeling are:

• Higher accuracy, which mostly leads to better learning result.
• Allows simplification of the input and provides a direct approach to $P(y|x)$
• Saves calculation resource
• Generates lower asymptotic errors

Compared with the advantages of using generative modeling:

• Takes all data into consideration, which could result in slower processing as a disadvantage
• Requires less training samples
• A flexible framework that could easily cooperate with other needs of the application

Disadvantages

• Training method usually requires multiple numerical optimization techniques
• Similarly, by the definition, the discriminative model will need the combination of multiple subtasks for a solving complex real-world problem

Optimizations in Applications

Since both advantages and disadvantages present on the two way of modeling, combining both approaches will be a good modeling in practice. For example, in Marras' article A Joint Discriminative Generative Model for Deformable Model Construction and Classification, he and his coauthors apply the combination of two modelings on face classification of the models, and receive a higher accuracy than the traditional approach.

Similarly, Kelm also proposed the combination of two modelings for pixel classification in his article Combining Generative and Discriminative Methods for Pixel Classification with Multi-Conditional Learning.

During the process of extracting the discriminative features prior to the clustering, Principal Component Analysis(PCA), though commonly used, is not a necessarily discriminative approach. In contrast, LDA is a discriminative one. Linear discriminant analysis(LDA), provides an efficient way of eliminating the disadvantage we list above. As we know, the discriminative model needs a combination of multiple subtasks before classification, and LDA  provides appropriate solution towards this problem by reducing dimension.

In Beyerlein's paper, DISCRIMINATIVE MODEL COMBINATION, the discriminative model combination provides a new approach in auto speech recognition. It not only helps to optimize the integration of various kinds of models into one log-linear posterior probability distribution. The combination also aims at minimizing the empirical word error rate of training samples.

In the article, A Unified and Discriminative Model for Query Refinement, Guo and his partners use a unified discriminative model in query refinement using linear classifier, and successfully obtain a much higher accuracy rate. The experiment they design also consider generative model as a comparison with the unified model. Just as expected in the real-world application, the generative model perform the poorest comparing to the other models, including the models without their improvement.

Types

Examples of discriminative models used in machine learning include:

• Logistic regression, a type of generalized linear regression used for predicting binary or categorical outputs (also known as maximum entropy classifiers)
• Support vector machines
• Boosting (meta-algorithm)
• Conditional random fields
• Linear regression
• Neural networks
• Linear Discriminant Analysis (The result could be used as a linear classifier.)
• Random forests
• Perceptrons

See also

• Generative model