Into

Modules

Documentation

classPiiKernelPerceptron

#include <PiiKernelPerceptron.h>

An implementation of the Kernel Perceptron algorithm.

Inherits PiiLearningAlgorithm< SampleSet >, PiiClassifier< SampleSet >

Description

This class implements a more general version of the Perceptron algorithm known as the Kernel Perceptron. The Kernel Perceptron uses a dual form of the Perceptron algorithm to find the separating hyperplane in a high-dimensional feature space. The algorithm is computationally less efficient than the ordinary Perceptron, but can solve problems that are not linearly separable in the input space. See classification_kernels for details on kernel functions.

The dual form of the Perceptron algoritm is based on the fact that (assuming zero initial weights) the weight vector is a linear combination of the training vectors:

Therefore, finding the coefficients is equivalent to finding the weight vector. One cannot just solve the weight vector as in the normal case, because the solution must be found in the feature space, not in the input space. Depending on the kernel function, we may even not know the dimensionality of the feature space. In the case of a Gaussian kernel, the feature space is infinite-dimensional.

The dual form of the decision threshold is . Now, if the weight vector and the feature vector are mapped into a high-dimensional feature space, the threshold becomes . Thus, the decision function for the Kernel Perceptron is

Here, k() denotes the kernel function. The original perceptron algorithm uses dot product as the kernel, resulting in a linear hyperplane classifier. Thus, using PiiDotProductKernel as the kernel function for PiiKernelPerceptron is functionally equivalent to (but less efficient than) using PiiPerceptron, except for the bias term.

After training, the Kernel Perceptron only keeps the support vectors (training samples with a non-zero weight) in memory. The number of retained support vectors varies widely depending on application, but sometimes only very few samples need to be stored.

The derivation above neglects the bias term. See classification_kernels for a justification.

Public types

typedef PiiSampleSet::Traits< SampleSet >::ConstFeatureIterator

Constructors and destructor

Constructs a new Kernel Perceptron.

Destroys the Kernel Perceptron.

Public member functions

virtual PiiClassification::LearnerCapabilities

Returns 0.

virtual double
(
  • ConstFeatureIterator featureVector
)

Returns the classification of featureVector (either 0 or 1), or NaN if the perceptron has not been trained yet.

virtual bool

Returns true if learn() was called, and the learning algorithm converged to a solution, false otherwise.

int

Returns the number of features in each feature vector.

PiiKernelFunction< ConstFeatureIterator > *

Returns the kernel function.

virtual void
(
  • const SampleSet & samples
  • const QVector< double > & labels
  • const QVector< double > & weights = < double >()
)

Runs the Kernel Perceptron algorithm with the given samples and class labels.

int

Returns the maximum number of learning iterations.

void
(
  • PiiKernelFunction< ConstFeatureIterator > * kernel
)

Sets the kernel function.

void
(
  • int maxIterations
)

Sets the maximum number of iterations the algorithm will take.

void
(
  • const SampleSet & supportVectors
)

Sets the support vectors.

void
(
  • const QVector< double > & weights
)

Sets the weight vector.

SampleSet

Returns the support vectors.

QVector< double >

Returns the weight vector.

Function details

  • PiiKernelPerceptron

    ()

    Constructs a new Kernel Perceptron.

  • ~PiiKernelPerceptron

    ()

    Destroys the Kernel Perceptron.

  • virtual PiiClassification::LearnerCapabilities capabilities

    ()
    [virtual]

    Returns 0.

    The Kernel Perceptron is a supervised classifier with no on-line learning capabilities.

    Reimplemented from PiiLearningAlgorithm.

  • virtual double classify

    (
    • ConstFeatureIterator featureVector
    )
    [virtual]

    Returns the classification of featureVector (either 0 or 1), or NaN if the perceptron has not been trained yet.

    Reimplemented from PiiClassifier.

  • virtual bool converged

    ()
    [virtual]

    Returns true if learn() was called, and the learning algorithm converged to a solution, false otherwise.

    The learning algorithm won't converge if the classes are not linearly separable in the feature space or if maxIterations() is reached before finding a solution.

    Reimplemented from PiiLearningAlgorithm.

  • int featureCount

    ()

    Returns the number of features in each feature vector.

    If the perceptron has not been trained, zero will be returned.

  • PiiKernelFunction< ConstFeatureIterator > * kernelFunction

    ()

    Returns the kernel function.

  • virtual void learn

    (
    • const SampleSet & samples
    • const QVector< double > & labels
    • const QVector< double > & weights = < double >()
    )
    [virtual]

    Runs the Kernel Perceptron algorithm with the given samples and class labels.

    Since the Kernel Perceptron is a binary classifier, the class labels must be either ones or zeros. The weights will be ignored.

    Reimplemented from PiiLearningAlgorithm.

  • int maxIterations

    ()

    Returns the maximum number of learning iterations.

    The default value is 100.

  • void setKernelFunction

    (
    • PiiKernelFunction< ConstFeatureIterator > * kernel
    )

    Sets the kernel function.

    This class will take the ownership of kernel. The old kernel function will be deleted. The default kernel is a Gaussian kernel with unit variance.

  • void setMaxIterations

    (
    • int maxIterations
    )

    Sets the maximum number of iterations the algorithm will take.

    This value limits the number of times the whole sample set is iterated over.

  • void setSupportVectors

    (
    • const SampleSet & supportVectors
    )

    Sets the support vectors.

    The support vectors are usually not set manually, but using the learn() function.

  • void setWeights

    (
    • const QVector< double > & weights
    )

    Sets the weight vector.

    The weighs are usually not assigned manually, but using the learn() function.

  • SampleSet supportVectors

    ()

    Returns the support vectors.

  • QVector< double > weights

    ()

    Returns the weight vector.

    The number of weights is equal to the number of support vectors.

Notes (0)

Add a note

Not a single note added yet. Be the first, add yours.