In Machine Learning a wide plethora of learning algorithms have been defined for different purposes and many variations of the existing ones as well as completely new learning methods are often proposed.
Furthermore, learning algorithms can be combined in ensemble methods, composed in meta learning algorithms (like AdaBoost) or used according to particular learning schemas like One-vs-All or One-vs-One schemas for multi-classification. KeLP tries to formalize this large world proposing a comprehensive set of interfaces to support the implementation of new algorithms:
- ClassificationLearningAlgorithm: for algorithms that learn from labelled data how to classify new instances. The current implementations include C-SVM, ν-SVM, OneClassSVM (Chang and Lin, 2011) and Pegasos (Shalev-Shwartz et al., 2007);
- OnlineLearningAlgorithm: for algorithms that support an incremental learning, like the Perceptron (Rosenblatt, 1957) or the PassiveAggressive algorithms (Crammer et al., 2006);
- RegressionLearningAlgorithm: for algorithms that learn from labelled data a regression function. Currently KeLP implements ε-SVR, Linear and Kernelized PassiveAggressiveRegression;
- ClusteringAlgorithm: for algorithms that are able to organize a dataset into clusters. Currently KeLP implements KernelBased K-Means (Kulis et at,. 2005);
- MetaLearningAlgorithm: for learning approaches that rely on another algorithms. We implemented Multi-classification schemas, e.g. One-VS-One and One-VS-All as well as budgeted policies of online learning algorithms like RandomizedPerceptron (Cavallanti et al., 2006) and Stoptron (Orabona et al., 2008)
- EnsembleLearningAlgorithm: for algorithms that combine other algorithms in order to provide a more robust solution
- BinaryLearningAlgorihm: this interface is implemented to derive binary classifiers. Notice that also One-Class classifier can extend this interface as they learn a binary classifier even being not provided of negative examples. Moreover, this interface can be used also to implement univariate regression algorithms, such as ε-SVR. (Chang and Lin, 2011)
Algorithms exploiting kernel functions must implement the interface KernelMethod, while algorithms operating directly in an explicit feature space must implement the interface LinearMethod. In describing how to implement a new LearningAlgorithm, we will use the mini-batch version of Pegasos as a practical example. In its base version, Pegasos is an efficient solver for linear binary SVM; then we have to implement ClassificationLearningAlgorithm, BinaryLearningAlgorithm and LinearMethod. Optionally, the class can be annotated with @JsonTypeName in order to specify an alternative “name type” to be used during the serialization/deserialization mechanism.
|
1 2 |
@JsonTypeName("pegasos") public class PegasosLearningAlgorithm implements LinearMethod, ClassificationLearningAlgorithm, BinaryLearningAlgorithm{ |
KeLP decouples learning algorithms from prediction functions that are used to provide predictions on new data. Regarding PegasosLearningAlgorithm, the proper prediction function is BinaryLinearClassifier, that is already implemented in the platform. Then, we have to add a new corresponding parameter, i.e. classifier. An empty constructor must be defined and all the learning parameters must be associated to the corresponding getter and setter methods, in order to make the JSON serialization/deserialization mechanism work. In this case, the learning parameters are the regularization coefficient lambda, the number of iterations T, the number of examples k exploited during each mini-batch iteration.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
private BinaryLinearClassifier classifier; private int k = 1; private int iterations = 1000; private float lambda = 0.01f; /** * Returns the number of examples k that Pegasos exploits in its * mini-batch learning approach * * @return k */ public int getK() { return k; } /** * Sets the number of examples k that Pegasos exploits in its * mini-batch learning approach * * @param k the k to set */ public void setK(int k) { this.k = k; } /** * Returns the number of iterations * * @return the number of iterations */ public int getIterations() { return iterations; } /** * Sets the number of iterations * * @param T the number of iterations to set */ public void setIterations(int T) { this.iterations = T; } /** * Returns the regularization coefficient * * @return the lambda */ public float getLambda() { return lambda; } /** * Sets the regularization coefficient * * @param lambda the lambda to set */ public void setLambda(float lambda) { this.lambda = lambda; } public PegasosLearningAlgorithm(){ this.classifier = new BinaryLinearClassifier(); this.classifier.setModel(new BinaryLinearModel()); } |
According to the selected interfaces some specific methods have to be implemented. As any LinearMethod we need to implement setRepresentation and getRepresentation which refer to the String identifier for the specific Representation the algorithm must exploit. Obviously a corresponding parameter must created, i.e. representation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
private String representation; @Override public String getRepresentation() { return representation; } @Override public void setRepresentation(String representation) { this.representation = representation; BinaryLinearModel model = this.classifier.getModel(); model.setRepresentation(representation); } |
As any BinaryLearningAlgorithm we need to implement getLabel and setLabel which refer to the Label that must considered as positive class. Obviously a corresponding parameter must created, i.e. label. Moreover, to be compliant with the LearningAlgorithm interface, the methods getLabels and setLabels must be implemented that, for the special case of BinaryLearningAlgorithm must operated on a single entry List:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
private Label label; @Override public void setLabels(List<label> labels){ if(labels.size()!=1){ throw new IllegalArgumentException("Pegasos algorithm is a binary method which can learn a single Label"); } else{ this.label=labels.get(0); this.classifier.setLabels(labels); } } @Override public List<label> getLabels() { return Arrays.asList(label); } @Override public Label getLabel(){ return this.label; } @Override public void setLabel(Label label){ this.setLabels(Arrays.asList(label)); } </label></label> |
Finally, as any ClassificationLearningAlgorithm we need to implement:
- getPredictionFunction: the proper prediction function must be returned, in this case the classifier object. It is a good practice to specialize the returning type, i.e. the method must return a BinaryLinearClassifier instead of a generic Classifier;
- duplicate: the instance of an algorithm must be created and returned, copying all the learning parameters (the state variables must not be set to their default value). It is a good practice to specialize the returning type, i.e. the method must return a PegasosLearningAlgorithm instead of a generic LearningAlgorithm;
- reset: it must force the algorithm to it default state, forgetting the learning process already conducted;
- learn: this method must implement the learning process of Pegasos.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
@Override public BinaryLinearClassifier getPredictionFunction(){ return this.classifier; } @Override public PegasosLearningAlgorithm duplicate() { PegasosLearningAlgorithm copy = new PegasosLearningAlgorithm(); copy.setK(k); copy.setLambda(lambda); copy.setIterations(iterations); copy.setRepresentation(representation); return copy; } @Override public void reset() { this.classifier.reset(); } @Override public void learn(Dataset dataset) { if(this.getPredictionFunction().getModel().getHyperplane()==null){ this.getPredictionFunction().getModel().setHyperplane(dataset.getZeroVector(representation)); } for(int t=1;t<=iterations;t++){ List A_t = dataset.getRandExamples(k); List A_tp = new ArrayList(); List signA_tp = new ArrayList(); float eta_t = ((float)1)/(lambda*t); Vector w_t = this.getPredictionFunction().getModel().getHyperplane(); //creating A_tp for(Example example: A_t){ BinaryMarginClassifierOutput prediction = this.classifier.predict(example); float y = -1; if(example.isExampleOf(label)){ y=1; } if(prediction.getScore(label)*y<1){ A_tp.add(example); signA_tp.add(y); } } //creating w_(t+1/2) w_t.scale(1-eta_t*lambda); float miscassificationFactor = eta_t/k; for(int i=0; i < A_tp.size(); i++){ Example example = A_tp.get(i); float y = signA_tp.get(i); this.getPredictionFunction().getModel().addExample(y*miscassificationFactor, example); } //creating w_(t+1) float factor = (float) (1.0/Math.sqrt(lambda)/Math.sqrt(w_t.getSquaredNorm())); if(factor < 1){ w_t.scale(factor); } } } |
References:
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.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub–gradient solver for SVM. In Proceedings of the International Conference on Machine Learning, 2007
Rosenblatt, Frank, The Perceptron–a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory, 1957.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. On- line passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585, December 2006. ISSN 1532-4435.
Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. Semi-supervised graph clustering: A kernel approach. In Proceedings of the ICML 2005, pages 457–464, New York, NY, USA, 2005. ACM.
Giovanni Cavallanti, Nicolo’ Cesa-Bianchi and Claudio Gentile. Tracking the best hyperplane with a simple budget perceptron. In proc. of the nineteenth annual conference on Computational Learning Theory. pp. 483–498. Springer-Verlag (2006)
Orabona, F., Keshet, J., Caputo, B.: The projectron: a bounded kernel-based perceptron. In Proceedings of ICML ’08. pp. 720–727. ACM, USA (2008)