LibSvmSolver (kelp-full 1.1.1 API)

java.lang.Object
- it.uniroma2.sag.kelp.learningalgorithm.classification.libsvm.solver.LibSvmSolver

All Implemented Interfaces:

BinaryLearningAlgorithm, LearningAlgorithm

Direct Known Subclasses:

LibCSvmSolver, LibNuSvmSolver
```
public abstract class LibSvmSolver
extends Object
implements BinaryLearningAlgorithm
```
This class implements the solver of the SVM quadratic problem described in [CC Chang & CJ Lin, 2011]. It is a Java porting of the library LIBSVM v3.17, written in C++.
Further details can be found in:
[CC Chang & CJ Lin, 2011] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011.
and
http://www.csie.ntu.edu.tw/~cjlin/libsvm/

Author:

Danilo Croce

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

protected class LibSvmSolver.Pair
The pair of indices i and j that are selected as working set

Nested Classes
Modifier and Type	Class and Description
`protected class`	`LibSvmSolver.Pair` The pair of indices i and j that are selected as working set

Field Summary

Fields
Modifier and Type	Field and Description
`protected int[]`	`active_set` The set of active examples with 0 < alpha[i] < get_C(i)
`protected int`	`active_size` The number of active examples with 0 < alpha[i] < get_C(i)
`protected float[]`	`alpha` The weight \(\alpha\) of the Support Vectors
`protected it.uniroma2.sag.kelp.learningalgorithm.classification.libsvm.solver.LibSvmSolver.AlphaStatus[]`	`alpha_status` The status of each example
`protected float`	`cn` The regularization parameter of negative examples
`protected float`	`cp` The regularization parameter of positive examples
`protected static boolean`	`doShrinking` A boolean value to apply shrinking
`protected static float`	`eps` Tolerance of termination criterion
`protected Example[]`	`examples` The input examples
`protected float[]`	`G` Gradient
`protected float[]`	`G_bar` Gradient bar
`protected Kernel`	`kernel` The Kernel function between examples, i.e.
`protected int`	`l` Total number of Support Vectors
`protected Label`	`label` The label to be learned by the classifier
`protected static int`	`logIteration` The number of iteration to be accomplished to print info in the standard output
`protected float[]`	`p`
`protected float[]`	`QD` Q-MATRIX is derived from kernel matrix: Q_{ij}=y_{i}y_{j}K_{ij}
`protected static int`	`shrinkingIteration` Number of iterations to be accomplished before shrinking
`protected static float`	`TAU` A small positive constant to
`protected boolean`	`unshrink`
`protected int[]`	`y` The integer label \(\pm 1\) of the training example

Constructor Summary

Constructors
Constructor and Description

LibSvmSolver()

LibSvmSolver(Kernel kernel, float Cp, float Cn)

Constructors
Constructor and Description
`LibSvmSolver()`
`LibSvmSolver(Kernel kernel, float Cp, float Cn)`

Method Summary

Methods
Modifier and Type	Method and Description
`protected abstract float`	`calculate_rho()`
`protected abstract void`	`do_shrinking()` Apply the shrinking step
`protected float[]`	`get_QD()` For each example i, it return the K_ii score
`protected float`	`get_Qij(int i, int j)`
`float`	`getCn()`
`float`	`getCp()`
`Kernel`	`getKernel()`
`Label`	`getLabel()`
`List<Label>`	`getLabels()` Returns the labels representing the concept to be learned.
`protected void`	`info(String msg)`
`protected boolean`	`is_free(int i)` Check if 0 < alpha[i] < get_C(i)
`protected boolean`	`is_lower_bound(int i)` Check if alpha[i] <= 0
`protected boolean`	`is_upper_bound(int i)` Check if alpha[i] >= get_C(i)
`protected float`	`kernel(Example exA, Example exB)` This function embeds the call to the kernel function
`protected void`	`reconstruct_gradient()` Reconstruct inactive elements of G from G_bar and free variables
`protected abstract int`	`select_working_set(LibSvmSolver.Pair pair)` Select the working set in each iteration.
`void`	`setC(float c)`
`void`	`setCn(float cn)`
`void`	`setCp(float cp)`
`void`	`setLabel(Label label)`
`void`	`setLabels(List<Label> labels)` Sets the labels representing the concept to be learned.
`SvmSolution`	`solve(int l_, Dataset dataset, float[] p_, int[] y_, float[] initial_alpha)` It solves the SMO algorithm in [CC Chang & CJ Lin, 2011] min 0.5(\alpha^T Q \alpha) + p^T \alpha y^T \alpha = \delta y_i = +1 or -1 0 <= alpha_i <= Cp for y_i = 1 0 <= alpha_i <= Cn for y_i = -1 Given: Q, p, y, Cp, Cn, and an initial feasible point \alpha l is the size of vectors and matrices eps is the stopping tolerance solution will be put in \alpha, objective value will be put in obj
`protected void`	`swap_index(int i, int j)` Swap the info of two examples
`protected void`	`swap(Example[] array, int i, int j)`
`protected void`	`swap(float[] array, int i, int j)`
`protected void`	`swap(int[] array, int i, int j)`
`protected void`	`swap(it.uniroma2.sag.kelp.learningalgorithm.classification.libsvm.solver.LibSvmSolver.AlphaStatus[] array, int i, int j)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface it.uniroma2.sag.kelp.learningalgorithm.LearningAlgorithm
duplicate, getPredictionFunction, learn, reset

- Field Detail
  - cp
```
protected float cp
```
    The regularization parameter of positive examples
  - cn
```
protected float cn
```
    The regularization parameter of negative examples
  - kernel
```
protected Kernel kernel
```
    The Kernel function between examples, i.e. \(K_ij\)
  - label
```
protected Label label
```
    The label to be learned by the classifier
  - unshrink
```
protected boolean unshrink
```
  - l
```
protected int l
```
    Total number of Support Vectors
  - y
```
protected int[] y
```
    The integer label \(\pm 1\) of the training example
  - examples
```
protected Example[] examples
```
    The input examples
  - alpha
```
protected float[] alpha
```
    The weight \(\alpha\) of the Support Vectors
  - p
```
protected float[] p
```
  - QD
```
protected float[] QD
```
    Q-MATRIX is derived from kernel matrix: Q_{ij}=y_{i}*y_{j}*K_{ij}
  - alpha_status
```
protected it.uniroma2.sag.kelp.learningalgorithm.classification.libsvm.solver.LibSvmSolver.AlphaStatus[] alpha_status
```
    The status of each example
  - active_set
```
protected int[] active_set
```
    The set of active examples with 0 < alpha[i] < get_C(i)
  - active_size
```
protected int active_size
```
    The number of active examples with 0 < alpha[i] < get_C(i)
  - G
```
protected float[] G
```
    Gradient
  - G_bar
```
protected float[] G_bar
```
    Gradient bar
  - TAU
```
protected static final float TAU
```
    A small positive constant to
    
    See Also:
    Constant Field Values
  - shrinkingIteration
```
protected static final int shrinkingIteration
```
    Number of iterations to be accomplished before shrinking
    
    See Also:
    Constant Field Values
  - logIteration
```
protected static final int logIteration
```
    The number of iteration to be accomplished to print info in the standard output
    
    See Also:
    Constant Field Values
  - eps
```
protected static final float eps
```
    Tolerance of termination criterion
    
    See Also:
    Constant Field Values
  - doShrinking
```
protected static final boolean doShrinking
```
    A boolean value to apply shrinking
    
    See Also:
    Constant Field Values
- Constructor Detail
  - LibSvmSolver
```
public LibSvmSolver()
```
  - LibSvmSolver
```
public LibSvmSolver(Kernel kernel,
            float Cp,
            float Cn)
```
    Parameters:
    kernel - The kernel function
    Cp - The regularization parameter for positive examples
    Cn - The regularization parameter for negative examples
- Method Detail
  - calculate_rho
```
protected abstract float calculate_rho()
```
  - do_shrinking
```
protected abstract void do_shrinking()
```
    Apply the shrinking step
  - get_QD
```
protected float[] get_QD()
```
    For each example i, it return the K_ii score
    
    Returns:
    the array of K_ii score
  - get_Qij
```
protected float get_Qij(int i,
            int j)
```
  - getCn
```
public float getCn()
```
    Returns:
    the \(C_n\) for the negative examples
  - getCp
```
public float getCp()
```
    Returns:
    the \(C_n\) for the positive examples
  - getKernel
```
public Kernel getKernel()
```
    Returns:
    the kernel function
  - getLabel
```
public Label getLabel()
```
    Specified by:
    
    getLabel in interface BinaryLearningAlgorithm
    
    Returns:
    the label associated to the positive class
  - getLabels
```
public List<Label> getLabels()
```
    Description copied from interface: LearningAlgorithm
    
    Returns the labels representing the concept to be learned.
    
    Specified by:
    
    getLabels in interface BinaryLearningAlgorithm
    
    Specified by:
    
    getLabels in interface LearningAlgorithm
    
    Returns:
    the label associated to the positive class, i.e. the output list contains a single entry
  - info
```
protected void info(String msg)
```
  - is_free
```
protected boolean is_free(int i)
```
    Check if 0 < alpha[i] < get_C(i)
    
    Parameters:
    i - the index of the example
    
    Returns:
  - is_lower_bound
```
protected boolean is_lower_bound(int i)
```
    Check if alpha[i] <= 0
    
    Parameters:
    i - the index of the example
    
    Returns:
  - is_upper_bound
```
protected boolean is_upper_bound(int i)
```
    Check if alpha[i] >= get_C(i)
    
    Parameters:
    i - the index of the example
    
    Returns:
  - kernel
```
protected float kernel(Example exA,
           Example exB)
```
    This function embeds the call to the kernel function
    
    Parameters:
    exA -
    exB -
    
    Returns:
    the kernel function result
  - reconstruct_gradient
```
protected void reconstruct_gradient()
```
    Reconstruct inactive elements of G from G_bar and free variables
  - select_working_set
```
protected abstract int select_working_set(LibSvmSolver.Pair pair)
```
    Select the working set in each iteration. This function returns the pair i,j such that
    i: maximizes -y_i * grad(f)_i, i in I_up(\alpha)
    j: minimizes the decrease of obj value
    (if quadratic coefficeint <= 0, replace it with tau)
    -y_j*grad(f)_j < -y_i*grad(f)_i, j in I_low(\alpha)
    
    Parameters:
    pair - The Q_ij to be evaluated
    
    Returns:
    1 if already optimal, return 0 otherwise
  - setCn
```
public void setCn(float cn)
```
    Parameters:
    cn - The regularization parameter for positive examples
  - setCp
```
public void setCp(float cp)
```
    Parameters:
    cp - The regularization parameter for negative examples
  - setC
```
public void setC(float c)
```
    Parameters:
    c - The regularization parameter for both positive and negative examples
  - setLabel
```
public void setLabel(Label label)
```
    Specified by:
    
    setLabel in interface BinaryLearningAlgorithm
  - setLabels
```
public void setLabels(List<Label> labels)
```
    Description copied from interface: LearningAlgorithm
    
    Sets the labels representing the concept to be learned.
    
    Specified by:
    
    setLabels in interface BinaryLearningAlgorithm
    
    Specified by:
    
    setLabels in interface LearningAlgorithm
    
    Parameters:
    labels - the labels representing the concept to be learned
  - solve
```
public SvmSolution solve(int l_,
                Dataset dataset,
                float[] p_,
                int[] y_,
                float[] initial_alpha)
```
    It solves the SMO algorithm in [CC Chang & CJ Lin, 2011] min 0.5(\alpha^T Q \alpha) + p^T \alpha y^T \alpha = \delta
    y_i = +1 or -1
    0 <= alpha_i <= Cp for y_i = 1
    0 <= alpha_i <= Cn for y_i = -1
    Given: Q, p, y, Cp, Cn, and an initial feasible point \alpha l is the size of vectors and matrices eps is the stopping tolerance solution will be put in \alpha, objective value will be put in obj
    
    Parameters:
    l_ - the size of input examples
    dataset - the dataset
    p_ -
    y_ - the labels of the examples
    initial_alpha - the initial \(\alpha\) values
    
    Returns:
    the solution of the SMO problem
  - swap
```
protected void swap(it.uniroma2.sag.kelp.learningalgorithm.classification.libsvm.solver.LibSvmSolver.AlphaStatus[] array,
        int i,
        int j)
```
  - swap
```
protected void swap(Example[] array,
        int i,
        int j)
```
  - swap
```
protected void swap(float[] array,
        int i,
        int j)
```
  - swap
```
protected void swap(int[] array,
        int i,
        int j)
```
  - swap_index
```
protected void swap_index(int i,
              int j)
```
    Swap the info of two examples
    
    Parameters:
    i - the first example index
    j - the second example index

Class LibSvmSolver

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface it.uniroma2.sag.kelp.learningalgorithm.LearningAlgorithm

Field Detail

cp

cn

kernel

label

unshrink

l

y

examples

alpha

p

QD

alpha_status

active_set

active_size

G

G_bar

TAU

shrinkingIteration

logIteration

eps

doShrinking

Constructor Detail

LibSvmSolver

LibSvmSolver

Method Detail

calculate_rho

do_shrinking

get_QD

get_Qij

getCn

getCp

getKernel

getLabel

getLabels

info

is_free

is_lower_bound

is_upper_bound

kernel

reconstruct_gradient

select_working_set

setCn

setCp

setC

setLabel

setLabels

solve

swap

swap

swap

swap

swap_index