Tutorial About Probabilistic Classification Models
Benjamin Adrian, Gunnar Grimnes, Jörn Hees, Matthias Sperber
Abstract
Introduction
Classification in general is the problem of deciding for a given input to which class it belongs. Usually classification can be subdivided into a learning phase (aka training phase) and a classification phase (aka test phase). (TODO: offline, online, reinforcement, ... learning)
Basics
There are several basics to concern and understand before diving into probabilistic learning models.
Example / Instance
Examples or also called instances are the basic entities in this field. They occur as training examples, as validation or test examples, and finally as real data.
E.g., In a document classification scenario, examples are documents. Already classified documents are used for training or evaluation purpose.
Feature
A feature is a descriptive property of an example. Features are processible by machines.
E.g., In a document classification scenario, features might be the words of a document. In consequence, single features might describe multiple examples (here documents)
Feature Extraction
Feature extraction is the task of extracting features from examples.
E.g., In our document classification scenario, a tokenizer that extracts words from text might be used for feature extraction.
In more sophisticated scenarios, feature extraction can be hierarchically nested by extracting new features from existing feature lists.
E.g., In our document classification scenario, a word n-gram algorithm extracts n-gram features from extracted word sequences.
Feature Selection
Each feature for each example has be processed by model trainers or executors. There are several reasons for selecting just subsets of existing features. First, not all features are useful for separating different classes. In details, there is no statistically significant dependency between class and feature occurance.
E.g., In our document classification scenario, stop words or high frequent words are not useful for separating e.g., spam mails from ham mails.
Second, just a small set of features might be enough for classifiying examples successfully. Adding more just decreases performance.
Main Steps
- Convert your problem into a classification problem
- Get a pre-classified data set (the more data or even data sets the better). Devide it into test, training and development sets.
- Think about your features. This is the most important step!
- Process data, extract these features, select significant ones and store them.
- Train your model with your training data
- Classify your test data.
- Evaluate results
Relational Classification
Relational data consists of entities, described by features and statisitcal dependencies between entities.
Nearest Neighbor (1-NN or NN)
Nearest Neighbor classifiers are classifiers of the most simple kind. In the training phase they simply record the class for each sample. Later in the classification phase they calculate the distances of the query to all samples in their records and return the class of the sample which is closest to the query.
$k$NN
The $k$-Nearest Neighbor classifier is a generalization of the simple NN, which does not immediately return the single "best match" sample's class, but inspects the nearest $k$ samples to the query and returns a class depending on a merging function, such as:
- most often observed class
- classes weighted by inverse distances
Naive Bayes
Naive Bayes Classificators are
Maximum Entropy
Multi Layer Perceptrons
Support Vector Machines
Sequential Classification
Hidden Markov Model
Conditional Random Field
A conditional random field is a conditional distribution
with an associated graphical structure.
