rusty_machine/learning/
svm.rs

1//! Support Vector Machine Module
2//!
3//! Contains implementation of Support Vector Machine using the
4//! [Pegasos training algorithm](http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf).
5//!
6//! The SVM models currently only support binary classification.
7//! The model inputs should be a matrix and the training targets are
8//! in the form of a vector of `-1`s and `1`s.
9//!
10//! # Examples
11//!
12//! ```
13//! use rusty_machine::learning::svm::SVM;
14//! use rusty_machine::learning::SupModel;
15//!
16//! use rusty_machine::linalg::Matrix;
17//! use rusty_machine::linalg::Vector;
18//!
19//! let inputs = Matrix::new(4,1,vec![1.0,3.0,5.0,7.0]);
20//! let targets = Vector::new(vec![-1.,-1.,1.,1.]);
21//!
22//! let mut svm_mod = SVM::default();
23//!
24//! // Train the model
25//! svm_mod.train(&inputs, &targets).unwrap();
26//!
27//! // Now we'll predict a new point
28//! let new_point = Matrix::new(1,1,vec![10.]);
29//! let output = svm_mod.predict(&new_point).unwrap();
30//!
31//! // Hopefully we classified our new point correctly!
32//! assert!(output[0] == 1f64, "Our classifier isn't very good!");
33//! ```
34
35
36use linalg::{Matrix, BaseMatrix};
37use linalg::Vector;
38
39use learning::toolkit::kernel::{Kernel, SquaredExp};
40use learning::{LearningResult, SupModel};
41use learning::error::{Error, ErrorKind};
42
43use rand;
44use rand::Rng;
45
46/// Support Vector Machine
47#[derive(Debug)]
48pub struct SVM<K: Kernel> {
49    ker: K,
50    alpha: Option<Vector<f64>>,
51    train_inputs: Option<Matrix<f64>>,
52    train_targets: Option<Vector<f64>>,
53    lambda: f64,
54    /// Number of iterations for training.
55    pub optim_iters: usize,
56}
57
58/// The default Support Vector Machine.
59///
60/// The defaults are:
61///
62/// - `ker` = `SquaredExp::default()`
63/// - `lambda` = `0.3`
64/// - `optim_iters` = `100`
65impl Default for SVM<SquaredExp> {
66    fn default() -> SVM<SquaredExp> {
67        SVM {
68            ker: SquaredExp::default(),
69            alpha: None,
70            train_inputs: None,
71            train_targets: None,
72            lambda: 0.3f64,
73            optim_iters: 100,
74        }
75    }
76}
77
78impl<K: Kernel> SVM<K> {
79    /// Constructs an untrained SVM with specified
80    /// kernel and lambda which determins the hardness
81    /// of the margin.
82    ///
83    /// # Examples
84    ///
85    /// ```
86    /// use rusty_machine::learning::svm::SVM;
87    /// use rusty_machine::learning::toolkit::kernel::SquaredExp;
88    ///
89    /// let _ = SVM::new(SquaredExp::default(), 0.3);
90    /// ```
91    pub fn new(ker: K, lambda: f64) -> SVM<K> {
92        SVM {
93            ker: ker,
94            alpha: None,
95            train_inputs: None,
96            train_targets: None,
97            lambda: lambda,
98            optim_iters: 100,
99        }
100    }
101}
102
103impl<K: Kernel> SVM<K> {
104    /// Construct a kernel matrix
105    fn ker_mat(&self, m1: &Matrix<f64>, m2: &Matrix<f64>) -> LearningResult<Matrix<f64>> {
106        if m1.cols() != m2.cols() {
107            Err(Error::new(ErrorKind::InvalidState,
108                           "Inputs to kernel matrices have different column counts."))
109        } else {
110            let dim1 = m1.rows();
111            let dim2 = m2.rows();
112
113            let mut ker_data = Vec::with_capacity(dim1 * dim2);
114            ker_data.extend(m1.iter_rows().flat_map(|row1| {
115                m2.iter_rows()
116                    .map(move |row2| self.ker.kernel(row1, row2))
117            }));
118
119            Ok(Matrix::new(dim1, dim2, ker_data))
120        }
121    }
122}
123
124/// Train the model using the Pegasos algorithm and
125/// predict the model output from new data.
126impl<K: Kernel> SupModel<Matrix<f64>, Vector<f64>> for SVM<K> {
127    fn predict(&self, inputs: &Matrix<f64>) -> LearningResult<Vector<f64>> {
128        let ones = Matrix::<f64>::ones(inputs.rows(), 1);
129        let full_inputs = ones.hcat(inputs);
130
131        if let (&Some(ref alpha), &Some(ref train_inputs), &Some(ref train_targets)) =
132               (&self.alpha, &self.train_inputs, &self.train_targets) {
133            let ker_mat = try!(self.ker_mat(&full_inputs, train_inputs));
134            let weight_vec = alpha.elemul(train_targets) / self.lambda;
135
136            let plane_dist = ker_mat * weight_vec;
137
138            Ok(plane_dist.apply(&|d| d.signum()))
139        } else {
140            Err(Error::new_untrained())
141        }
142    }
143
144    fn train(&mut self, inputs: &Matrix<f64>, targets: &Vector<f64>) -> LearningResult<()> {
145        let n = inputs.rows();
146
147        let mut rng = rand::thread_rng();
148
149        let mut alpha = vec![0f64; n];
150
151        let ones = Matrix::<f64>::ones(inputs.rows(), 1);
152        let full_inputs = ones.hcat(inputs);
153
154        for t in 0..self.optim_iters {
155            let i = rng.gen_range(0, n);
156            let row_i = full_inputs.select_rows(&[i]);
157            let sum = full_inputs.iter_rows()
158                .fold(0f64, |sum, row| sum + self.ker.kernel(row_i.data(), row)) *
159                      targets[i] / (self.lambda * (t as f64));
160
161            if sum < 1f64 {
162                alpha[i] += 1f64;
163            }
164        }
165
166        self.alpha = Some(Vector::new(alpha) / (self.optim_iters as f64));
167        self.train_inputs = Some(full_inputs);
168        self.train_targets = Some(targets.clone());
169
170        Ok(())
171    }
172}
rusty_machine/learning/svm.rs

rusty_machine/learning/
svm.rs
