reference.html

一种新颖的SVM算法

  114      0.88427      -9.06655e-08
  126     0.561356      1.15792e-07
  138        2.558      2.0497e-08
  155      2.50095      -1.24475e-08
  157     0.247452      -1.35147e-07
  161      3.78932      -1.2767e-07
  165     0.686947      1.03066e-07
Finished checking support vector accuracy.
Total   deviation is 9.30535e-07      No. of SVs: 14
Average deviation is 6.64668e-08
Minimum alpha     is 0.057789
Maximum alpha     is 3.78932</PRE>
<P>
The SVM program uses a different type of optimizer to construct the
rule, depending on which one you selected when setting the parameters.
When using LOQO as the optimizer (the default) if there is an error
in optimization this is stated. MINOS gives 
an output of the following form :
<P>
<PRE> ==============================
 M I N O S    5.4    (Dec 1992)
 ==============================

 Begin SV_TEST        
OPTIMAL SOLUTION FOUND (0)
----------------------------------------</PRE>
<P>
In this case, the optimizer signals that an optimal solution was
found.  If the data is scaled badly, or the data is inseparable (and
the bound on the alphas is infinite), then an error may occur here.
Therefore, you will have to ensure the scaling options are set
correctly, and you may have to change the bound on the alpha values
(the value of <I>C</I>).
<P>
The next section informs the user how many support vectors there are,
and lists the example numbers of those examples which were support
vectors.  This section also indicates the largest alpha value
(lagrangian multiplier), and the
value of b0 (threshold of the decision function). 
This does not apply to the multi-class SVM.
<P>
This is followed by information as to how the SVM
performed on both the training set and the test set.  In the case of
pattern recognition (as shown above), the output indicates the number
of positive and negative samples, and the number of those which were
misclassified in both the training and the test set.  For instance, in
the example above, all of the examples in the training set were 
classified correctly.   
<BR> 
When running the SVM program to
perform regression estimation, various measures of error are displayed
here.  The user is given the average (absolute) error on the training
set.  Also, the totals and averages are displayed for both absolute
and squared error on the training set.
<BR> 
For the multiclass machine a table is displayed giving the number of
errors on the individual classes. This contains the same information
as the normal pattern recognition SVM in a slightly different form.
Adding the columns gives you the total number of examples in a class.
The diagonal is the number of correct classifications.
<P>
Following the performance statistics, a list of the values of the
alphas (Lagrange multipliers) for each support vector is given, along
with its deviation (how far away the support vector is from the
boundary of the margin). If no deviation is printed, the vector was
exactly distance 1 from the margin.
Finally some statistics are given, indicating
the minimum and maximum alpha values (useful for setting <I>C</I>,
the scaling of your
data and sometimes the SV zero threshold.)
<P>
<H1><A NAME="SECTION00050000000000000000"><TT>loadsv</TT></A></H1>
 <A NAME="loadsv">&#160;</A>
<P>
The <TT>loadsv</TT> program is used to load an SV Machine that has
already been trained 
in order to classify new test data. The program 
is run from the command line, and has the following syntax :
<P>
<TT>loadsv &lt;sv machine file&gt; &lt;Test File&gt; </TT>
<P>
Classification of test data is performed in exactly
the same as in the <TT>sv</TT> program
(section <A HREF="reference.html#sv">4</A>).
<P>
<H1><A NAME="SECTION00060000000000000000"><TT>transform_sv</TT></A></H1>
<P>
This is a modified version of the <TT>sv</TT> program, that implements
B. Sch&#246;lkopf's [<A HREF="reference.html#Schol:Thesis">Sch97</A>] ideas of transformation invariance for images.
The training data must be binary classified images and only pattern
recognition can be performed. 
The general idea is that most images are still the same, even if they
are moved a pixel sideways or up or down. The program initially trains
an SVM and then creates a new training set including all support
vectors and their transformations in four directions. This set is used
to train a second machine, which potentially may generalize better
than the first machine.
<P>
Running the program works just like the <TT>sv</TT> program except that
you are asked for the x and y dimensions of the images and the
background intensity.
<P>
At the end you are given two sets of statistics. The first set is the
usual set that the <TT>sv</TT> program produces. The second consists of
the error rate on the newly created training set, the original
training set and the test set.
<P>
<H1><A NAME="SECTION00070000000000000000"><TT>snsv</TT></A></H1>
<P>
Included in the RHUL SV Machine distribution is the utility program 
<TT>snsv</TT> which converts the SN data file format for pattern
recognition problems only into our own data file format. For details 
on the exact format of SN files see ``<TT>sv/docs/snsv/sn-format.txt</TT>''.
For a description of the file format see the appendix 
or for a simple introduction, see ``<TT>sv/docs/intro/sv_user.tex</TT>''.
<P>
The utility program is called in the following way:
<P>
<TT>
snsv &lt;sn data file&gt; &lt;sn truth data file&gt; &lt;output data file&gt;
</TT>
<P>
The first argument is the name of the data file in SN format 
(binary, ASCII or packed) and the second the SN data file containing
the truth values (classifications) of the vectors described in 
the data file. The third argument is the name of the output file.
<P>
The program has the following menu options:
<P>
<PRE>(1) Single class versus other classes ; or
(2) All classes</PRE>
<P>
Option 1 takes the data and truth files and creates a binary classified
data file. Examples from a single class (which you specify) are
labeled as the positive examples, and all other classes are negative 
examples. This is useful when you have multi-class pattern recognition data, 
and you wish to learn a one-against-the-rest classifier.
<P>
Option 2 just saves the class data out as is. If there are more than two 
classes this data file can only be used with a multi-class SV Machine.
<P>
Finally you are asked whether you wish the output to be in binary or ASCII.
Binary offers faster loading times and smaller file sizes, however ASCII
can be useful for debugging or analyzing your data with an editor. All the 
SV programs automatically detect the format (binary or ASCII) of data files.
<P>
<H1><A NAME="SECTION00080000000000000000"><TT>ascii2bin</TT> and <TT>bin2ascii</TT></A></H1>
<P>
The programs are very simple. They convert between our binary and ASCII
input files.They take two command line arguments:
<P>
<TT>ascii2bin &lt;input file&gt; &lt;output file&gt;</TT>
<P>
and
<P>
<TT>bin2ascii &lt;input file&gt; &lt;output file&gt;</TT>
<P>
If you have a program generating data, you might want to look at the
appendix describing the data format.
<P>
<H1><A NAME="SECTION00090000000000000000">Further Information</A></H1>
<P>
There is an on-line version of the support vector machine which has
been developed in the department.  The web site has a graphical
interface which allows you to plot a few points and see what decision
boundary is produced.  The page also provides links to other SVM sites.  
The web address of the page is :
<P>
<TT>http://svm.cs.rhbnc.ac.uk</TT>
<P>
If you have any further questions e-mail us at:
<P>
<TT>[e-mail]</TT>
<P>
<H1><A NAME="SECTION000100000000000000000">Acknowledgements</A></H1>
<P>
We would like to thank A. Gammerman, V. Vapnik, V. Vovk and C. Watkins
at Royal Holloway, K. M&#252;ller at GMD and Y. LeCun, P. Haffner and
P. Simard at AT&amp;T 
for their support in this project.
<P>
<H1><A NAME="SECTION000110000000000000000">SV Kernels</A></H1>
<P>
This is a list of the kernel functions in the RHUL SV Machine:
<UL>
<LI> 1. The simple dot product:
<P>
<BR><IMG WIDTH=300 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath628" SRC="img6.gif"><BR>
<LI> 2. The simple polynomial kernel:
<P>
<BR><IMG WIDTH=330 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath630" SRC="img7.gif"><BR>
<P>
where <I>d</I> is user defined.
<P>
(Taken from [<A HREF="reference.html#vapnik95">Vap95</A>])
<LI> 3. Vovk's real polynomial:
<P>
<BR><IMG WIDTH=326 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath634" SRC="img8.gif"><BR>
<P>
where <I>d</I> is user defined and where <IMG WIDTH=110 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline638" SRC="img9.gif">.
<P>
(From private communications with V. Vovk)
<LI> 4. Vovk's real infinite polynomial:
<P>
<BR><IMG WIDTH=322 HEIGHT=36 ALIGN=BOTTOM ALT="displaymath640" SRC="img10.gif"><BR>
<P>
where <IMG WIDTH=110 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline638" SRC="img9.gif">.
<P>
(From private communications with V. Vovk)
<LI> 5. Radial Basis function:
<P>
<BR><IMG WIDTH=305 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath644" SRC="img11.gif"><BR>
<P>
where <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline646" SRC="img12.gif"> is user defined.
<P>
(Taken from [<A HREF="reference.html#vapnik95">Vap95</A>])
<LI> 6. Two layer neural network:
<P>
<BR><IMG WIDTH=311 HEIGHT=34 ALIGN=BOTTOM ALT="displaymath648" SRC="img13.gif"><BR>
<P>
where <I>b</I> and <I>c</I> are user defined.
<P>
(Taken from [<A HREF="reference.html#vapnik95">Vap95</A>])
<LI> 7. Linear splines with an infinite number of points:
<P>
For the one-dimensional case:
<P>
<BR><IMG WIDTH=482 HEIGHT=37 ALIGN=BOTTOM ALT="displaymath654" SRC="img14.gif"><BR>
<P>
For the multi-dimensional case <IMG WIDTH=187 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline656" SRC="img15.gif">
<P>
(Taken from [<A HREF="reference.html#vladgolo">VGS</A>])
<LI> 8. Full polynomial kernel:
<P>
<BR><IMG WIDTH=289 HEIGHT=29 ALIGN=BOTTOM ALT="displaymath658" SRC="img16.gif"><BR>
<P>
where <I>a</I>, <I>b</I> and <I>d</I> are user defined.
<P>
(From [<A HREF="reference.html#vapnik95">Vap95</A>] and generalized)
<LI> 9. Regularized Fourier (weaker mode regularization)
<P>
For the one-dimensional case:
<P>
<BR><IMG WIDTH=309 HEIGHT=49 ALIGN=BOTTOM ALT="displaymath666" SRC="img17.gif"><BR>
<P>
where <IMG WIDTH=126 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline548" SRC="img3.gif"> and <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline646" SRC="img12.gif"> is user defined.
<P>
For the multi-dimensional case <IMG WIDTH=187 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline656" SRC="img15.gif">
<P>
(From [<A HREF="reference.html#vladgolo">VGS</A>] and [<A HREF="reference.html#vlad98">Vapng</A>])
<LI> 10. Semi Local Kernel
<P>
<BR><IMG WIDTH=369 HEIGHT=20 ALIGN=BOTTOM ALT="displaymath674" SRC="img18.gif"><BR>
<P>
where <I>d</I> and <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline678" SRC="img19.gif"> are user defined and weight between global and
local approximation.
<P>
(From private communications with V. Vapnik)
<LI> 11. Regularized Fourier (stronger mode regularization)
<P>
For the one-dimensional case:
<P>
<BR><IMG WIDTH=343 HEIGHT=41 ALIGN=BOTTOM ALT="displaymath680" SRC="img20.gif"><BR>
<P>
where <IMG WIDTH=126 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline548" SRC="img3.gif"> and <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline646" SRC="img12.gif"> is user defined.
<P>
For the multi-dimensional case <IMG WIDTH=187 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline656" SRC="img15.gif">
<P>
(From [<A HREF="reference.html#vladgolo">VGS</A>] and [<A HREF="reference.html#vlad98">Vapng</A>])
<LI> 17. Anova 1
<P>
<BR><IMG WIDTH=374 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath688" SRC="img21.gif"><BR>
<P>
where the degree <I>d</I> and <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline646" SRC="img12.gif"> are user defined.
<P>
(From private communications with V. Vapnik)
<LI> 18. Generic Kernel 1
<P>
This is a kernel intended for experiments, just modify the appropriate
function in kernel_generic_1_c.C. You can use the parameters a_val,
b_val, c_val, d_val and e_val.
<LI> 19. Generic Kernel 2
<P>
This is a kernel intended for experiments, just modify the appropriate
function in kernel_generic_2_c.C. You can use the parameters a_val,
b_val, c_val, d_val and e_val.
<P>
</UL><H1><A NAME="SECTION000120000000000000000">Input file format</A></H1>
<P>
This is just a brief description of the input file format for the
training and testing data. A detailed
description is given in the next section.
<P>
<H2><A NAME="SECTION000121000000000000000">ASCII input</A></H2>
<P>
The input files consist of a simple header and the actual data. When
saving files additional data is added to the header, but this can be
safely ignored.
<P>
The simplest input files are pure ASCII and only contain numbers. 
The first number specifies the number of examples in the file, the