readme.txt

把 sequential 有导师学习问题转化为传统的有导师学习问题

The Recurrent Sliding Window Classifier (RSW) is to be used with the WEKA 
machine learning package. WEKA has been developed at the Computer Science 
Department, University of Waikato ,NZ. 

1. An introduction to sequential data classification and recurrent sliding 
windows:

	The standard supervised learning problem is to learn to map from
an input feature vector x to an output class variable y given N training
examples.  Many recent learning problems can be viewed as extensions of
standard supervised learning to the setting where each input object X is
a sequence of feature vectors X = (x1, ..., xT), and the corresponding
output object Y is a sequence of class labels Y = (y1, ..., yT).  The
sequential supervised learning (SSL) problem is to learn to map from X
to Y given a set of N training examples {(X1,Y1), ..., (XN, YN)}.

	Several recent learning systems involved solving SSL
problems. One example is the famous NETTalk problem of learning to
pronounce English words.  Each training example consists of a sequence
of letters (e.g., ``enough'') and a corresponding output sequence of
phonemes (e.g., In^-f-).  Another example is the problem of
part-of-speech tagging in which the input is a sequence of words (e.g.,
``do you want fries with that?'') and the output is a sequence of parts
of speech (e.g., ``verb pron verb noun prep pron'').  A third example is
the problem of information extraction from web pages in which the input
sequence is a sequence of tokens from a web page and the output is a
sequence of field labels.

	In the literature, two general strategies for solving SSL
problems have been studied.  One strategy, which we might call the
``direct'' approach, is to develop probabilistic models of sequential
data such as Hidden Markov Models (HMMs) and Conditional Random Fields
(CRFs).  These methods directly learn a model of the sequential data.

         The other general strategy that has been explored might be
called the ``indirect'' approach (i.e., a ``hack'').  In this strategy,
the sequential supervised learning problem is solved indirectly by first
converting it into a standard supervised learning problem, solving that
problem, and then converting the results into a solution to the SSL
problem. Specifically, the indirect approach is to convert the input
sequence X and output sequence Y into a set of ``windows'' {w1, ..., w6}
as shown in the table below.  Each window wt consists of a central
element xt and some number of elements to the left and right of xt.  The
output of the window is the corresponding label yt.  We will denote the
number of elements to the left of xt as the Left Input Context (LIC),
and the number of elements to the right of xt as the Right Input Context
(RIC).  In the example, LIC=RIC=3.  Contextual positions before the
start of the sequence or after the end of the sequence are filled by a
designated null value (in this case "_").

Simple Sliding Windows:
 original SSL training example: (X, Y) where X = "enough" and Y = "In^-f-"
 derived windows:       input elements:      output class label:
 w1		 	_ _ _ e n o u  		I
 w2                     _ _ e n o u g		n
 w3 			_ e n o u g h		^
 w4 			e n o u g h _		-
 w5 			n o u g h _ _		f
 w6  			o u g h _ _ _		-

In this example, each input element is a single character, but in
general, each input element can be a vector of features.

The process of converting SSL training examples into windows is called
"windowizing".  The resulting windowized examples can be provided as
input to any standard supervised learning algorithm which will learn a
classifier that takes an input window and predicts an output class.  The
RSW package can then take this classifier and apply it to classify
additional windowized SSL examples.  RSW computes two measures of error
rate: (i) error rate on individual windows and (ii) error rate on entire
sequences.  An entire (X,Y) sequence is classified incorrectly if any of
its windows are misclassified.

The RSW package also supports recurrent sliding windows.  In recurrent
sliding windows, the predicted output of the window classifier at
positions t-1, t-2, ..., are provided as additional input features to
make predictions at position t.   These additional input features are
called the Output Context.  Recurrent Sliding Windows require that the
X sequence be processed in one direction, either from left-to-right or
right-to-left.  If the sequence is processed left-to-right, the Left
Output Context (LOC) specifies the number of previous positions whose
predictions are fed back as additional inputs.  If the sequence is
processed right-to-left, the Right Output Context (ROC) parameter
specifies the number of positions whose predictions are fed back as
additional inputs.  No more than one of LOC and ROC can be nonzero.  If
LOC=ROC=0, then only simple sliding windows are produced.

The table below shows the case for LOC=1 (and LIC=RIC=3 as before).
When the training data are windowized, the correct label for yt-1 is
provided as an input feature for predicting yt.  

Recurrent Sliding Windows
(X, Y)			enough			In^-f-

 w1		 	_ _ _ e n o u - 	I
 w2                     _ _ e n o u g I		n
 w3 			_ e n o u g h n		^
 w4 			e n o u g h _ ^		-
 w5 			n o u g h _ _ -		f
 w6  			o u g h _ _ _ f		-

These windowized examples can then be provided to a standard supervised
learning algorithm which learns to map the input windows to the output
labels.  The learned function can then be applied by RSW to classify new
(X,Y) sequences.  The new test sequences are windowized dynamically, by
using the predicted value yhat at position t-1 as the extra input
feature to predict yt.  As with simple sliding windows, two error rates
are computed:  (i) the fraction of individual elements incorrectly
predicted, and (ii) the fraction of entire (X,Y) sequences incorrectly
predicted. 

2. Structure of the ARFF file for sequential data:

For RSW, the ARFF file contains one example for each element of each
training sequence.  The data file has the standard ARFF format with the
following extensions:

The first attribute in each line must be the sequence number.  Each
training example (X,Y) is assigned a unique sequence number (in
ascending order counting from 1).  The second attribute in each line
must be the element number.  Each position (xt,yt) for t = 1, ..., T
(where T is the length of X and Y) must be assigned an element number
(in ascending order counting from 1).  The remaining attributes in each
line provide features that describe xt and the class label yt.  The
following example ARFF file shows two training sequences (bad, BAD) and
(feed, FEED).  Note that each attribute and the class variable must
specify an extra null value that is used to pad context that extends
beyond the end of the sequence.  In this case, we have specified the
null value "_".

@relation SampleSequentialData

@attribute sequence_number numeric
@attribute element_number numeric
@attribute feature1 {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_}
@attribute class {A1, B1, C1, D1, E1, F1, _}

@data
1, 1, b, B1
1, 2, a, A1
1, 3, d, D1
2, 1, f, F1
2, 2, e, E1
2, 3, e, E1
2, 4, d, D1

	The type for the sequence_number and element_number attributes
must be numeric. The sequence numbers must start with 1 and proceed
serially without any breaks or jumps in increasing order.  The element
numbers inside each sequence also must start at 1 and proceed serially
in increasing order until the end of the sequence.  The class attribute
must be nominal. RSW converts the data structured as above into the
windowized data as shown in the previous section. The non-nominal
attributes remain unmodified.


3. Using RSW from the command line:

RSW is a meta classifier (like Bagging and AdaBoostM1).
Therefore, it requires a base classifier. To run RSW from the command
line do the following:

Preparation steps:
1. Move the files RSW.java and RSW.class to the directory weka/classifiers/meta
2. Move the files SequentialClassifier.java and SequentialClassifier.class to 
the directory weka/classifiers
3. Move the files DistributionSequentialClassifier.java and 
DistributionSequentialClassifier.class to the directory weka/classifiers	 
4. Move the files SequentialEvaluation.java and SequentialEvaluation.class to 
the directory weka/classifiers
5. Move the files Windowise.java and Windowise.class to the directory 
weka/classifiers
6. Change your working directory to the directory holding the weka package.
7. Run RSW like any other classifier with its command line options: 
	java RSW {options}

RSW takes all options taken by any other classifier eg. -t "train.arff" -T 
"test.arff" etc. In addition to these, RSW requires 5 mandatory options. 
-W name of base classifier
-A left input context for sliding window
-B right input context for sliding window
-Y left output context for sliding window
-Z right output context for sliding window


4. Using RSW from the GUI:
	The directory weka/gui contains a file named GenericObjectEditor.props. 
In that file, below the lines saying  

# Lists the Classifiers I want to choose from

there is a list of all the classifiers that may appear in the drop-down list of 
the GUI Explorer. Insert the following line as part of that list and save the 
file.
weka.classifiers.meta.RSW, \

Now open the GUI Explorer and use the RSW classifier just as you would
use any other classifier. 


5. Parameter Selection with RSW using cross-validation:

In our experience, it is important to carefully choose the size of the
input and output contexts to obtain good results.  If the contexts are
too large, performance is damaged because of high variance (overfitting)
by the base learning algorithm.  If the contexts are too small,
performance may be poor because not enough contextual information is
available to the base learning algorithm.  We have observed cases where
the input context should be very small yet the output context is large
and also cases where the output context should be zero and the input
context should be large.  Furthermore, the choice of context may also
depend on whether you seek to maximize the number of elements correctly
classified or the number of entire sequences correctly classified.

A good way to choose the context parameter values (LIC, LOC, RIC, ROC)
is to perform an internal cross-validation on the training data.  RSW
supports this with the SeqCVParameterSelection class. Follow these steps:

1. Move the files SeqCVParameterSelection.java and SeqCVParameterSelection.class
to the directory weka/classifiers/meta.
2. Move the files Instances.java and Instances.class to the directory weka/core. 
You will have to replace the files with the same name already existing in that 
directory. 
3. Use the SeqCVParameterSelection from the command line exactly like you would 
use CVParameterSelection but with RSW as the base classifier. Please note that 
SeqCVParameterSelection will not accept any other base classifier.