Package elki.svm.solver

Class Solver

java.lang.Object

elki.svm.solver.Solver

Direct Known Subclasses:

NuSolver

public class Solver
extends java.lang.Object

SMO solver for support vector machines, derived from libSVM.

An SMO algorithm in Fan et al., JMLR 6(2005), p. 1889--1918

Solves:
\[\min 0.5(\alpha^T Q \alpha) + p^T \alpha\]
\[y^T \alpha = \delta\] \[y_i = \pm 1\] \[0 ≤ alpha_i ≤ Cp \text{for} y_i = 1\] \[0 ≤ alpha_i ≤ Cn \text{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

Since:

0.8.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Solver.SolutionInfo

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int[]	active_set
(package private) int	active_size
(package private) double[]	alpha
(package private) byte[]	alpha_status
(package private) double	Cn
(package private) double	Cp
(package private) double	eps
(package private) static byte	FREE
(package private) double[]	G
(package private) double[]	G_bar
(package private) int	l
private static Logging	LOG
(package private) static byte	LOWER_BOUND
(package private) double[]	p
(package private) QMatrix	Q
(package private) float[]	Q_i
(package private) float[]	Q_j
(package private) boolean	unshrink
(package private) static byte	UPPER_BOUND
(package private) byte[]	y

Constructor Summary

Constructors

Constructor	Description
Solver()

Method Summary

Modifier and Type	Method	Description
private boolean	be_shrunk(int i, double Gmax1, double Gmax2)
(package private) Solver.SolutionInfo	buildSolutionInfo(int l, double Cp, double Cn)
protected double	calculate_obj()
(package private) double	calculate_rho()
(package private) void	do_shrinking()
(package private) double	get_C(int i)
protected void	initializeActiveSet()	Initialize the active set.
protected void	initializeAlpha()	Initialize the alpha values.
void	initializeGradient()
(package private) boolean	is_free(int i)
(package private) boolean	is_lower_bound(int i)
(package private) boolean	is_upper_bound(int i)
protected double	maxViolating(int[] working_set)
protected double	minViolating(int[] working_set, double Gi)
protected static double	nonzero(double d)
(package private) void	reconstruct_gradient()
(package private) boolean	select_working_set(int[] working_set)
Solver.SolutionInfo	solve(int l, QMatrix Q, double[] p_, byte[] y_, double[] alpha_, double Cp, double Cn, double eps, boolean shrinking)
(package private) void	swap_index(int i, int j)
(package private) void	update_alpha_status(int i)
private void	update_G(int i, int j, double old_alpha_i, double old_alpha_j)
private void	update_G_bar(double C_i, float[] Q_i)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

active_size

int active_size

y

byte[] y

G

double[] G

LOWER_BOUND

static final byte LOWER_BOUND

See Also:

Constant Field Values

UPPER_BOUND

static final byte UPPER_BOUND

See Also:

Constant Field Values

FREE

static final byte FREE

See Also:

Constant Field Values

alpha_status

byte[] alpha_status

alpha

double[] alpha

Q

QMatrix Q

eps

double eps

Cp

double Cp

Cn

double Cn

p

double[] p

active_set

int[] active_set

G_bar

double[] G_bar

Q_i

float[] Q_i

Q_j

float[] Q_j

l

int l

unshrink

boolean unshrink

Constructor Detail

Solver

public Solver()

Method Detail

get_C

double get_C(int i)

update_alpha_status

void update_alpha_status(int i)

is_upper_bound

boolean is_upper_bound(int i)

is_lower_bound

boolean is_lower_bound(int i)

is_free

boolean is_free(int i)

swap_index

void swap_index(int i,
                int j)

reconstruct_gradient

void reconstruct_gradient()

solve

public Solver.SolutionInfo solve(int l,
                                 QMatrix Q,
                                 double[] p_,
                                 byte[] y_,
                                 double[] alpha_,
                                 double Cp,
                                 double Cn,
                                 double eps,
                                 boolean shrinking)

buildSolutionInfo

Solver.SolutionInfo buildSolutionInfo(int l,
                                      double Cp,
                                      double Cn)

initializeAlpha

protected void initializeAlpha()

Initialize the alpha values.

initializeActiveSet

protected void initializeActiveSet()

Initialize the active set.

update_G

private void update_G(int i,
                      int j,
                      double old_alpha_i,
                      double old_alpha_j)

update_G_bar

private void update_G_bar(double C_i,
                          float[] Q_i)

initializeGradient

public void initializeGradient()

calculate_obj

protected double calculate_obj()

nonzero

protected static double nonzero(double d)

select_working_set

boolean select_working_set(int[] working_set)

maxViolating

protected double maxViolating(int[] working_set)

minViolating

protected double minViolating(int[] working_set,
                              double Gi)

do_shrinking

void do_shrinking()

be_shrunk

private boolean be_shrunk(int i,
                          double Gmax1,
                          double Gmax2)

calculate_rho

double calculate_rho()