Часть 1: Простые матрицы и линейная регрессия
Серия Мотивация
Я был инженером MLOps в течение последних 5 лет, и хотя моя работа не связана с повседневным написанием низкоуровневых функций машинного обучения, я хотел убедиться, что понимаю, как все работает в условиях капот.
В дополнение к этому я хочу учиться/совершенствоваться в Rust. И судя по всему — ты тоже!
Моя цель — изучить rust и получить практическое представление о методах машинного обучения. Для этого я хочу написать очень простую библиотеку, способную взять массив любого размера и измерения, а затем применить к нему несколько очень простых методов машинного обучения. Окончательным тестом будет использование этой библиотеки для глубокого обучения распознаванию изображений.
Начальные замечания
Мой любимый способ научиться чему-либо — начать с наивной точки зрения, а затем столкнуться с проблемами все более сложной сложности и решить их. Таким образом, остается меньше места для любых логических или интеллектуальных скачков, которые обычно расстраивают меня, когда я пытаюсь учиться.
Этот итеративный процесс также помогает в определении направления и основывает процесс разработки на определенной дисциплине, препятствуя работе над вещами, которые не имеют прямого отношения к поставленной задаче.
Я собираюсь следовать этому подходу, поэтому я начну с очень простого и буду делать ошибки (иногда преднамеренные) на этом пути.
Часть 1 Описание
В части 1 этой серии мы начнем абсолютно ни с чем и закончим очень простой структурой Matrix и алгоритмом LinearRegression, который работает с такими Matrix как ввод и вывод.
Какой API мы хотим, чтобы линейная регрессия имела?
Всегда очень хорошо начинать процесс разработки с продумывания того, как будет использоваться наш код. Мы хотим, чтобы наши пользователи могли создавать LinearRegression структуры, что бы они ни включали. Мы хотим, чтобы они могли сопоставить строку LinearRegression с некоторыми данными, и мы хотим, чтобы они могли использовать этот экземпляр LinearRegression для прогнозирования значений для других точек данных. Следующий API — это первое, что приходит на ум.
struct LinearRegression{ /* some fields */ }
impl LinearRegression {
pub fn new() -> Self { todo!() }
pub fn fit(&mut self, x: Matrix, y: Matrix) { todo!() }
pub fn predict(&self, x: f64) -> f64 { todo!() }
}
Какого типа должна быть Матрица?
Матрица представляет собой двумерный массив со строками и столбцами. Очень распространенный способ представления матриц - это вложенный список списков:
let matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9], ];
и мы могли бы очень легко начать с определения нашего типа Matrix как векторов ржавчины!
type Matrix = Vec<Vec<f64>>;
Проблема №1 — сохранение данных в валидности
Используя приведенное выше объявление типа Matrix, мы сразу же сталкиваемся с очень большой проблемой. Что произойдет, если мы напишем такой код?
let input: Matrix = vec![ vec![1], vec![3], vec![4, 5], ]; let output: Matrix = vec![ vec![0], vec![1], vec![2], ]; let regression = LinearRegression::new(); regression.fit(input, output);
input не является допустимой матрицей — ее последняя строка содержит больше элементов, чем строки, предшествующие ей. Что бы мы сделали, если бы попытались использовать эту матрицу для построения нашей линии регрессии? Мы могли бы подтвердить! В этом случае функция fit должна будет вернуть Result , потому что потенциально она может завершиться ошибкой, если переданная матрица недействительна.
impl LinearRegression {
/* ... */
pub fn fit(&mut self, x: Matrix, y: Matrix) -> Result<(), String> {
if !validate_matrix(x) {
return Err("x is not a valid Matrix!".to_owned());
}
if !validate_matrix(y) {
return Err("y is not a valid Matrix!".to_owned());
}
todo!()
}
/* ... */
}
Но в rust есть мощная система типов, и здесь мы можем использовать ее в своих интересах. Как очень хорошо объяснено в разделе Разбирать, не проверять — мы могли бы вместо этого убедиться, что Matrix в нашем коде rust всегда действителен!
Как мы можем сделать это? Обернув Vec<Vec<f64>> в нашу собственную структуру, а затем проанализировав любые данные, которые используются для инициализации Matrix.
struct Matrix {
data: Vec<Vec<f64>>,
}
impl Matrix {
pub fn new(data: Vec<Vec<f64>>) -> Result<Self, String> {
let inner_dim = match data.first() {
Some(first) => first.len(),
None => 0,
};
for (dim, inner_vec) in data.iter().enumerate() {
if inner_vec.len() != inner_dim {
return Err(format!("vector in position {dim} does not match the inferred inner dimension of {inner_dim}"));
}
}
Ok(Self{ data })
}
}
Таким образом, если мы когда-нибудь попытаемся передать неверные данные в функцию Matrix::new, она вернет Result::Error.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_only_valid_matrices() {
// This matrix is fine!
let matrix = Matrix::new(
vec![
vec![1, 2, 3],
vec![1, 2, 3],
vec![1, 2, 3],
]
);
assert!(matrix.is_ok());
// This matrix should not be possible - it's last row has less elements
// than all the other rows
let matrix = Matrix::new(
vec![
vec![1, 2, 3],
vec![1, 2, 3],
vec![1, 2],
]
);
assert!(matrix.is_err());
}
}
Теперь у нас есть уверенность, что если мы примем Matrix в качестве входных данных для нашей функции LinearRegression::fit, она всегда будет действительна! Анализируя данные в момент создания экземпляра, мы можем удалить любую проверку, которая в противном случае была бы необходима.
В том же духе — если мы когда-нибудь создадим нашу структуру LinearRegression следующим образом:
let regression = LinearRegression::new(); /* HERE! */ regression.fit(Matrix::new(vec![vec![1.]]), Matrix::new(vec![vec![10.]]));
между строками 1 и 3 (где я добавил комментарий «ЗДЕСЬ!») линейная регрессия как бы… бесполезна! Его линия еще не была смоделирована на основе каких-либо данных, поэтому она всегда будет возвращать одни и те же (и скорее мусорные) прогнозы. И здесь снова — мы могли бы положиться на пользователя, чтобы убедиться, что он правильно использует нашу библиотеку, но поскольку мы используем ржавчину — мы можем удалить такое «бесполезное» состояние LinearRegression даже при компиляции!
struct LinearRegression { /* some fields */ }
impl LinearRegression {
// The difference is here:
// 1. I removed the `pub fn new` line
// 2. And instead made the `pub fn fit` be the
// entrypoint. I also dropped the `Result` type
// as it's not needed - the `Matrix` type is always valid!
pub fn fit(x: Matrix, y: Matrix) -> Self { todo!() }
pub fn predict(data: Matrix) -> Matrix { todo!() }
}
Проблема 1. Что произойдет, если пользователи нашей библиотеки передают неверные данные в линейную регрессию?
Решение 1. Мы анализируем все данные по мере создания Matrix, чтобы Matrix всегда содержало только действительные данные!
Проблема №2 — выравнивание данных
Эта проблема требует некоторого взгляда в будущее и небольшого прыжка веры. Это связано с формой нашей матрицы, и что произойдет, если мы когда-нибудь захотим расширить ее в будущем? Наша матрица имеет только 2 измерения, но в будущем мы можем захотеть обобщить нашу библиотеку для N-мерных массивов. Кроме того, что произойдет, если мы захотим «изменить» нашу матрицу? Допустим, наша матрица представляет изображение в градациях серого — каждое число f64 представляет собой значение пикселя между 0 и 1, представляющее, насколько оно белое или черное.
Очень пикселизированное изображение, представляющее 0, может выглядеть примерно так, как наша матрица:
let matrix = Matrix::new(
vec![
vec![1, 1, 1],
vec![1, 0, 1],
vec![1, 1, 1],
],
);
Его размеры: 3 x 3. 3 строки и 3 столбца.
Однако в будущем — если мы захотим передать эти данные, например, в нейронную сеть — мы на самом деле захотим объединить эти данные в массив 1 x 9. (Если это не очевидно — здесь требуется небольшой прыжок веры.)
let matrix = matrix.reshape(vec![1, 9]);
Как будет выглядеть такая функция reshape?
impl Matrix {
/* ... */
pub fn reshape(self, new_shape: Vec<usize>) -> Result<Self, String> {
let old_shape: Vec<usize> = self.data.iter().map(|inner| inner.len()).collect();
let old_total_size: usize = old_shape.iter().product();
let new_total_size: usize = new_shape.iter().product();
if old_total_size != new_total_size {
return Err(format!("Matrix of shape {:?} cannot be reshaped into Matrix of shape {:?}", old_shape, new_shape));
}
let mut data = vec![vec![0.0; new_shape[1]]; new_shape[0]];
let mut num_iter = self.data.into_iter().flatten();
for outer_idx in 0..new_shape[0] {
for inner_idx in 0..new_shape[1] {
// .unwrap() here is safe because we already checked that the dimensions match
// if .unwrap() here panics - it means that our old matrix was somehow invalid to begin with,
// and that's a bug with the library, not an error that we should propagate to the user!
data[outer_idx][inner_idx] = num_iter.next().unwrap();
}
}
Ok(Self{ data })
}
}
Вы видите здесь большую проблему? Мы обращаемся к числам из self.data по порядку — num_iter.next() в каждой итерации цикла. Таким образом, сглаженные данные как в старом, так и в новом Matrix будут точно такими же, единственная разница заключается в размерах внешнего и внутреннего Vec. Чтобы прояснить этот момент, рассмотрим следующий пример:
let matrix1 = Matrix::new(vec![vec![1, 2, 3]]); // shape (1 x 3) let matrix2 = Matrix::new(vec![vec![1], vec![2], vec![3]]); // shape (3 x 1)
Данные в matrix1 и matrix2 одинаковы, если бы не тот факт, что мы по-разному «распределяем» их между внешним и внутренним векторами. И хотя все числа внутри matrix1 и matrix2 одинаковы — нам нужно воссоздавать (копировать) внутренний и внешний векторы при каждом изменении формы. Это пустая трата времени — именно из-за найденного нами инварианта (номера по порядку совпадают). Вместо того, чтобы копировать все числа при каждом изменении формы, что, если бы вместо этого мы сохранили числа в плоской форме для начала, а чтобы узнать, каковы внутренние и внешние измерения, мы могли бы сохранить форму вместе с данными вот так :
struct Matrix {
data: Vec<f64>,
shape: [usize; 2],
}
fn check_shape_matches_data(data_size: usize, new_shape: &[usize; 2]) -> Result<(), String> {
let shape_size = new_shape[0] * new_shape[1];
if data_size != shape_size {
return Err(format!("shape {new_shape:?} doesn't match data of size {data_size}"));
}
Ok(())
}
impl Matrix {
pub fn new(data: Vec<f64>, shape: [usize; 2]) -> Result<Self, String> {
check_shape_matches_data(data.len(), &shape)?;
Ok(Self { data, shape })
}
pub fn reshape(mut self, new_shape: [usize; 2]) -> Result<Self, String> {
check_shape_matches_data(self.data.len(), &new_shape)?;
self.shape = new_shape;
Ok(self)
}
}
[usize; 2] похоже на Vec<usize>, но мы гарантируем, что оно всегда будет иметь ровно 2 элемента (поскольку наша матрица имеет только 2 измерения). Вы можете видеть, как теперь нам просто нужно сравнить общий размер data vec с формой (как в Matrix::new, так и в Matrix::reshape. Нам не нужно перебирать какие-либо внутренние векторы и проверять, совпадают ли внутренние размеры и т. д. (В в будущем — когда мы обобщим на N-меры — мы также увидим, как отсутствие вложенных векторов упрощает это обобщение. Вы уже видите, как?).
Но самое главное — функция Matrix::reshape теперь вообще не манипулирует базовыми данными матрицы! Каждое изменение формы теперь очень дешевая операция.
Проблема 2: изменение матрицы на основе вложенных Vec относительно сложно и дорого.
Решение 2. Выровняйте поле data и сохраните shape рядом!
Проблема №3 — доступ к данным
Наш Matrix выглядит все лучше и лучше! Но поскольку мы остановились на довольно хорошем базовом решении того, как данные будут храниться, нам нужно начать думать о том, как к ним будет осуществляться доступ. Вы видите в настоящее время, если мы хотим сделать что-то вроде этого:
let matrix = Matrix::new(vec![1, 2, 3], [3, 1]).unwrap(); do_something_with_data(matrix.data); do_something_with_shape(matrix.shape);
мы получим ошибку! Ни data, ни shape не являются публичными полями! Поэтому мы не можем получить к ним прямой доступ, пока не сделаем их общедоступными. Должны ли мы это сделать?
struct Matrix {
pub data: Vec<f64>,
pub shape: [usize; 2],
}
Это ужасная идея! Рассмотрим следующий пример:
let mut matrix = Matrix::new(vec![1, 2, 3], [3, 1]).unwrap(); matrix.data.push(10);
Вы видите, что не так? Теперь мы разрешили пользователям Matrix аннулировать его внутреннюю согласованность. data и shape не совпадают, и ничто не мешает этому! Мы нарушили наш контракт — Matrix недействительно всегда!
Альтернативой является использование инкапсуляции — держите поля закрытыми и предоставляйте функциональность только по мере необходимости через связанные функции и методы. Одной из таких функций может быть возможность видеть форму нашей матрицы (без возможности изменить ее — reshape уже предоставляет это).
struct Matrix {
data: Vec<f64>,
shape: [usize; 2],
}
impl Matrix {
/* ... */
pub fn get_shape(&self) -> &[usize; 2] {
&self.shape
}
}
Сладкий! Красиво и просто!
Но что, если бы мы захотели посмотреть, какие значения находятся в поле data, или что, если бы мы захотели их изменить?
Заманчиво начать писать что-то вроде этого:
impl Matrix {
/* ... */
pub fn get(&self, index: [usize; 2]) -> f64 { todo!() }
pub fn get_mut(&mut self, index: [usize; 2]) -> &mut f64 { todo!() }
}
Но мы можем сделать это поведение совместимым с общим оператором индексации Rust, реализовав трейты оператора Index и IndexMut для нашего Matrix.
use std::ops::{Index, IndexMut};
fn convert_index(shape: &[usize; 2], index: &[usize]) -> usize {
index[0] * shape[1] + index[1]
}
impl Index<[usize; 2]> for Matrix {
type Output = f64;
fn index(&self, index: [usize; 2]) -> &Self::Output {
let data_index = convert_index(&self.shape, &index);
&self.data[data_index]
}
}
impl IndexMut<[usize; 2]> for Matrix {
fn index_mut(&mut self, index: [usize; 2]) -> &mut Self::Output {
let data_index = convert_index(&self.shape, &index);
&mut self.data[data_index]
}
}
impl Index<&[usize]> for Matrix {
type Output = f64;
fn index(&self, index: &[usize]) -> &Self::Output {
if index.len() != self.shape.len() {
panic!("index must have length {}", self.shape.len());
}
let data_index = convert_index(&self.shape, index);
&self.data[data_index]
}
}
impl IndexMut<&[usize]> for Matrix {
fn index_mut(&mut self, index: &[usize]) -> &mut Self::Output {
if index.len() != self.shape.len() {
panic!("index must have length {}", self.shape.len());
}
let data_index = convert_index(&self.shape, index);
&mut self.data[data_index]
}
}
Это позволяет пользователям нашего Matrix индексировать его напрямую следующим образом:
let matrix = Matrix::new(vec![1, 2, 3, 4], [2, 2]);
println!("{}", matrix[[1, 0]]); // prints "3"
matrix[[1, 0]] = 10;
println!("{}", matrix[[1, 0]]); // prints "10"
Проблема 3.Пользователи Matrix не могут получить доступ ни к data, ни к shape.
Решение 3.Мы решили оставить поля закрытыми, но предоставить определенные функции, такие как индексирование или заимствование формы, с помощью методов и реализации свойств оператора.
Линейная регрессия
Теперь у нас есть все необходимое для реализации элементарной линейной регрессии. Я собираюсь использовать следующую формулу для моделирования линии регрессии.
LinearRegression::fit принимает два вектора — x и y. x — это входные данные формы [N, 1] — всего N строк — и каждая строка имеет только 1 размер (x на числовой прямой). y — ожидаемый результат. Он должен иметь те же размеры, что и x.
pub struct LinearRegression {
intercept: f64, // a in the equation
coefficient: f64, // b in the equation
}
impl LinearRegression {
pub fn fit(x: Matrix, y: Matrix) -> Self {
let shape_x = x.get_shape();
let shape_y = y.get_shape();
if shape_x[1] != 1 {
panic!("LinearRegression works only with 1 dimensional data points");
}
if shape_y[1] != 1 {
panic!("LinearRegression works only with 1 dimensional data points");
}
if shape_x[0] != shape_y[0] {
panic!("shape of x and y do not match");
}
// Calculate mean_x and mean_y
let n = shape_x[0];
let mut mean_x = 0.;
let mut mean_y = 0.;
for i in 0..n {
mean_x += x[[i, 0]];
mean_y += y[[i, 0]];
}
mean_x /= n as f64;
mean_y /= n as f64;
// Calculate numerator and denominator;
let mut numerator = 0.;
let mut denominator = 0.;
for i in 0..n {
let x_err = x[[i, 0]] - mean_x;
let y_err = y[[i, 0]] - mean_y;
numerator += x_err * y_err;
denominator += x_err * x_err;
}
let coefficient = numerator / denominator;
let intercept = mean_y - coefficient * mean_x;
Self { intercept, coefficient }
}
pub fn predict(&self, x: f64) -> f64 {
self.intercept + x * self.coefficient
}
}
Это работает!
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_predict() {
let regression = LinearRegression { intercept: 5., coefficient: 2.3 };
assert_eq!(regression.predict(10.), 28.);
assert_eq!(regression.predict(99.), 232.7);
}
#[test]
fn test_fit() {
let x = Matrix::new(vec![1., 2., 3., 4., 5., 6.], [6, 1]).unwrap();
let y = Matrix::new(vec![1., 1.25, 1.5, 1.75, 2., 2.25], [6, 1]).unwrap();
let regression = LinearRegression::fit(x, y);
assert_eq!(regression.intercept, 0.75);
assert_eq!(regression.coefficient, 0.25);
assert_eq!(regression.predict(99.), 25.5);
}
}
Следующие шаги
Во второй части я собираюсь очистить наш код линейной регрессии, внедрить дополнительные трейты оператора, чтобы включить арифметические операции над векторами, внедрить широковещательную рассылку и начать обобщать матрицу до N измерений.
Обратная связь
Я @bamwasylow в Твиттере — любой отзыв приветствуется!
