Hidden Markov Model -Based Sequence Classifiers in C#

hmm-2-5B3-5D

Distinct Hidden Markov Models can be trained individually on data obtained from each class of a classification problem. If we create a set of those models and specialize each model to recognize each of the separate classes, we can then use the HMMs ability to calculate the likelihood that a given sequence belongs to the model to determine the most likely class of an unknown sequence. 

This post is a continuation for the previous
article, Hidden Markov Models in C#.

 

The code presented here is also part of the Accord.NET Framework. The Accord.NET Framework is a framework for developing machine learning, computer vision, computer audition, statistics and math applications. It is based on the already excellent AForge.NET Framework. Please see the starting guide for mode details. The latest version of the framework includes the latest version of this code plus many other statistics and machine learning tools.

Introduction

Hidden Markov Models

An introduction about Hidden Markov Models (HMM) was presented in a previous article, entitled Hidden Markov Models in C#. HMMs are models are stochastic methods to model temporal and sequence data.

They allow, among other things, (1) to infer the most likely sequence of states that produced a given output sequence, to (2) infer which will be the most likely next state (and thus predicting the next output) and (3) calculate the probability that a given sequence of outputs originated from the system (allowing the use of hidden Markov models for sequence classification). In the context of this article, we will be more interested in results from ability (3).

Summary for Hidden Markov Models

 

Hidden Markov Models can be seem as finite state machines where for each sequence unit observation there is a state transition and, for each state, there is a output symbol emission. The picture on the left summarizes the overall definition of a HMM given in the previous article.

 

 

Hidden Markov Model -Based Sequence Classifier

Hidden Markov Models can be trained individually on data obtained from each class of a classification problem. If we create a set of models and specialize each model to recognize each of the separated classes, then we will be able to explore the HMMs ability to calculate the likelihood that a given sequence belongs to itself to perform classification of discrete sequences.

After all models have been trained, the probability of the unknown-class sequence can be computed for each model. As each model specialized in a given class, the one which outputs the highest probability can be used to determine the most likely class for the new sequence, as shown in the picture below.

Evaluation structure for a classifier based on Hidden Markov Models

Schematic representation of the sequence classification procedure.

 

Source Code

The implementation is very straightforward, as shown in the picture below. The Tag property of the HiddenMarkovModel class can be used to store additional information about which class the model will be representing.

Class diagram for HMM-based sequence classifierClass diagram for the HMM-based sequence classifier.

Computing the most likely class for a given sequence

Computing the most likely class for a given sequence is as simple as iterating through all models in the set and selecting the one which has produced the highest likelihood value.

 

Training each model to recognize each of the output classes

To train each model to recognize each of the output classes we have to split the training data into subsets whose outputs corresponds to each of the classes from the classification problem.

 

Using the Code

Code usage is very simple. Once one has the input data available in the form of a sequence array and output data in form of a integer array, create a new HiddenMarkovClassifier object with the appropriate parameters.

Then, just call Learn() passing the input and output data and the convergence limit for the learning algorithm. After that, call Compute() passing a new integer sequence to be classified by the system.

 

Sample Application

The accompanying sample application can read Excel spreadsheets containing integer sequences and labels for those sequences. An example spreadsheet contained inside the Resources folder in the compressed archive file demonstrates the expected format for this data.

Hidden Markov Model - Accord.NET Hidden Markov Model - Accord.NET

Left: Input sequences data. Right: Hidden Markov Models contained in the Sequence Classifier with initial configurations.

Hidden Markov Model - Accord.NET Hidden Markov Model - Accord.NET

Left: Trained models. Right: Performance test for the Hidden Markov Model Sequence Classifier.

 

See also

 

References

Hidden Markov Models in C#

hmm_thumb-5B5-5D

Hidden Markov Models (HMM) are stochastic methods to model temporal and sequence data. They are especially known for their application in temporal pattern recognition such as speech, handwriting, gesture recognition, part-of-speech tagging, musical score following, partial discharges and bioinformatics.

 

The code presented here is also part of the Accord.NET Framework. The Accord.NET Framework is a framework for developing machine learning, computer vision, computer audition, statistics and math applications. It is based on the already excellent AForge.NET Framework. Please see the starting guide for mode details. The latest version of the framework includes the latest version of this code plus many other statistics and machine learning tools.

Contents

  1. Introduction
  2. Definition
    1. Notation
    2. Canonical problems
    3. Choosing the structure
  3. Algorithms
    1. Evaluation
    2. Decoding
    3. Learning
  4. Using the code
  5. Remarks
    1. Known issues
  6. Acknowledgements
  7. See also
  8. References

 

Introduction

Hidden Markov Models were first described in a series of statistical papers by Leonard E. Baum and other authors in the second half of the 1960s. One of the first applications of HMMs was speech recognition, starting in the mid-1970s. Indeed, one of the most comprehensive explanations on the topic was published in “A Tutorial On Hidden Markov Models And Selected Applications in Speech Recognition”, by Lawrence R. Rabiner in 1989. In the second half of the 1980s, HMMs began to be applied to the analysis of biological sequences, in particular DNA. Since then, they have become ubiquitous in the field of bioinformatics.

Dynamical systems of discrete nature assumed to be governed by a Markov chain emits a sequence of observable outputs. Under the Markov assumption, it is also assumed that the latest output depends only on the current state of the system. Such states are often not known from the observer when only the output values are observable.

Example of a hidden Markov model Hidden Markov Models attempt to model such systems and allow, among other things, (1) to infer the most likely sequence of states that produced a given output sequence, to (2) infer which will be the most likely next state (and thus predicting the next output) and (3) calculate the probability that a given sequence of outputs originated from the system (allowing the use of hidden Markov models for sequence classification).

The “hidden” in Hidden Markov Models comes from the fact that the observer does not know in which state the system may be in, but has only a probabilistic insight on where it should be.

 

Definition

Hidden Markov Models can be seem as finite state machines where for each sequence unit observation there is a state transition and, for each state, there is a output symbol emission.

Notation

Traditionally, HMMs have been defined by the following quintuple:

lambda = (N, M, A, B, pi)

where

  • N is the number of states for the model
  • M is the number of distinct observations symbols per state, i.e. the discrete alphabet size.
  • A is the NxN state transition probability distribution given in the form of a matrix A = {aij}
  • B is the NxM observation symbol probability distribution given in the form of a matrix B = {bj(k)}
  • π is the initial state distribution vector π = {πi}

 

Note that, if we opt out the structure parameters M and N we have the more often used compact notation

lambda = (A, B, pi)

Canonical problems

There are three canonical problems associated with hidden Markov models, which I’ll quote from Wikipedia:

  1. Given the parameters of the model, compute the probability of a particular output sequence. This requires summation over all possible state sequences, but can be done efficiently using the Forward algorithm, which is a form of dynamic programming.
  2. Given the parameters of the model and a particular output sequence, find the state sequence that is most likely to have generated that output sequence. This requires finding a maximum over all possible state sequences, but can similarly be solved efficiently by the Viterbi algorithm.
  3. Given an output sequence or a set of such sequences, find the most likely set of state transition and output probabilities. In other words, derive the maximum likelihood estimate of the parameters of the HMM given a dataset of output sequences. No tractable algorithm is known for solving this problem exactly, but a local maximum likelihood can be derived efficiently using the Baum-Welch algorithm or the Baldi-Chauvin algorithm. The Baum-Welch algorithm is an example of a forward-backward algorithm, and is a special case of the Expectation-maximization algorithm.

The solution for those problems are exactly what makes Hidden Markov Models useful. The ability to learn from the data (using the solution of problem 3) and then become able to make predictions (solution to problem 2) and able to classify sequences (solution of problem 2) is nothing but applied machine learning. From this perspective, HMMs can just be seem as supervisioned sequence classifiers and sequence predictors with some other useful interesting properties.

Choosing the structure

Choosing the structure for a hidden Markov model is not always obvious. The number of states depend on the application and to what interpretation one is willing to give to the hidden states. Some domain knowledge is required to build a suitable model and also to choose the initial parameters that an HMM can take. There is also some trial and error involved, and there are sometimes complex tradeoffs that have to be made between model complexity and difficulty of learning, just as is the case with most machine learning techniques.

Additional information can be found on http://www.cse.unsw.edu.au/~waleed/phd/tr9806/node12.html.

 

Algorithms

The solution to the three canonical problems are the algorithms that makes HMMs useful. Each of the three problems are described in the three subsections below.

Evaluation

The first canonical problem is the evaluation of the probability of a particular output sequence. It can be efficiently computed using either the Viterbi-forward or the Forward algorithms, both of which are forms of dynamic programming.

The Viterbi algorithm originally computes the most likely sequence of states which has originated a sequence of observations. In doing so, it is also able to return the probability of traversing this particular sequence of states. So to obtain Viterbi probabilities, please refer to the Decoding problem referred below.

The Forward algorithm, unlike the Viterbi algorithm, does not find a particular sequence of states; instead it computes the probability that any sequence of states has produced the sequence of observations. In both algorithms, a matrix is used to store computations about the possible state sequence paths that the model can assume. The forward algorithm also plays a key role in the Learning problem, and is thus implemented as a separate method.

 

Decoding

The second canonical problem is the discovery of the most likely sequence of states that generated a given output sequence. This can be computed efficiently using the Viterbi algorithm. A trackback is used to detect the maximum probability path travelled by the algorithm. The probability of travelling such sequence is also computed in the process.

 

Learning

The third and last problem is the problem of learning the most likely parameters that best models a system given a set of sequences originated from this system. Most implementations I’ve seem did not consider the problem of learning from a set of sequences, but only from a single sequence at a time. The algorithm below, however, is fully suitable to learn from a set of sequences and also uses scaling, which is another thing I have not seem in other implementations.

The source code follows the original algorithm by Rabiner (1989). There are, however, some known issues with the algorithms detailed in Rabiner’s paper. More information about those issues is available in a next section of this article entitled “Remarks”.

 

Using the code

Lets suppose we have gathered some sequences from a system we wish to model. The sequences are expressed as a integer array such as:

For us, it can be obvious to see that the system is outputting sequences that always start with a zero and have one or more ones at the end. But lets try to fit a Hidden Markov Model to predict those sequences.

Once the model is trained, lets test to see if it recognizes some sequences:

Of course the model performs well as this a rather simple example. A more useful test case would consist of allowing for some errors in the input sequences in the hope that the model will become more tolerant to measurement errors.

We can see that, despite having a very low probability, the likelihood values for the sequences containing a simulated measurement error are greater than the likelihoods for the sequences which do not follow the sequence structure at all.

In a subsequent article, we will see that those low values for the likelihoods will not be a problem because HMMs are often used in sets to form sequence classifiers. When used in such configurations, what really matters is which HMM returns the highest probability among others in the set.

 

Remarks

A practical issue in the use of Hidden Markov Models to model long sequences is the numerical scaling of conditional probabilities. The probability of observing a long sequence given most models is extremely small, and the use of these extremely small numbers in computations often leads to numerical instability, making application of HMMs to genome length sequences quite challenging.

There are two common approaches to dealing with small conditional probabilities. One approach is to rescale the conditional probabilities using carefully designed scaling factors, and the other approach is to work with the logarithms of the conditional probabilities. For more information on using logarithms please see the work entitled “Numerically Stable Hidden Markov Model Implementation”, by Tobias P. Mann.

Known issues

The code on this article is based on the Tutorial by Rabiner. There are, however, some problems with the scaling and other algorithms. An errata depicting all issues is available in the website “An Erratum for ‘A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition’” and is maintained by Ali Rahimi. I have not yet verified if the implementation presented here also suffers from the same mistakes explained there. This code has worked well under many situations, but I cannot guarantee its perfectness. Please use at your own risk.

Acknowledgements

Thanks to Guilherme C. Pedroso, for the help with the Baum-Welch generalization for multiple input sequences. He has also co-written a very interesting article using hidden Markov models for gesture recognition, entitled “Automatic Recognition of Finger Spelling for LIBRAS based on a Two-Layer Architecture” published in the 25th Symposium On Applied Computing (ACM SAC 2010).

See also

References

Onde encontrar cabo de força para fonte de alimentação de notebooks

cabo-2_thumb-5B5-5D

Geralmente, ao comprar uma fonte nova, principalmente pela internet, o que chega é somente a fonte, sem o cabo de alimentação que a conecta na tomada. Neste caso, é preciso adquiri-lo separadamente. O que não chega a ser importuno desde que na sua cidade alguem saiba onde encontrar este bendito cabo, o que não é o caso de Valinhos, por exemplo, em que me disseram que eu nunca o acharia.

Bom, se você mora em São Carlos, a boa notícia é que ele pode ser encontrado na:

Eletrônica Gaspar

Av. São Carlos, 2615, São Carlos-SP
Fone: (16) 3371-4014 / 3371-3412

 

É a segunda vez que anuncio o endereço da Gaspar neste blog. Um detalhe interessante é que na Gaspar você encontra dois tipos de cabos, o de dois pinos e o de três pinos.

cabo-2

O cabo de dois pinos, comumente usado em aparelhos de som, custa R$7,00, mas não encaixa perfeitamente na fonte. Contudo, com alguma força (ou com algum entalhamento no conector de plástico) é possível fazê-lo entrar. Vale a pena se você, por exemplo, não tiver uma fiação terra em sua casa e já estiver usando um adaptador de três pinos para poder carregar seu notebook. É uma opção também caso não consiga encontrar o cabo de três pinos em sua cidade, já que este deve estar disponível em qualquer assistência ou loja de eletrônica.

cabo-3

Já o cabo de três pinos encaixa perfeitamente porém custava R$21,00. Estes preços são referentes ao mês de fevereiro de 2010 na Gaspar, mas não creio que mudem muito de loja para loja nem ao decorrer dos anos.

 

No meu caso, resolvi comprar o de dois pinos para evitar ter de andar sempre carregando um adaptador na mala para os (quase todos) casos em que não há uma conexão terra disponível nos lugares onde vou. Após algum trabalho para fazê-lo entrar, funciona perfeitamente na minha fonte HP importada do DealExtreme.

Kernel Functions for Machine Learning Applications

In recent years, Kernel methods have received major attention, particularly due to the increased popularity of the Support Vector Machines. Kernel functions can be used in many applications as they provide a simple bridge from linearity to non-linearity for algorithms which can be expressed in terms of dot products. In this article, we will list a few kernel functions and some of their properties.

Many of these functions have been incorporated in Accord.NET, a framework for creating machine learning, statistics, and computer vision applications.

Contents

  1. Kernel Methods
    1. The Kernel Trick
    2. Kernel Properties
    3. Choosing the Right Kernel
  2. Kernel Functions
    1. Linear Kernel
    2. Polynomial Kernel
    3. Gaussian Kernel
    4. Exponential Kernel
    5. Laplacian Kernel
    6. ANOVA Kernel
    7. Hyperbolic Tangent (Sigmoid) Kernel
    8. Rational Quadratic Kernel
    9. Multiquadric Kernel
    10. Inverse Multiquadric Kernel
    11. Circular Kernel
    12. Spherical Kernel
    13. Wave Kernel
    14. Power Kernel
    15. Log Kernel
    16. Spline Kernel
    17. B-Spline Kernel
    18. Bessel Kernel
    19. Cauchy Kernel
    20. Chi-Square Kernel
    21. Histogram Intersection Kernel
    22. Generalized Histogram Intersection Kernel
    23. Generalized T-Student Kernel
    24. Bayesian Kernel
    25. Wavelet Kernel
  3. Source code
  4. See also
  5. References

Kernel Methods

Kernel methods are a class of algorithms for pattern analysis or recognition, whose best known element is the support vector machine (SVM). The general task of pattern analysis is to find and study general types of relations (such as clusters, rankings, principal components, correlations, classifications) in general types of data (such as sequences, text documents, sets of points, vectors, images, graphs, etc) (Wikipedia, 2010a).

The main characteristic of Kernel Methods, however, is their distinct approach to this problem. Kernel methods map the data into higher dimensional spaces in the hope that in this higher-dimensional space the data could become more easily separated or better structured. There are also no constraints on the form of this mapping, which could even lead to infinite-dimensional spaces. This mapping function, however, hardly needs to be computed because of a tool called the kernel trick.

The Kernel trick

The Kernel trick is a very interesting and powerful tool. It is powerful because it provides a bridge from linearity to non-linearity to any algorithm that can expressed solely on terms of dot products between two vectors. It comes from the fact that, if we first map our input data into a higher-dimensional space, a linear algorithm operating in this space will behave non-linearly in the original input space.

Now, the Kernel trick is really interesting because that mapping does not need to be ever computed. If our algorithm can be expressed only in terms of a inner product between two vectors, all we need is replace this inner product with the inner product from some other suitable space. That is where resides the “trick”: wherever a dot product is used, it is replaced with a Kernel function. The kernel function denotes an inner product in feature space and is usually denoted as:

K(x,y) = <φ(x),φ(y)>

Using the Kernel function, the algorithm can then be carried into a higher-dimension space without explicitly mapping the input points into this space. This is highly desirable, as sometimes our higher-dimensional feature space could even be infinite-dimensional and thus unfeasible to compute.

Kernel Properties

Kernel functions must be continuous, symmetric, and most preferably should have a positive (semi-) definite Gram matrix. Kernels which are said to satisfy the Mercer’s theorem are positive semi-definite, meaning their kernel matrices have only non-negative Eigen values. The use of a positive definite kernel insures that the optimization problem will be convex and solution will be unique.

However, many kernel functions which aren’t strictly positive definite also have been shown to perform very well in practice. An example is the Sigmoid kernel, which, despite its wide use, it is not positive semi-definite for certain values of its parameters. Boughorbel (2005) also experimentally demonstrated that Kernels which are only conditionally positive definite can possibly outperform most classical kernels in some applications.

Kernels also can be classified as anisotropic stationary, isotropic stationary, compactly supported, locally stationary, nonstationary or separable nonstationary. Moreover, kernels can also be labeled scale-invariant or scale-dependant, which is an interesting property as scale-invariant kernels drive the training process invariant to a scaling of the data.

Choosing the Right Kernel

Choosing the most appropriate kernel highly depends on the problem at hand – and fine tuning its parameters can easily become a tedious and cumbersome task. Automatic kernel selection is possible and is discussed in the works by Tom Howley and Michael Madden.

The choice of a Kernel depends on the problem at hand because it depends on what we are trying to model. A polynomial kernel, for example, allows us to model feature conjunctions up to the order of the polynomial. Radial basis functions allows to pick out circles (or hyperspheres) – in constrast with the Linear kernel, which allows only to pick out lines (or hyperplanes).

The motivation behind the choice of a particular kernel can be very intuitive and straightforward depending on what kind of information we are expecting to extract about the data. Please see the final notes on this topic from Introduction to Information Retrieval, by Manning, Raghavan and Schütze for a better explanation on the subject.

Kernel Functions

Below is a list of some kernel functions available from the existing literature. As was the case with previous articles, every LaTeX notation for the formulas below are readily available from their alternate text html tag. I can not guarantee all of them are perfectly correct, thus use them at your own risk. Most of them have links to articles where they have been originally used or proposed.

1. Linear Kernel

The Linear kernel is the simplest kernel function. It is given by the inner product <x,y> plus an optional constant c. Kernel algorithms using a linear kernel are often equivalent to their non-kernel counterparts, i.e. KPCA with linear kernel is the same as standard PCA.

k(x, y) = x^T y + c

2. Polynomial Kernel

The Polynomial kernel is a non-stationary kernel. Polynomial kernels are well suited for problems where all the training data is normalized.

k(x, y) = (alpha x^T y + c)^d
Adjustable parameters are the slope alpha, the constant term c and the polynomial degree d.

3. Gaussian Kernel

The Gaussian kernel is an example of radial basis function kernel.

k(x, y) = expleft(-frac{ lVert x-y rVert ^2}{2sigma^2}right)

Alternatively, it could also be implemented using

k(x, y) = expleft(- gamma lVert x-y rVert ^2 )

The adjustable parameter sigma plays a major role in the performance of the kernel, and should be carefully tuned to the problem at hand. If overestimated, the exponential will behave almost linearly and the higher-dimensional projection will start to lose its non-linear power. In the other hand, if underestimated, the function will lack regularization and the decision boundary will be highly sensitive to noise in training data.

4. Exponential Kernel

The exponential kernel is closely related to the Gaussian kernel, with only the square of the norm left out. It is also a radial basis function kernel.

k(x, y) = expleft(-frac{ lVert x-y rVert }{2sigma^2}right)

5. Laplacian Kernel

The Laplace Kernel is completely equivalent to the exponential kernel, except for being less sensitive for changes in the sigma parameter. Being equivalent, it is also a radial basis function kernel.

k(x, y) = expleft(- frac{lVert x-y rVert }{sigma}right)

It is important to note that the observations made about the sigma parameter for the Gaussian kernel also apply to the Exponential and Laplacian kernels.

6. ANOVA Kernel

The ANOVA kernel is also a radial basis function kernel, just as the Gaussian and Laplacian kernels. It is said to perform well in multidimensional regression problems (Hofmann, 2008).

k(x, y) =  sum_{k=1}^n  exp (-sigma (x^k - y^k)^2)^d

7. Hyperbolic Tangent (Sigmoid) Kernel

The Hyperbolic Tangent Kernel is also known as the Sigmoid Kernel and as the Multilayer Perceptron (MLP) kernel. The Sigmoid Kernel comes from the Neural Networks field, where the bipolar sigmoid function is often used as an activation function for artificial neurons.

k(x, y) = tanh (alpha x^T y + c)

It is interesting to note that a SVM model using a sigmoid kernel function is equivalent to a two-layer, perceptron neural network. This kernel was quite popular for support vector machines due to its origin from neural network theory. Also, despite being only conditionally positive definite, it has been found to perform well in practice.

There are two adjustable parameters in the sigmoid kernel, the slope alpha and the intercept constant c. A common value for alpha is 1/N, where N is the data dimension. A more detailed study on sigmoid kernels can be found in the works by Hsuan-Tien and Chih-Jen.

8. Rational Quadratic Kernel

The Rational Quadratic kernel is less computationally intensive than the Gaussian kernel and can be used as an alternative when using the Gaussian becomes too expensive.

k(x, y) = 1 - frac{lVert x-y rVert^2}{lVert x-y rVert^2 + c}

9. Multiquadric Kernel

The Multiquadric kernel can be used in the same situations as the Rational Quadratic kernel. As is the case with the Sigmoid kernel, it is also an example of an non-positive definite kernel.

k(x, y) = sqrt{lVert x-y rVert^2 + c^2}

10. Inverse Multiquadric Kernel

The Inverse Multi Quadric kernel. As with the Gaussian kernel, it results in a kernel matrix with full rank (Micchelli, 1986) and thus forms a infinite dimension feature space.

k(x, y) = frac{1}{sqrt{lVert x-y rVert^2 + theta^2}}

11. Circular Kernel

The circular kernel is used in geostatic applications. It is an example of an isotropic stationary kernel and is positive definite in R2.

k(x, y) = frac{2}{pi} arccos ( - frac{ lVert x-y rVert}{sigma}) - frac{2}{pi} frac{ lVert x-y rVert}{sigma} sqrt{1 - left(frac{ lVert x-y rVert}{sigma} right)^2}
mbox{if}~ lVert x-y rVert < sigma mbox{, zero otherwise}

12. Spherical Kernel

The spherical kernel is similar to the circular kernel, but is positive definite in R3.

k(x, y) = 1 - frac{3}{2} frac{lVert x-y rVert}{sigma} + frac{1}{2} left( frac{ lVert x-y rVert}{sigma} right)^3

mbox{if}~ lVert x-y rVert < sigma mbox{, zero otherwise}

13. Wave Kernel

The Wave kernel is also symmetric positive semi-definite (Huang, 2008).

k(x, y) = frac{theta}{lVert x-y rVert right} sin frac{lVert x-y rVert }{theta}

14. Power Kernel

The Power kernel is also known as the (unrectified) triangular kernel. It is an example of scale-invariant kernel (Sahbi and Fleuret, 2004) and is also only conditionally positive definite.

k(x,y) = - lVert x-y rVert ^d

15. Log Kernel

The Log kernel seems to be particularly interesting for images, but is only conditionally positive definite.

k(x,y) = - log (lVert x-y rVert ^d + 1)

16. Spline Kernel

The Spline kernel is given as a piece-wise cubic polynomial, as derived in the works by Gunn (1998).

k(x, y) = 1 + xy + xy~min(x,y) - frac{x+y}{2}~min(x,y)^2+frac{1}{3}min(x,y)^3

However, what it actually mean is:

k(x,y) = prod_{i=1}^d 1 + x_i y_i + x_i y_i min(x_i, y_i) - frac{x_i + y_i}{2} min(x_i,y_i)^2 + frac{min(x_i,y_i)^3}{3}

Withx,y in R^d

17. B-Spline (Radial Basis Function) Kernel

The B-Spline kernel is defined on the interval [−1, 1]. It is given by the recursive formula:

k(x,y) = B_{2p+1}(x-y)

mbox{where~} p in N mbox{~with~} B_{i+1} := B_i otimes  B_0.

In the work by Bart Hamers it is given by:

k(x, y) = prod_{p=1}^d B_{2n+1}(x_p - y_p)

Alternatively, Bn can be computed using the explicit expression (Fomel, 2000):

B_n(x) = frac{1}{n!} sum_{k=0}^{n+1} binom{n+1}{k} (-1)^k (x + frac{n+1}{2} - k)^n_+

Where x+ is defined as the truncated power function:

x^d_+ = begin{cases} x^d, & mbox{if }x > 0   0, & mbox{otherwise} end{cases}

18. Bessel Kernel

The Bessel kernel is well known in the theory of function spaces of fractional smoothness. It is given by:

k(x, y) = frac{J_{v+1}( sigma lVert x-y rVert)}{ lVert x-y rVert ^ {-n(v+1)} }

where J is the Bessel function of first kind. However, in the Kernlab for R documentation, the Bessel kernel is said to be:

k(x,x') = - Bessel_{(nu+1)}^n (sigma |x - x'|^2)

19. Cauchy Kernel

The Cauchy kernel comes from the Cauchy distribution (Basak, 2008). It is a long-tailed kernel and can be used to give long-range influence and sensitivity over the high dimension space.

k(x, y) = frac{1}{1 + frac{lVert x-y rVert^2}{sigma^2} }

20. Chi-Square Kernel

The Chi-Square kernel comes from the Chi-Square distribution:

k(x,y) = 1 - sum_{i=1}^n frac{(x_i-y_i)^2}{frac{1}{2}(x_i+y_i)}

However, as noted by commenter Alexis Mignon, this version of the kernel is only conditionally positive-definite (CPD). A positive-definite version of this kernel is given in (Vedaldi and Zisserman, 2011) as

and is suitable to be used by methods other than support vector machines.

21. Histogram Intersection Kernel

The Histogram Intersection Kernel is also known as the Min Kernel and has been proven useful in image classification.

k(x,y) = sum_{i=1}^n min(x_i,y_i)

22. Generalized Histogram Intersection

The Generalized Histogram Intersection kernel is built based on the Histogram Intersection Kernel for image classification but applies in a much larger variety of contexts (Boughorbel, 2005). It is given by:

k(x,y) = sum_{i=1}^m min(|x_i|^alpha,|y_i|^beta)

23. Generalized T-Student Kernel

The Generalized T-Student Kernel has been proven to be a Mercel Kernel, thus having a positive semi-definite Kernel matrix (Boughorbel, 2004). It is given by:

k(x,y) = frac{1}{1 + lVert x-y rVert ^d}

24. Bayesian Kernel

The Bayesian kernel could be given as:

k(x,y) = prod_{l=1}^N kappa_l (x_l,y_l)

where

kappa_l(a,b) = sum_{c in {0;1}} P(Y=c mid X_l=a) ~ P(Y=c mid X_l=b)

However, it really depends on the problem being modeled. For more information, please see the work by Alashwal, Deris and Othman, in which they used a SVM with Bayesian kernels in the prediction of protein-protein interactions.

25. Wavelet Kernel

The Wavelet kernel (Zhang et al, 2004) comes from Wavelet theory and is given as:

k(x,y) = prod_{i=1}^N h(frac{x_i-c_i}{a}) :  h(frac{y_i-c_i}{a})

Where a and c are the wavelet dilation and translation coefficients, respectively (the form presented above is a simplification, please see the original paper for details). A translation-invariant version of this kernel can be given as:

k(x,y) = prod_{i=1}^N h(frac{x_i-y_i}{a})

Where in both h(x) denotes a mother wavelet function. In the paper by Li Zhang, Weida Zhou, and Licheng Jiao, the authors suggests a possible h(x) as:

h(x) = cos(1.75x)exp(-frac{x^2}{2})

Which they also prove as an admissible kernel function.

 

Source Code

The latest version of the source code for almost all of the kernels listed above is available in the Accord.NET Framework. Some are also available in the sequel of this article, Kernel Support Vector Machines for Classification and Regression in C#. They are provided together with a comprehensive and simple implementation of SVMs (Support Vector Machines) in C#. However, for the latest sources, which may contain bug fixes and other enhancements, please download the most recent version available of Accord.NET.

See also

 

References

Citing this work

If you would like, please cite this work as: Souza, César R. “Kernel Functions for Machine Learning Applications.” 17 Mar. 2010. Web. <http://crsouza.blogspot.com/2010/03/kernel-functions-for-machine-learning.html>.

Windows Vista falha ao retornar do modo sleep ou da hibernação – Como resolver?

Este é um problema muito comum. Já observei várias máquinas, incluindo absolutamente todas as máquinas do laboratório da UFSCar que tinham o Vista instalado em 2008 enfrentando dificuldades em retornar da hibernação ou do sleep. O problema é bem característico:

O Problema

Passos:

  • Deixe seu computador entrar em sleep ou hibernar.
  • Tente voltar do modo de espera.

Resultado:

  • A máquina liga, mas sem vídeo (a tela permanece apagada) e sem nenhum recurso USB (como mouse e teclado) respondendo a seu comando.

Sendo que a única maneira de recuperar é forçando um shutdown segurando o botão de power.

A Solução

Apesar da Microsoft alegar que este problema não existe, a solução é relativamente simples. O problema ocorre pois um dos dispositivos USB falha ao ser suspenso. Para verificar se é este mesmo o problema, siga estes passos:

  1. Abra um prompt de comando com privilégios de administrador.

  2. Digite powercfg -energy

Isto fará com que seja criado um arquivo HTML indicando quaisquer erros relacionados com o sistema de energia. O arquivo será criado em C:Windowssystem32energy-report.html

Abra o arquivo. Provavelmente haverá uma linha indicando “USB Suspend:USB Device not Entering Suspend” ou algo similar em português. Neste caso,

  1. Vá até o Painel de Controle->Opções de Energia->(seu plano de energia)->Modificar configurações do plano->Modificar Configurações Avançadas->Configurações USB->Suspensão USB Seletiva e desabilite esta configuração.

  2. Clique OK.

  3. Problema resolvido.

Impressão de Painéis em São Carlos para Apresentações em Congressos Científicos

Alguns meses atrás precisei encontrar um local que fabricasse painéis para apresentações em congressos e conferências, como para a IX International Conference on Machine Learning and Applications. Buscando informações, um dos locais em São Carlos a que fui recomendado foi a Disque Cópias Xerox e Plotagem.

Disque Copias Xerox e Plotagem


View Larger Map

Rua Sete de Setembro, 2152
Fone: 3372-9545

Painel 90cm x 120cm (gloss paper)

  • Apenas impressão: R$42,00
  • Impressão com acabamento (suportes): R$47,00

O tempo para secagem do painel é de aproximadamente 5 dias. O painel pode ser fornecido no formato PDF ou PowerPoint. E a qualidade é bastante satisfatória. O mesmo serviço em Campinas chega a custar R$80,00.

List of Windows Messages

Here is a list of all Windows Messages available in the form of a C# enumeration, just in case someone finds it useful.