Shorelark

В этом туториале мы создадим симуляцию эволюции с помощью нейронной сети и генетического алгоритма.

Я расскажу вам, как работают простая нейронная сеть и генетический алгоритм, затем мы реализуем их на Rust и скомпилируем приложение в WebAssembly.

Предполагается, что вы немного знакомы с Rust, остальное я постараюсь объяснить.

• Исходный код проекта
• Демо приложения

Часть 1

Проект

Начнем с того, что мы будем симулировать.

Основная идея состоит в том, что у нас есть двумерная доска, представляющая мир:

Этот мир состоит из птиц (поэтому проект называется "Shorelark" (береговой жаворонок)):

...и еды (абстрактной, богатой белком и клетчаткой):

Каждая птица обладает зрением, позволяющим обнаруживать еду:

...и мозгом, управляющим ее телом (скоростью и вращением).

Вместо кодирования определенного поведения птиц (например, "иди к ближайшей еде, находящейся в поле зрения"), мы сделаем так, что они будут учиться и эволюционировать.

Мозг

Условно, мозг - это не что иное, как функция от некоторых входных данных к некоторым выходных данным, например:

f(зрение, обоняние, слух, вкус, осязание) = (речь, движение)

Поскольку у наших птиц есть только зрение, их мозг может быть упрощен до:

f(зрение) = движение

Математически мы можем представить входные данные этой функции (биологического глаза) как список чисел, где каждое число (биологический фоторецептор) описывает, как близко находится объект (еда):

(0.0 - в поле зрения нет объектов, 1.0 - объект находится прямо напротив нас)

Наши птицы не видят цвет (для простоты) - вы можете использовать трассировку лучей, чтобы сделать глаза более реалистичными.

В качестве выходных данных функция будет возвращать кортеж (Δspeed, Δrotation).

Например, сообщение от мозга (0.1, 45) означает "тело, ускорься на 0.1 единицы и повернись на 45 градусов по часовой стрелке", а сообщение (0.0, 0) означает "тело, продолжай в том же духе".

Важно, чтобы использовались относительные значения (delta speed и delta rotation), поскольку наш мозг не будет знать о локации и вращении относительно мира - передача этой информации усложнит мозг без реальной выгоды.

Получается, что мозг - это f(глаза), верно? Но f(глаза) = что?

Нейронная сеть: введение

Полагаю, вы знаете, что мозг состоит из нейронов, соединенных синапсами:

Синапсы переносят электрический и химический сигналы между нейронами, а нейроны "решают", должен определенный сигнал передаваться дальше или блокироваться; в конечном счете, это позволяет людям распознавать буквы, есть брюссельскую капусту и писать злобные комментарии в Твиттере.

Из-за внутренней сложности биологические нейронные сети не самая легкая вещь для симуляции, что заставило некоторых умных людей изобрести класс математических структур под названием "искусственные нейронные сети", которые позволяют до некоторой степени аппроксимировать работу мозга с помощью математики.

Искусственные нейронные сети (далее - просто нейронные сети) играют важную роль в обобщении наборов данных (например, изучая, как выглядит кошка), поэтому они широко используются в распознавании лиц (например, для камер), языковом переводе (например, для GNMT) и - в нашем случае - для управления цветными пикселями.

Сеть, которую мы будем использовать, называется "нейронной сетью прямого распространения" (feedforward neural network, FFNN)...

FFNN иногда называют многослойными перцептронами. Они являются одним из строительных блоков сверточных нейронных сетей, таких как DeepDream.

...и выглядит так:

Это макет FFNN с 5 синапсами и 3 нейронами, организованными в 2 слоя: входной (слева) и выходной (справа).

Между этими слоями могут существовать дополнительные слои, которые называются "скрытыми" - они улучшают способность сети к интерпретации входных данных (чем больше мозг, тем "большую абстракцию" он способен понять, до определенной степени).

Похожий процесс происходит в нашей зрительной коре.

В отличие от биологических нейронных сетей (которые переносят электрические сигналы), FFNN принимают некоторые числа и пропускают их через несколько слоев. Числа на последнем слое определяют ответ сети.

Например, если мы скормили сети сырые пиксели изображения, она может ответить следующим:

• 0.0 - это изображение не содержит рыжего кота, поедающего лазанью
• 0.5 - это изображение может содержать рыжего кота, поедающего лазанью
• 1.0 - это изображение точно содержит рыжего кота, поедающего лазанью

Сеть также может возвращать несколько значений (количество выходных значений равняется количеству нейронов в выходном слое):

• (0.0, 0.5) - это изображение не содержит рыжего кота, но может содержать лазанью
• (0.5, 0.0) - это изображение может содержать рыжего кота, но не содержит лазанью

Значение входных и выходных чисел определяется нами - мы готовим так называемый набор обучающих данных ("при получении этого изображения, ты должна возвращать 1.0", "при получении этого изображения, ты должна возвращать 0.0").

Вы даже можете создать сеть для определения зрелых яблок - виды сетей ограничены только вашим воображением.

Двигаемся дальше.

Нейронные сети: глубокое погружение

FFNN зиждется на 2 столпах: нейронах и синапсах.

Нейрон (обычно изображаемый в виде круга) принимает некоторые входные значения, обрабатывает их и возвращает некоторое выходное значение - каждый нейрон имеет минимум один вход и максимум один выход:

Один нейрон с тремя синапсами

Кроме того, каждый нейрон имеет смещение (bias):

Один нейрон с тремя синапсами и смещением

Смещение - это как инструкция if нейрона - оно позволяет нейрону оставаться неактивным (возвращать нуль) до тех пор, пока входное значение не будет выше (строго) смещения. Формально, мы говорим, что смещение позволяет регулировать порог активации (activation threshold) нейрона.

Предположим, что у нас есть нейрон с тремя входными значениями, каждое значение определяет, видит нейрон лазанью (1.0) или нет (0.0). Если мы хотим, чтобы нейрон активировался при виде двух лазаний, мы просто создаем нейрон со смещением -1.0. Таким образом, "обычным" состоянием нейрона будет -1.0 (покой), при виде одной лазаньи - 0.0 (все еще покой), при виде двух лазаний - 1.0 (активация, вуаля).

Если вам не нравится моя метафора с лазаньей, вот математическое объяснение.

Помимо нейронов, у нас есть синапсы - сети, соединяющие выход одного нейрона с входном другого нейрона. Каждый синапс имеет вес (weight):

Один нейрон с тремя синапсами с весами

Вес - это фактор (отсюда x перед каждым числом, подчеркивающий его мультипликативную природу), поэтому вес:

• 0.0 означает, что синапс фактически мертв (он не передает информацию от одного нейрона другому)
• 0.3 означает, что если нейрон А возвращает 0.7, нейрон B получит 0.7 * 0.3 ~= 0.2
• 1.0 означает, что синапс фактически является транзитным - если нейрон A возвращает 0.7, нейрон B получит 0.7 * 1.0 = 0.7

Вернемся к нашей сети и заполним недостающие веса и смещения произвольными числами:

Красиво, не правда ли?

Посмотрим, что наша сеть думает о, скажем, (0.5, 0.8):

Напомню, что нас интересует выходное значение самого правого нейрона (это наш выходной слой). Поскольку он зависит от двух предыдущих нейронов (из входного слоя), начнем с них.

Сначала сфокусируемся на верхнем левом нейроне - для вычисления его выходного значения начнем с вычисления взвешенной суммы (weighted sum) его входных значений:

0.5 * 0.2 = 0.1

...затем добавляем смещение:

0.1 - 0.3 = -0.2

...и фиксируем (clamp) это значение с помощью так называемой функции активации (activation function). Функция активации ограничивает выходное значение нейрона предопределенным диапазоном, симулируя поведение оператора if.

Простейшей функцией активации является линейный выпрямитель (rectified linear unit, ReLU), что по сути является f32::max:

Другой популярной функцией активации является tanh - ее граф выглядит несколько иначе (похож на s), и она имеет другие свойства.

Функция активации влияет на входное и выходное значения. Например, tanh заставляет сеть работать с числами в диапазоне <-1.0, 1.0>, ReLU - в диапазоне <0.0, +inf>.

Как мы видим, когда наша взвешенная сумма со смещением меньше нуля, выходным значением нейрона будет 0.0. Это как раз то, что происходит в нашем случае:

max(-0.2, 0.0) = 0.0

Отлично, теперь разберемся с нижним левым нейроном:

# Взвешенная сумма:
0.8 * 1.0 = 0.8

# Смещение:
0.8 + 0.0 = 0.8

# Функция активации:
max(0.8, 0.0) = 0.8

Вычисление входного слоя завершено:

...что приводит нас к последнему нейрону:

# Взвешенная сумма:
(0.0 * 0.6) + (0.8 * 0.5) = 0.4

# Смещение:
0.4 + 0.2 = 0.6

# Функция активации:
max(0.6, 0.0) = 0.6

...и выводу всей сети:

0.6 * 1.0 = 0.6

Вуаля: для входного значения (0.5, 0.8) наша сеть отвечает 0.6 (в нашем случае это число ничего не значит).

Несмотря на то, что это одна из самых простых FFNN, при наличии соответствующих весов, она способна решить проблему XOR. Но управлять птицей она не может.

Более сложные FFNN, такие как эта:

...работают точно также: мы двигаемся слева направо, нейрон за нейроном, вычисляя выходные значений, пока не получим все числа из выходного слоя (на представленной диаграмме некоторые синапсы пересекаются, но это ничего не значит - это просто неудачное представление многомерных графов на плоском экране).

Вы можете задать вопрос: "Как узнать веса сети?". Ответ прост: в качестве весов используются произвольные значения!

Если вы привыкли к детерминированным алгоритмам (сортировка пузырьком), это может вас раздражать, но так работают сети, состоящие более чем из нескольких нейронов: мы скрещиваем пальцы, рандомизируем начальные веса и работаем с тем, что получили.

Обратите внимание, я сказал начальные веса - некоторые ненулевые веса. Существуют алгоритмы, позволяющие улучшить сеть (по сути, обучить ее).

Одним из самых популярных "обучающих" алгоритмов для FFNN является обратное распространение (backpropagation):

Мы показываем сети много (сотни тысяч) примеров в форме "для этого входного значения, ты должна возвращать это", и алгоритм медленно меняет веса сети до тех пор, пока не получит правильные ответы.

Или нет - сеть может застрять в локальном оптимуме и перестать учиться.

Обратное распространение - это пример обучения с учителем (supervised learning).

Обратное распространение - отличный инструмент, когда у нас имеется большой набор размеченных примеров (таких как фотографии или статистика), поэтому он нам не подходит: мы хотим, чтобы наши птицы учились всему самостоятельно.

Решение?

Генетические алгоритмы и магия больших чисел.

Генетический алгоритм: введение

С математической точки зрения наша основная проблема состоит в том, что у нас есть функция (представленная с помощью нейронной сети), которая определяется с помощью большого количества параметров:

Если каждый параметр будет представлен числом с плавающей точкой одинарной точности, сеть, состоящая всего из 3 нейронов и 5 синапсов, можно определить в таком количестве разных комбинаций...

(3.402 * 10^38) ^ (3 + 5) ~= 1.8 * 10^308

Сколько здесь чисел с плавающей точкой?

...что тепловая смерть Вселенной наступит быстрее, чем мы закончим их проверять - нам нужно быть умнее!

Все возможные наборы параметров называются пространством поиска (search space).

Поскольку перебор нашего пространства поиска в поисках единственного лучшего ответа не обсуждается, мы можем сосредоточиться на гораздо более простой задаче - поиске списка неоптимальных ответов.

И для этого нам нужно погрузиться глубже.

Генетический алгоритм: глубокое погружение

Это дикая морковь и ее одомашненная форма:

Эта одомашненная широко известная форма не появилась из ниоткуда, она является результатом сотен лет искусственного отбора по определенным критериям, таким как текстура или цвет корня.

Было бы здорово, если бы мы могли проделать тоже самое с нашими нейронными мозгами. Если мы создадим группу произвольных птиц и выборочно отберем тех, которые кажутся наиболее приспособленными... хм.

Оказывается, мы не первые, кому в голову пришла эта идея - существует целая отрасль информатики, называемая "эволюционными вычислениями", которая занимается решением проблем "точно так, как это делает природа".

Из всех эволюционных алгоритмов конкретный подкласс, который мы будем изучать, называется "генетическим алгоритмом".

Как и в случае с нейронными сетями, нет одного генетического алгоритма - существует множество разных алгоритмов. Поэтому, мы рассмотрим, как все работает в целом.

Генетический алгоритм начинается с популяции:

Популяция состоит из особей (individuals) (иногда называемых агентами (agents)):

Особь - это одно возможное решение определенной задачи (отсюда популяция - это набор возможных решений).

В нашем случае каждая особь будет моделировать мозг (или всю птицу, если угодно), но обычно это зависит от проблемы, которую вы решаете:

• если мы пытаемся эволюционировать антенну, особь будет одной антенной
• если мы пытаемся эволюционировать план запроса, особь будет одним планом запроса

Особь представляет некоторое решение, не обязательно лучшее.

Особь состоит из генов (совокупность генов особи называется геномом):

Геном представлен весами нейронной сети. Геном может быть списком чисел, графом или чем угодно, что способно моделировать решение задачи

Ген - это единичный параметр, который эволюционирует и настраивается генетическим алгоритмом.

В нашем случае каждый ген будет просто весом нейронной сети, но представление предметной области не всегда является настолько простым.

Например, если мы пытаемся помочь приятелю коммивояжеру, и основная проблема вообще не основана на нейронных сетях, одиночный ген может представлять собой кортеж координат (x, y), определяющий часть пути коммивояжера (в этом случае особь будет описывать весь его путь):

Теперь предположим, что у нас есть произвольная популяция из 50 птиц - мы передаем их генетическому алгоритму, что происходит?

Как и в случае с искусственным отбором, генетический алгоритм начинает с оценки каждой особи (каждого из возможных решений), чтобы определить, какие из них являются лучшими для текущей популяции.

С биологической точки зрения это эквивалентно прогулке по саду и проверке, какая морковь самая оранжевая и вкусная.

Оценка происходит с использованием так называемой функции приспособленности (fitness function), которая возвращает оценку приспособленности (fitness score), количественно определяющую, насколько хороша конкретная особь (то есть конкретное решение):

Пример фитнес-функции, которая количественно оценивает морковь по цвету и радиусу ее корня

Создание пригодной для использования функции приспособленности - одна из самых сложных задач, когда дело касается генетических алгоритмов, поскольку обычно существует множество показателей, по которым можно оценивать особь.

Даже наша воображаемая морковка имеет как минимум три показателя: цвет, радиус корня и вкус, и все их нужно свести в одно число.

К счастью, когда дело касается птиц, нам особо не из чего выбирать: "качество" птицы определяется количеством пищи, которую она съела в течение текущего поколения.

Птица, съевшая 30 единиц еды, лучше той, которая съела всего 20 - вот и все.

Отрицание функции приспособленности заставляет генетический алгоритм возвращать худшие решения вместо лучших - просто забавный трюк, который стоит запомнить на будущее.

Теперь пришло время для главного генетического алгоритма: воспроизводства (reproduction)!

В широком смысле воспроизводство - это процесс создания новой (в идеале, несколько улучшенной) популяции, на основе нынешней.

Это математический эквивалент выбора самой вкусной моркови и посадки ее семян.

Происходит следующее: генетический алгоритм произвольно выбирает двух особей (отдавая предпочтение тем, у которых более высокие показатели приспособленности) и использует их для создания двух новых особей (так называемого потомства (offspring)):

Потомство получается путем взятия геномов обоих родителей и проведения над ними скрещивания (crossover - кроссинговер) и мутации:

Скрещивание позволяет смешивать два разных генома для получения приблизительного промежуточного решения, а мутация позволяет обнаруживать новые решения, которых не было в исходной популяции.

Обе новые особи попадают в new population (новую популяцию), и процесс повторяется, пока не будет создана вся новая популяция. Затем текущая популяция отбрасывается, и все моделирование повторяется с этой новой (в идеале, улучшенной) популяцией.

Как видите, в этом процессе много случайностей: мы начинаем c произвольной популяции, рандомизируем распределение генов…​ ​это не может работать, не так ли?

Часть 2

В этой части мы заложим основы нашего проекта и реализуем простую FFNN (feedforward neural network - нейронная сеть прямого распространения), которая впоследствии станет мозгом. Мы также рассмотрим множество тонкостей и идиом, которые встречаются в коде Rust, включая тесты.

Настройка

Создаем новый проект:

mkdir shorelark
cd shorelark

Прежде всего, нам нужно определить, какую версию набора инструментов (toolchain) мы будем использовать - в противном случае, некоторые части кода могут работать не так, как ожидается.

По состоянию на март 2024 года последней стабильной версией Rust является 1.76, поэтому создаем файл rust-toolchain следующего содержания:

1.76.0

Теперь самое сложное - нам нужно определиться со структурой нашего проекта. Поскольку он будет состоять из множества независимых подмодулей (таких как нейронная сеть и генетический алгоритм), нам пригодится рабочая область (workspace):

# Cargo.toml
[workspace]
resolver = "2"

members = [
    "libs/*",
]

Это означает, что вместо обычного src/main.rs, мы создадим директорию libs и поместим туда наши библиотеки (крейты):

mkdir libs
cd libs
cargo new neural-network --name lib-neural-network --lib

Существует много подходов к организации рабочих пространств. Вместо того, чтобы хранить все в директории libs, можно хранить все в директории crates. Или можно создать две отдельные директории: одну для крейтов приложения, другую — для крейтов библиотек:

project
├─ Cargo.toml
├─ app
│  ├─ Cargo.toml
│  └─ src
│      └─ main.rs
└─ libs
   ├─ subcrate-a
   │  ├─ Cargo.toml
   │  └─ src
   │     └─ lib.rs
   └─ subcrate-b
      ├─ Cargo.toml
      └─ src
         └─ lib.rs

Разработка propagate()

Пора заняться делом.

Начнем сверху вниз со структуры, моделирующей сеть - она обеспечит точку входа в наш крейт. Редактируем lib.rs:

// libs/neural-network/src/lib.rs
#[derive(Debug)]
pub struct Network;

Самая важная операция нейронной сети - распространение (передача) чисел:

...поэтому:

#[derive(Debug)]
pub struct Network;

impl Network {
    pub fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        todo!()
    }
}

Некоторые языки программирования позволяют оставлять разрабатываемые функции пустыми:

int get_berry_number() {
    // TODO решить парадокс
}

но эквивалентный код Rust не будет компилироваться:

fn berry_number() -> usize {
    // TODO решить парадокс
}

error[E0308]: mismatched types
 --> src/lib.rs
  |
1 | fn berry_number() -> usize {
  |    ------------      ^^^^^ expected `usize`, found `()`
  |    |
  |    implicitly returns `()` as its body has no tail or `return`
  |    expression

Это объясняется тем, что почти все в Rust является выражением:

// это выражение
let value = if condition {
    "computer says yass"
} else {
    "computer says no"
};

// и это выражение
let value = loop {
    break 123;
};

let value = {
    // пустой блок - это тоже выражение
};

...поэтому Rust видит эту функцию так:

fn berry_number() -> usize {
    return ();
}

() называется единичным значением (unit value) (или единичным типом (unit type), в зависимости от контекста).

Rust предоставляет два макроса, позволяющие пометить функцию как находящуюся в процессе разработки: todo!() и устаревший unimplemented!().

Оба макроса позволяют компилировать код и, если встречаются во время выполнения, приводят к безопасному сбою приложения:

thread 'main' panicked at 'not yet implemented'

Подобно океану, состоящему из капель, сеть состоит из слоев:

...поэтому:

#[derive(Debug)]
pub struct Network {
    layers: Vec<Layer>,
}

#[derive(Debug)]
struct Layer;

Слои состоят из нейронов:

...поэтому:

#[derive(Debug)]
struct Layer {
    neurons: Vec<Neuron>,
}

Наконец, нейроны содержат смещения (biases) и выходные (output) веса:

#[derive(Debug)]
struct Neuron {
    bias: f32,
    weights: Vec<f32>,
}

Взглянем на наш начальный проект целиком:

#[derive(Debug)]
pub struct Network {
    layers: Vec<Layer>,
}

impl Network {
    pub fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        todo!()
    }
}

#[derive(Debug)]
struct Layer {
    neurons: Vec<Neuron>,
}

#[derive(Debug)]
struct Neuron {
    bias: f32,
    weights: Vec<f32>,
}

Отлично.

Вы могли заметить, что только два объекта являются общедоступными (pub): Network и Network:propagate().

Это связано с тем, что Layer и Neuron останутся деталями реализации, мы не будем делать их общедоступными.

Благодаря такому подходу мы сможем вносить изменения в нашу реализацию, не навязывая критических изменений другим крейтам (пользователям нашей библиотеки).

Например, настоящие нейронные сети обычно реализуются с помощью матриц - если мы решим переписать нашу сеть для использования матриц, это не будет критическим изменением: сигнатура Network:propagate() останется прежней, а поскольку пользователи не имеют доступа к Layer и Neuron, они не заметят их исчезновения.

Далее, поскольку числа необходимо передавать через каждый слой, в них нам также понадобится propagate():

impl Layer {
    fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        todo!()
    }
}

Имея Layer::propagate(), мы можем вернуться и реализовать Network::propagate():

impl Network {
    pub fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        let mut inputs = inputs;

        for layer in &self.layers {
            inputs = layer.propagate(inputs);
        }

        inputs
    }
}

Это вполне удовлетворительный и правильный фрагмент кода, но он не идиоматичен - мы можем сделать его лучше, более rustic!

Прежде всего, это называется перепривязкой (повторной привязкой, rebinding) (или затенением (shadowing)):

let mut inputs = inputs;

...и в этом нет необходимости, потому что мы можем переместить этот mut в параметр функции:

impl Network {
    pub fn propagate(&self, mut inputs: Vec<f32>) -> Vec<f32> {
        for layer in &self.layers {
            inputs = layer.propagate(inputs);
        }

        inputs
    }
}

Но не обяжет ли это вызывающую сторону передавать изменяемые (мутабельные) значения? Неа!

fn process(mut items: Vec<f32>) {
    // ...
}

fn main() {
    let items = vec![1.2, 3.4, 5.6];
    // ^ `mut` здесь не нужен

    process(items);
    //      ^ просто работает
}

Только что введенный нами mut находится в так называемой позиции привязки (binding position):

// иммут. - иммутабельный, мут. - мутабельный
fn foo_1(items: &[f32]) {
    //   ^^^^^  ------
    //  привязка  тип
    //  (иммут.) (иммут.)
}

fn foo_2(mut items: &[f32]) {
    //   ^^^^^^^^^  ------
    //    привязка   тип
    //     (мут.)  (иммут.)
}

fn foo_3(items: &mut [f32]) {
    //   ^^^^^  ----------
    //  привязка   тип
    //  (иммут.)  (мут.)
}

fn foo_4(mut items: &mut [f32]) {
    //   ^^^^^^^^^  ----------
    //    привязка    тип
    //     (мут.)    (мут.)
}

struct Person {
    name: String,
    eyeball_radius: usize,
}

fn decompose(Person { name, mut eyeball_radius }: Person) {
    //       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  ------
    //                     привязка                тип
    //         (частично иммут., частично мут.)  (иммут.)
}

...и привязки, в отличие от типов, являются локальными для функции:

fn foo(items: &mut Vec<usize>) {
    // Когда тип является мутабельным, мы можем модифицировать то,
    // на что указывает ссылка:
    items.push(1234);

    // Но если привязка остается иммутабельной, мы НЕ можем модифицировать
    // саму ссылку:
    items = some_another_vector;
    //    ^ error: cannot assign to immutable argument
}

fn bar(mut items: &Vec<usize>) {
    // С другой стороны, когда привязка является мутабельной, мы можем модифицировать
    // саму ссылку:
    items = some_another_vector;

    // Но если тип остается иммутабельным, мы не можем модифицировать то,
    // на что указывает ссылка:
    items.push(1234);
    //   ^^^^^ error: cannot borrow `*items` as mutable, as it is
    //         behind a `&` reference
}

Есть еще одна вещь, которую мы можем применить к нашему коду - этот шаблон известен как свертывание (folding):

for layer in &self.layers {
    inputs = layer.propagate(inputs);
}

...и стандартная библиотека Rust предоставляет для этого специальную функцию:

impl Network {
    pub fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        self.layers
            .iter()
            .fold(inputs, |inputs, layer| layer.propagate(inputs))
    }
}

На вкус и цвет, как известно, товарища нет.

Вуаля - в конце концов, благодаря замыканию нам даже не нужен mut inputs - теперь наш код полностью соответствует Haskell (т.е. является функциональным по духу).

Перейдем к нейронам - один нейрон принимает много входных данных и возвращает одно выходное значение, поэтому:

#[derive(Debug)]
struct Neuron {
    bias: f32,
    weights: Vec<f32>,
}

impl Neuron {
    fn propagate(&self, inputs: Vec<f32>) -> f32 {
        todo!()
    }
}

Возвращаемся к реализации Layer::propagate():

#[derive(Debug)]
struct Layer {
    neurons: Vec<Neuron>,
}

impl Layer {
    fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        let mut outputs = Vec::new();

        for neuron in &self.neurons {
            let output = neuron.propagate(inputs);
            outputs.push(output);
        }

        outputs
    }
}

Если мы попытаемся скомпилировать этот код, то получим первый сбой проверки заимствований:

error[E0382]: use of moved value: `inputs`
  --> src/lib.rs
   |
   |     fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
   |                         ------ move occurs because `inputs` has
   |                                type `Vec<f32>`, which does not
   |                                implement the `Copy` trait
  ...
   |             let output = neuron.propagate(inputs);
   |                                           ^^^^^^
   |                                value moved here, in previous
   |                                iteration of loop

Очевидно, что компилятор прав: после вызова neuron.propagate(inputs) мы теряем владение над inputs, поэтому не можем использовать их в последующих итерациях цикла.

К счастью, исправить это легко - достаточно сделать так, чтобы neuron::propagate() работал с заимствованными значениями:

impl Layer {
    fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        /* ... */

        for neuron in &self.neurons {
            let output = neuron.propagate(&inputs);
            /* ... */
        }

        /* ... */
    }
}

/* ... */

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */
    }
}

Вот как выглядит наш код на данный момент:

impl Layer {
    fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        let mut outputs = Vec::new();

        for neuron in &self.neurons {
            let output = neuron.propagate(&inputs);
            outputs.push(output);
        }

        outputs
    }
}

...и, верите или нет, этот шаблон называется отображением (mapping), и стандартная библиотека также предоставляет для него специальный метод!

impl Layer {
    fn propagate(&self, inputs: Vec<f32>) -> Vec<f32> {
        self.neurons
            .iter()
            .map(|neuron| neuron.propagate(&inputs))
            .collect()
    }
}

Остается завершить neuron::propagate() - как и прежде, начнем с сырой версии:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        let mut output = 0.0;

        for i in 0..inputs.len() {
            output += inputs[i] * self.weights[i];
        }

        output += self.bias;

        if output > 0.0 {
            output
        } else {
            0.0
        }
    }
}

Этот фрагмент содержит две неидиоматичные конструкции и одну потенциальную ошибку - начнем с последней.

Поскольку мы перебираем self.weights, используя длину inputs, у нас есть три крайних случая:

1. Когда inputs.len() < self.weights.len().
2. Когда inputs.len() == self.weights.len().
3. Когда inputs.len() > self.weights.len().

Наш код основан на предположении, что пункт 2 всегда верен, но это предположение: мы нигде его не проверяем! Если мы по ошибке передадим меньше или больше входных данных, то получим либо неверный результат, либо сбой.

Существует как минимум два способа решить эту проблему:

1. Мы можем изменить Neuron::propagate() для возврата сообщения об ошибке:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> Result<f32, String> {
        if inputs.len() != self.weights.len() {
            return Err(format!(
                "получено {} входных данных, ожидалось {}",
                inputs.len(),
                self.weights.len(),
            ));
        }

        /* ... */
    }
}

...или с помощью одного из моих любимых крейтов - thiserror:

pub type Result<T> = std::result::Result<T, Error>;

#[derive(Debug, Error)]
pub enum Error {
    #[error("получено {got} входных данных, ожидалось {expected}")]
    MismatchedInputSize {
        got: usize,
        expected: usize,
    },
}

/* ... */

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> Result<f32> {
        if inputs.len() != self.weights.len() {
            return Err(Error::MismatchedInputSize {
                got: inputs.len(),
                expected: self.weights.len(),
            });
        }

        /* ... */
    }
}

2. Мы можем использовать assert_eq!() / panic!():

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        assert_eq!(inputs.len(), self.weights.len());

        /* ... */
    }
}

В большинстве случаев первый вариант лучше, поскольку он позволяет вызывающей стороне поймать ошибку и легко ее обработать. Однако в нашем случае игра не стоит свеч, поскольку:

1. Если assert_eq() не сработает, значит, наша реализация, скорее всего, неверна, и пользователи ничего не смогут сделать со своей стороны, чтобы решить проблему.
2. Это игрушечный проект - не будем зря тратить время.

Поэтому:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        assert_eq!(inputs.len(), self.weights.len());

        /* ... */
    }
}

Что касается идиом, это:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */

        if output > 0.0 {
            output
        } else {
            0.0
        }
    }
}

...является скрытым f32::max():

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */

        output.max(0.0)
    }
}

А это:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */

        let mut output = 0.0;

        for i in 0..inputs.len() {
            output += inputs[i] * self.weights[i];
        }

        /* ... */
    }
}

...можно упростить сначала с помощью .zip():

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */

        let mut output = 0.0;

        for (&input, &weight) in inputs.iter().zip(&self.weights) {
            output += input * weight;
        }

        /* ... */
    }
}

Операции индексации массива, такие как inputs[i], всегда выполняют так называемую проверку границ (bounds check) - это фрагмент кода, который гарантирует, что индекс находится в пределах массива, и паникует, когда он слишком велик:

fn main() {
    let numbers = vec![1];
    println!("{}", numbers[123]);
}

thread 'main' panicked at 'index out of bounds: the len is 1 but
the index is 123'

Когда вместо индексации мы используем комбинаторы, такие как .zip() или .map(), мы позволяем компилятору опустить эти проверки, что делает наш код не только более читаемым (на вкус и цвет...), но и более быстрым.

...затем с помощью .map() и .sum():

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        /* ... */

        let mut output = inputs
            .iter()
            .zip(&self.weights)
            .map(|(input, weight)| input * weight)
            .sum::<f32>();

        /* ... */
    }
}

Синтаксис ::<>, используемый на последней строке, называется турборыбой (turbofish). Он позволяет предоставлять явные общие (generic) аргументы, когда у компилятора возникают проблемы с их выводом.

Вуаля:

impl Neuron {
    fn propagate(&self, inputs: &[f32]) -> f32 {
        assert_eq!(inputs.len(), self.weights.len());

        let output = inputs
            .iter()
            .zip(&self.weights)
            .map(|(input, weight)| input * weight)
            .sum::<f32>();

        (self.bias + output).max(0.0)
    }
}

Это, несомненно, красиво, но работает ли это? Может ли наш код распознать кошку на изображении? Можем ли мы использовать его для прогнозирования будущих цен Dogecoin?

Разработка new()

До сих пор мы были настолько сосредоточены на алгоритме, что практически не думали о конструкторах, но как можно использовать сеть, которую невозможно создать?

Мы могли бы сделать так:

#[derive(Debug)]
pub struct Network {
    layers: Vec<Layer>,
}

impl Network {
    pub fn new(layers: Vec<Layer>) -> Self {
        Self { layers }
    }

    /* ... */
}

...но не будем, поскольку хотим оставить Layer и Neuron вне общедоступного интерфейса.

В прошлой статье мы много говорили о произвольных числах, поэтому я уверен, что рано или поздно нам понадобится что-то вроде этого:

impl Network {
    pub fn random() -> Self {
        todo!()
    }
}

Чтобы рандомизировать сеть, нам нужно знать количество ее слоев и количество нейронов в каждом слое - их можно описать одним вектором:

impl Network {
    pub fn random(neurons_per_layer: Vec<usize>) -> Self {
        todo!()
    }
}

...или более элегантным способом:

#[derive(Debug)]
pub struct LayerTopology {
    pub neurons: usize,
}

impl Network {
    pub fn random(layers: Vec<LayerTopology>) -> Self {
        todo!()
    }

    /* ... */
}

// Заметьте, как создание отдельного типа позволило нам переименовать аргумент просто в `layers`.
//
// Изначально аргумент назывался `neurons_per_layer`, поскольку `Vec<usize>`
// не предоставлял достаточно информации о том, что представляет собой этот `usize`.
// Использование отдельного типа делает это очевидным.

Теперь, если внимательно посмотреть на слой нейронной сети:

...можно заметить, что на самом деле он определяется двумя числами: размерами входных и выходных данных. Означает ли это, что наша структура LayerTopology с одним полем неверна? Наоборот!

Мы использовали знания в предметной области.

В FFNN все слои соединены последовательно слева направо:

Поскольку выходные данные слоя A являются входными данными слоя B, если мы сделаем так:

#[derive(Debug)]
pub struct LayerTopology {
    pub input_neurons: usize,
    pub output_neurons: usize,
}

...тогда мы не только сделаем наш интерфейс громоздким, но, что еще хуже, нам потребуется дополнительная проверка, гарантирующая, что соблюдаются условия layer[0].output_neurons == layer[1].input_neurons и т.д. - полная бессмыслица!

Принимая во внимание тот простой факт, что последовательные слои должны иметь совпадающие входы и выходы, мы можем упростить код еще до его написания.

Наивная реализация выглядит так:

impl Network {
    pub fn random(layers: Vec<LayerTopology>) -> Self {
        let mut built_layers = Vec::new();

        for i in 0..(layers.len() - 1) {
            let input_size = layers[i].neurons;
            let output_size = layers[i + 1].neurons;

            built_layers.push(Layer::random(
                input_size,
                output_size,
            ));
        }

        Self { layers: built_layers }
    }
}

...давайте ее "растифицируем" - угадайте, что произойдет, если мы вызовем Network::random(vec![])?

impl Network {
    pub fn random(layers: Vec<LayerTopology>) -> Self {
        // Сеть с одним слоем технически возможна, но бессмысленна:
        assert!(layers.len() > 1);

        /* ... */
    }
}

Так лучше.

Что касается цикла for, то итерация по соседним элементам - это еще один шаблон, предоставляемый стандартной библиотекой через метод windows():

impl Network {
    pub fn random(layers: Vec<LayerTopology>) -> Self {
        /* ... */

        for adjacent_layers in layers.windows(2) {
            let input_size = adjacent_layers[0].neurons;
            let output_size = adjacent_layers[1].neurons;

            /* ... */
        }

        /* ... */
    }
}

Если вы знаете о деструктуризации, то можете попробовать переписать этот цикл следующим образом:

for [fst, snd] in layers.windows(2) {
    built_layers.push(Layer::random(fst.neurons, snd.neurons));
}

...но, к сожалению, компьютер говорит "Нет":

error[E0005]: refutable pattern in `for` loop binding: `&[]`,
              `&[_]` and `&[_, _, _, ..]` not covered
 --> src/lib.rs
  |
  |     for [fst, snd] in layers.windows(2) {
  |         ^^^^^^^^^^ patterns `&[]`, `&[_]` and `&[_, _, _, ..]`
  |                    not covered
  |
  = note: the matched value is of type `&[LayerTopology]`

Компилятор не понимает, что windows(2) возвращает массив, состоящий ровно из двух элементов, ему известно лишь, что windows() может возвращать массивы произвольных размеров, которые не обязательно соответствуют нашему шаблону (этот шаблон называется опровержимым (refutable), потому что он не совпадает со всеми возможными случаями; трюк с деструктуризацией можно провернуть только с помощью неопровержимого (irrefutable) шаблона).

Ночной Rust, содержащий константные дженерики (const generics) предлагает решение - .array_windows():

#![feature(array_windows)]

for [fst, snd] in layers.array_windows() {
    built_layers.push(Layer::random(fst.neurons, snd.neurons));
}

...однако для простоты мы не будем использовать константные дженерики и продолжим работать со стабильной функцией.

В этом случае переход на итераторы для меня является очевидным:

impl Network {
    pub fn random(layers: Vec<LayerTopology>) -> Self {
        let layers = layers
            .windows(2)
            .map(|layers| Layer::random(layers[0].neurons, layers[1].neurons))
            .collect();

        Self { layers }
    }
}

И последний штрих: если это не делает код неудобным, рекомендуется принимать заимствованные значения вместо собственных:

impl Network {
    pub fn random(layers: &[LayerTopology]) -> Self {
        /* ... */
    }
}

Чаще всего принятие заимствованных значений не сильно меняет логику функции, но делает ее более универсальной - с заимствованным массивом теперь можно делать следующее:

let network = Network::random(&[
    LayerTopology { neurons: 8 },
    LayerTopology { neurons: 15 },
    LayerTopology { neurons: 2 },
]);

...и:

let layers = vec![
    LayerTopology { neurons: 8 },
    LayerTopology { neurons: 15 },
    LayerTopology { neurons: 2 },
];

let network_a = Network::random(&layers);
let network_b = Network::random(&layers);
//                              ^ нет необходимости в `.clone()`

Что дальше, что дальше... проверяем заметки... а, Layer::random()!

impl Layer {
    fn random(input_size: usize, output_size: usize) -> Self {
        let mut neurons = Vec::new();

        for _ in 0..output_size {
            neurons.push(Neuron::random(input_size));
        }

        Self { neurons }
    }

    /* ... */
}

...или:

impl Layer {
    fn random(input_size: usize, output_size: usize) -> Self {
        let neurons = (0..output_size)
            .map(|_| Neuron::random(input_size))
            .collect();

        Self { neurons }
    }
}

|_| называется toilet closure (гардеробным замыканием?) - это функция, принимающая аргумент, который ей не важен/нужен.

Мы могли бы написать:

.map(|output_neuron_id| Neuron::random(input))

...но поскольку нам не нужно читать этот output_neuron_id, более идиоматичным будет назвать аргумент _ (или хотя бы _output_neuron_id) для индикации факта неиспользуемости.

Сам _ называется заменителем (placeholder) и может использоваться в разных контекстах:

// Как привязка:
fn ignore_some_arguments(_: usize, b: usize, _: usize) {
    //                   ^                   ^
}

// ...но не как название:
fn _() {
// ^ error: expected identifier, found reserved identifier `_`
}

// Как тип:
fn load_files(paths: &[&Path]) -> Vec<String> {
    paths
        .iter()
        .map(std::fs::read_to_string)
        .collect::<Result<_, _>>()
    //                    ^  ^
        .unwrap()
}

// ...но только внутри выражений:
fn what_am_i(foo: _) {
    //            ^ error: the type placeholder `_` is not allowed
    //              within types on item signatures
}

Наконец, последний фрагмент нашей цепочки - Neuron::random():

impl Neuron {
    fn random(input_size: usize) -> Self {
        let bias = todo!();

        let weights = (0..input_size)
            .map(|_| todo!())
            .collect();

        Self { bias, weights }
    }

    /* ... */
}

В отличие от C++ или Python, стандартная библиотека Rust не предоставляет генератора псевдослучайных чисел (далее также - ГПСЧ). Что это означает? Это означает, что пришло время для crates.io!

Когда дело доходит до ГПСЧ, rand фактически является стандартом. Это чрезвычайно универсальный крейт, который позволяет генерировать не только псевдослучайные числа, но и другие типы, такие как строки.

Добавляем его в Cargo.toml:

# ...

[dependencies]
rand = "0.8"

...и затем:

use rand::Rng;

/* ... */

impl Neuron {
    fn random(input_size: usize) -> Self {
        let mut rng = rand::thread_rng();
        let bias = rng.gen_range(-1.0..=1.0);

        let weights = (0..input_size)
            .map(|_| rng.gen_range(-1.0..=1.0))
            .collect();

        Self { bias, weights }
    }
}

0..3 - это полуоткрытый интервал, который совпадает с 0, 1 и 2. 0..=3 - это закрытый интервал, который также включает 3.

Конечно, rng.gen_range(-1.0..=1.0) довольно точно предсказывает цены Dogecoin, но существует ли способ убедиться, что наша сеть работает, как ожидается?

Тестирование

Чистая функция - это функция, которая при одних и тех же аргументах всегда возвращает одно и то же значение. Например, это чистая функция:

pub fn add(x: usize, y: usize) -> usize {
    x + y
}

...а это нет:

pub fn read(path: impl AsRef<Path>) -> String {
    std::fs::read_to_string(path).unwrap()
}

add(1, 2) всегда возвращает 3, в то время как read("file.txt") будет возвращать разные строки в зависимости от того, что содержит файл file.txt в данный момент.

Чистые функции хороши тем, что их можно тестировать изолированно:

// Этот тест всегда проходит
// (он является *детерминированным*)
#[test]
fn test_add() {
    assert_eq!(add(1, 2), 3);
}

// Этот тест может пройти, а может провалиться, предугадать невозможно
// (он является *недетерминированным*)
#[test]
fn test_read() {
    assert_eq!(
        std::fs::read_to_string("serials-to-watch.txt"),
        "killing eve",
    );
}

К сожалению, генерация чисел в Neuron::random() делает эту функцию нечистой, что легко доказать:

#[test]
fn random_is_pure() {
    let neuron_a = Neuron::random(4);
    let neuron_b = Neuron::random(4);

    // Если бы `Neuron::random()` была чистой, оба нейрона всегда были бы одинаковыми:
    assert_eq!(neuron_a, neuron_b);
}

Тестировать нечистые функции сложно, потому что мы мало что можем утверждать достоверно:

/* ... */

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn random() {
        let neuron = Neuron::random(4);

        assert!(/* что? */);
    }
}

Мы можем попробовать:

#[test]
fn test() {
    let neuron = Neuron::random(4);

    assert_eq!(neuron.weights.len(), 4);
}

...но это бесполезный тест, он ничего не доказывает.

С другой стороны, превращать Neuron::random() в чистую функцию кажется... нелепым? Какой смысл в рандомизации, если результат всегда будет одинаковым?

Обычно я примиряю оба мира, рассматривая источник нечистоты. В данном случае это:

impl Neuron {
    fn random(input_size: usize) -> Self {
        let mut rng = rand::thread_rng(); // упс

        /* ... */
    }
}

Что если вместо вызова thread_rng(), мы будем принимать параметр с рандомизатором?

use rand::{Rng, RngCore};

/* ... */

impl Network {
    pub fn random(rng: &mut dyn RngCore, layers: &[LayerTopology]) -> Self {
        let layers = layers
            .windows(2)
            .map(|layers| Layer::random(rng, layers[0].neurons, layers[1].neurons))
            .collect();

        /* ... */
    }

    /* ... */
}

/* ... */

impl Layer {
    fn random(rng: &mut dyn RngCore, input_size: usize, output_size: usize) -> Self {
        let neurons = (0..output_size)
            .map(|_| Neuron::random(rng, input_size))
            .collect();

        /* ... */
    }

    /* ... */
}

/* ... */

impl Neuron {
    fn random(rng: &mut dyn RngCore, input_size: usize) -> Self {
        /* ... */
    }

    /* ... */
}

...тогда мы сможем использовать в наших тестах фиктивный, предсказуемый ГПСЧ, в то время как пользователи смогут передавать настоящий ГПСЧ по своему выбору.

Вы можете использовать аналогичный подход для проверки вывода приложения, если вместо:

fn do_something() {
    println!("Делаем что-нибудь...");
    println!("...сделано!");
}

...мы сделаем:

fn do_something(stdout: &mut dyn Write) {
    writeln!(stdout, "Делаем что-нибудь...").unwrap();
    writeln!(stdout, "...сделано!").unwrap();
}

...тогда мы сможем легко тестировать вывод:

#[test]
fn ensure_something_happens() {
    let mut stdout = String::new();
    do_something(&mut stdout);

    assert_eq!(stdout, "Делаем что-нибудь...\n...сделано!\n");
}

Я делал это раньше, и это оказалось очень удобным.

Технически ни do_something(), ни random() не являются чистыми функциями, поскольку им не хватает свойства, называемого ссылочной прозрачностью (referential transparency) - хотя всегда есть:

fn do_something<W: Write>(stdout: W) -> W {
    /* ... */
}

Поскольку крейт rand не предоставляет предсказуемого (фиктивного) ГПСЧ, нам придется использовать другой крейт — мне нравится rand_chacha (легко запомнить, вероятно, вы уже запомнили):

# ...

[dependencies]
rand = "0.8"

[dev-dependencies]
rand_chacha = "0.3"

...что позволяет нам сделать следующее:

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;

    #[test]
    fn random() {
        // Поскольку мы всегда используем одинаковый заполнитель (seed), наш `rng`
        // будет всегда возвращать одинаковый набор значений
        let mut rng = ChaCha8Rng::from_seed(Default::default());
        let neuron = Neuron::random(&mut rng, 4);

        assert_eq!(neuron.bias, /* ... */);
        assert_eq!(neuron.weights, &[/* ... */]);
    }
}

Мы пока не знаем, какие числа будут возвращены, но это легко выяснить - мы просто начнем с нулей, а затем скопируем и вставим числа из результатов теста:

#[test]
fn random() {
    /* ... */

    assert_eq!(neuron.bias, 0.0);
    assert_eq!(neuron.weights, &[0.0, 0.0, 0.0, 0.0]);
}

Первый cargo test дает нам:

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `-0.6255188`,
 right: `0.0`

...поэтому:

#[test]
fn random() {
    /* ... */

    assert_eq!(neuron.bias, -0.6255188);

    /* ... */
}

Второй cargo test дает:

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `[0.67383957, 0.8181262, 0.26284897, 0.5238807]`,
 right: `[0.0, 0.0, 0.0, 0.0]`', src/lib.rs:29:5

...поэтому:

#[test]
fn random() {
    /* ... */

    assert_eq!(
        neuron.weights,
        &[0.67383957, 0.8181262, 0.26284897, 0.5238807]
    );
}

Обратите внимание, что числа разные, и это нормально - они могут быть разными, пока каждый cargo test работает с одним и тем же набором чисел (и это так, потому что мы использовали ГПСЧ с постоянным заполнителем).

Прежде чем двигаться дальше, нам нужно затронуть еще одну тему: неточность чисел с плавающей точкой (запятой).

Тип, который мы используем, f32, представляет собой 32-битное число с плавающей точкой, которое может представлять значения от ~1,2*10^-38 до ~3,4*10^38. Увы, он может представлять не все эти числа, а только некоторые.

Например, с помощью f32 мы не можем закодировать ровно 0.15:

fn main() {
    println!("{:.10}", 0.15f32);
    // 0.1500000060
}

...или 0.45:

fn main() {
   println!("{:.10}", 0.45f32);
   // 0.4499999881
}

Обычно это не имеет значения, потому что числа с плавающей точкой проектировались не для точности, а только для скорости, но иногда это похоже на кирпич, падающий с неба:

#[test]
fn test() {
    assert_eq!(0.45f32, 0.15 + 0.15 + 0.15);
}

thread 'test' panicked at 'assertion failed: `(left == right)`
  left: `0.45`,
 right: `0.45000002`'

Если вы не читали о числах с плавающей точкой, советую взглянуть на эту статью.

Итак, если мы не можем сравнивать числа точно, то как их сравнивать? Приблизительно!

#[test]
fn test() {
    let actual: f32 = 0.1 + 0.2;
    let expected = 0.3;

    assert!((actual - expected).abs() < f32::EPSILON);
}

Это стандартный способ сравнения чисел с плавающей точкой во всех языках программирования, реализующих IEEE 754 (по сути, во всех языках программирования) - вместо того, чтобы искать точный результат, мы сравниваем оба числа с отступом погрешности (margin of error) (также называемым допуском (tolerance)).

Поскольку сравнивать числа таким способом неудобно, это можно делать с помощью макроса:

macro_rules! assert_almost_eq {
    ($left:expr, $right:expr) => {
        let left: f32 = $left;
        let right: f32 = $right;

        assert!((left - right).abs() < f32::EPSILON);
    }
}

#[test]
fn test() {
    assert_almost_eq!(0.45f32, 0.15 + 0.15 + 0.15);
}

...или с помощью крейта, такого как approx:

#[test]
fn test() {
    approx::assert_relative_eq!(0.45f32, 0.15 + 0.15 + 0.15);
}

Мне нравится approx, добавляем его в Cargo.toml:

# ...

[dev-dependencies]
approx = "0.4"
rand_chacha = "0.3"

...и обновляем тесты:

use super::*;
use approx::assert_relative_eq;
use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;

#[test]
fn random() {
    let mut rng = ChaCha8Rng::from_seed(Default::default());
    let neuron = Neuron::random(&mut rng, 4);

    assert_relative_eq!(neuron.bias, -0.6255188);

    assert_relative_eq!(
        neuron.weights.as_slice(),
        [0.67383957, 0.8181262, 0.26284897, 0.5238807].as_ref()
    );
}

После того, что мы узнали, написать тест для Neuron::propagate() не составляет труда:

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn random() {
        /* ... */
    }

    #[test]
    fn propagate() {
        todo!()
    }
}

Вероятно, вы слышали, что тесты следует именовать, исходя из их предварительных условий и ожиданий.

Обычно это так - если бы мы разрабатывали магазин, было бы полезно структурировать тесты следующим образом:

#[cfg(test)]
mod tests {
    use super::*;

    mod cart {
        use super::*;

        mod when_user_adds_a_flower_to_their_cart {
            use super::*;

            #[test]
            fn user_can_see_this_flower_in_their_cart() {
                /* ... */
            }

            #[test]
            fn user_can_remove_this_flower_from_their_cart() {
                /* ... */
            }

            mod and_submits_order {
                /* ... */
            }

            mod and_abandons_cart {
                /* ... */
            }
        }
    }
}

Проблема в том, что наш Neuron не является типичным "бизнес-кодом", и многие "шаблоны бизнес-кода" не работают с математическим кодом. Если нам потребуется учитывать некоторые крайние случаи, скажем:

fn propagate(/* ... */) {
    if /* ... */ {
        do_foo()
    } else {
        do_bar()
    }
}

...тогда имеет смысл создать два отдельных теста:

#[cfg(test)]
mod tests {
    use super::*;

    mod propagate {
        use super::*;

        mod given_neuron_with_foo {
            use super::*;

            #[test]
            fn fooifies_it() {
                /* ... */
            }
        }

        mod given_neuron_thats_bar {
            use super::*;

            #[test]
            fn bars_it() {
                /* ... */
            }
        }
    }
}

...но в нашем случае лучше использовать простые fn random() и fn propagate().

Как убедиться в том, что propagate() работает правильно? Вычислить ожидаемый результат вручную:

#[test]
fn propagate() {
    let neuron = Neuron {
        bias: 0.5,
        weights: vec![-0.3, 0.8],
    };

    // Проверяем работу `.max()` (нашего ReLU):
    assert_relative_eq!(
        neuron.propagate(&[-10.0, -10.0]),
        0.0,
    );

    // `0.5` и `1.0` выбраны произвольно:
    assert_relative_eq!(
        neuron.propagate(&[0.5, 1.0]),
        (-0.3 * 0.5) + (0.8 * 1.0) + 0.5,
    );

    // Мы могли бы сразу написать `1.15`, но полная формула
    // делает наши намерения более ясными
}

Попробуйте самостоятельно реализовать тесты для Layer и Network.

Заключительные мысли

Что именно мы создали?

Может показаться, что реализованное нами не имеет ничего общего с обучением или моделированием:

• Что насчет глаз?
• Где код, отвечающий за движение?
• Как создать этот зеленоватый терминал в стиле Fallout?

...но это только потому, что сама нейронная сеть, хотя и является относительно сложной частью нашей кодовой базы, сама по себе почти ничего не делает - не волнуйтесь, в конце концов, все встанет на свои места.

А пока не стесняйтесь знакомиться с исходным кодом.

Почему наш код такой объемный?

При поиске "нейронная сеть на Python с нуля", мы находим множество статей, в которых FFNN реализуется с помощью нескольких строк кода Python - по сравнению с ними наш код кажется раздутым, почему так?

Потому что это позволяет многому научиться! Мы могли бы закодировать нашу сеть в 1/10 от ее текущего размера, используя nalgebra, мы могли бы использовать один из уже существующих крейтов, но нам важен не только пункт назначения, но и само путешествие.

Что дальше?

На данный момент у нас есть простая FFNN - в следующем разделе мы реализуем генетический алгоритм и подключим его к нашей нейронной сети.

Часть 3

В предыдущей части мы реализовали простую FFNN, которая может передавать числа через рандомизированные слои - это первый шаг на пути создания мозга.

Однако рандомизация - это далеко не все. По большей части эволюция заключается во внесении небольших, постепенных изменений, чтобы система со временем становилась лучше, чтобы наш мозг начал накапливать знания и функционировать так, как ожидается.

Но как мы можем обучить группу чисел с плавающей точкой (запятой, если угодно)?

Проект

Скоро мы узнаем, как работает генетический алгоритм, реализовав его на Rust. Мы подробно рассмотрим, как селекция, скрещивание и мутация вместе позволяют компьютеру находить сложные решения, казалось бы, из воздуха.

Мы постараемся не жестко кодировать конкретный алгоритм выбора или скрещивания, а использовать типажи для создания библиотеки, которую при желании даже можно будет опубликовать на crates.io!

Как и в предыдущей части, сегодня мы рассмотрим различные тонкости синтаксиса Rust, уделяя особое внимание терминологии.

Надеюсь, к концу этой статьи вы сможете сказать: я могу реализовать все это самостоятельно!

Введение

Для начала вспомним, как работает генетический алгоритм, и в чем смысл нашей затеи.

У нас есть объект - нейронная сеть, которая определяется множеством параметров. Их так много, что даже для самых маленьких сетей мы не сможем перебрать все их комбинации за всю нашу жизнь.

Все возможные параметры называются пространством поиска (search space); эрудит сказал бы, что пространство поиска нашей проблемы огромно, и после этого просто убежал бы.

Что мы можем сделать, так это попробовать подражать природе: если мы начнем с группы произвольных неоптимальных решений, мы можем попытаться улучшить их, чтобы со временем получить лучшие решения.

Одним из методов, позволяющих моделировать всю эту эволюционную технику, является генетический алгоритм - он начинается с группы произвольных кандидатов-решений (популяции), которые затем улучшаются с помощью мутаций и скрещиваний, используя функцию приспособленности для оценки найденных решений (особей):

Обзор генетического алгоритма; сверху по часовой стрелке: 1) оцениваем текущие решения с помощью функции приспособленности, 2) выполняем скрещивание и мутацию, 3) повторяем процесс с новой улучшенной популяцией.

Поскольку генетический алгоритм предполагает работу с произвольными числами, он является примером вероятностного метода.

Вероятностные алгоритмы жертвуют точностью ради производительности - они не всегда возвращают лучшие ответы, но обычно дают довольно хорошие результаты и делают это довольно дешево.

Производители овощей не хотят, чтобы вы знали об этом, но существует простая процедура, позволяющая стать морковным магнатом, основанная на генетическом алгоритме:

10  идем в сад
20  сеем несколько произвольных морковок
30  ждем, когда они вырастут
40  берем семена лучших морковок и сеем их
50  возвращаемся к 30

в этом случае:
- популяция = морковки
- особь = морковка
- мутация & скрещивание = происходят автоматически (бесплатный труд!)
- фитнес-функция = ваши глаза & мозг

К этому моменту большинство этих слов должны быть вам знакомы - мы уже рассматривали основы эволюционных вычислений в первой статье. К концу этой статьи вы получите ответы на такие вопросы, как:

• Как мы отбираем особей? Должна существовать тысяча способов делать это! (это правда)
• Как мы представляем их геномы? Должна существовать тысяча способов делать это! (это правда)
• Как реализовать это на Rust? Ты обещал, что код будет работать в браузере! (будет)

Разработка: схема

Начнем с создания второго крейта в нашем рабочем пространстве:

cd shorelark/libs
cargo new genetic-algorithm --name lib-genetic-algorithm --lib

Редактируем lib.rs:

pub struct GeneticAlgorithm;

Наш генетический алгоритм будет предоставлять только одну функцию - иногда ее называют iterate, иногда - step или process. Я решил быть оригинальным:

impl GeneticAlgorithm {
    pub fn evolve(&self) {
        todo!()
    }
}

Что мы эволюционируем? Популяцию, конечно!

impl GeneticAlgorithm {
    pub fn evolve(&self, population: &[???]) -> Vec<???> {
        todo!()
    }
}

Наша реальная проблема будет зависеть от нейронной сети, но поскольку мы хотим, чтобы эта библиотека была универсальной, мы не можем жестко закодировать NeuralNetwork в качестве принимаемого параметра - вместо этого мы можем указать параметр типа:

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
        todo!()
    }
}

I означает особь (individual):

// видимость  дженерики   _ параметры функции
// |          _|     ____|  (или просто "параметры")
// |         |      |
// v-v       v-----vv----------v
   pub fn foo<'a, T>(bar: &'a T) { /* ... */ }
//            ^^  ^  ^--------^
//            |   |  |
//            |   |  параметр функции
//            |   |  (или просто "параметр")
//            |   параметр типа
//            параметр времени жизни

Это читается так:

"Общедоступная функция foo является общей по времени жизни a и типу T, и принимает один параметр bar, который является ссылкой на T".

Это определение функции. В месте вызова функции передаваемые ей значения называются аргументами:

// v-----------------------v место вызова
   foo::<'static, f32>(&1.0);
//       ^-----^  ^-^  ^--^
//       |        |    |
//       |        |    аргумент функции
//       |        |    (или просто "аргумент")
//       |        аргумент типа
//       аргумент времени жизни

Не будем забывать о предварительных условиях:

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
        assert!(!population.is_empty());

        /* ... */
    }
}

Схема алгоритма:

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
        /* ... */

        (0..population.len())
            .map(|_| {
                // TODO отбор
                // TODO скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

Разработка: отбор

На этом этапе внутри цикла нам нужно выбрать двух особей - они станут родителями и "создадут" для нас цифровое потомство.

Выбор особей называется этапом отбора генетического алгоритма и должен удовлетворять следующим двум свойствам:

• каждая особь должна иметь ненулевой шанс быть выбранной
• особи с более высоким показателем приспособленности в среднем должны выбираться чаще, чем особи с более низким показателем приспособленности

Начнем с того, что подумаем, как мы хотим, чтобы пользователи предоставляли свою фитнес-функцию - как бы тривиально это ни звучало, здесь существует как минимум два взаимоисключающих подхода:

1. Фитнес-функция как параметр особи:

impl GeneticAlgorithm {
    pub fn evolve<I>(
        &self,
        population: &[I],
        evaluate_fitness: &dyn Fn(&I) -> f32,
    ) -> Vec<I> {
        /* ... */
    }
}

2. Показатель приспособленности как свойство особи:

pub trait Individual {
    fn fitness(&self) -> f32;
}

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */
    }
}

Первый подход:

• ✅ позволяет предоставить множество различных фитнес-функций для одного типа особей, что может кому-то пригодиться (но не нам)
• ❌ требует указания фитнес-функции для каждого вызова .evolve(), что немного неудобно

Второй подход:

• ✅ позволяет инкапсулировать все индивидуально-ориентированные атрибуты в один типаж, облегчая понимание того, что пользователи должны предоставить
• ❌ указание различных фитнес-функций возможно, но делать это немного сложнее

Моя интуиция голосует 213:7 за использование типажа (он нам в любом случае понадобится, как вы увидите позже).

Что касается метода отбора, мы будем использовать алгоритм, который называется пропорциональным отбором по приспособленности (fitness proportionate selection) (также известный как выбор колеса рулетки (roulette wheel selection)), потому что его легко понять - представим, что у нас есть три особи:

Особь	Показатель приспособленности	Показатель приспособленности в %
A	3	3 / (1 + 2 + 3) = 3 / 6 = 50%
B	2	2 / (1 + 2 + 3) = 2 / 6 = 33%
C	1	1 / (1 + 2 + 3) = 1 / 6 = 16%

Если мы поместим их на колесо рулетки (или, если угодно, на круговую диаграмму), где каждая особь займет часть колеса, равную доле его показателя приспособленности ко всей популяции:

...тогда рандомизация особи будет сводиться к "вращению" колеса с произвольной силой и оценке того, что получилось:

На практике отбор, пропорциональный приспособленности, является, скорее, антипаттерном, потому что позволяет лучшим особям доминировать в симуляции.

Предположим, наш генетический алгоритм находит решение, которое намного лучше остальных:

...в этом случае отбор, пропорциональный приспособленности, с радостью будет выбирать это зеленое решение в 99% случаев, превращая остальных особей в армию скопированных зеленых клонов.

Вы можете задаться вопросом:

"Но разве наша цель состоит не в нахождении лучшего решения?"

Да, но важно помнить, что решения, найденные с помощью генетического алгоритма, всегда являются лучшими на сегодняшний день: если мы отбросим, казалось бы, бесперспективного кандидата слишком рано, то никогда не узнаем, не сделает ли настройка какого-либо параметра его лучше лучшего (простите за тавтологию) решения в долгосрочной перспективе.

Другими словами, чем больше у нас разных особей, тем больше шансов, что одна из них окажется вундеркиндом по игре на тромбоне.

Для простоты мы продолжим использовать выбор колеса рулетки, но отмечу, что выбор ранга (rank selection) - это пример алгоритма, который не демонстрирует доминирующего поведения лучших особей и будет работать с нашими птичками!

Вместо того, чтобы жестко кодировать нашу библиотеку для использования выбора колеса рулетки, создадим типаж. Это позволит пользователям предоставлять любой алгоритм, который им нравится:

pub trait SelectionMethod {
    fn select(&self);
}

Метод отбора должен иметь доступ ко всей популяции:

pub trait SelectionMethod {
    fn select<I>(&self, population: &[I]) -> &I
    where
        I: Individual;
}

...и, для ясности, укажем время жизни:

pub trait SelectionMethod {
    fn select<'a, I>(&self, population: &'a [I]) -> &'a I
    where
        I: Individual;
}

Нам потребуются произвольные числа, так что:

# ...

[dependencies]
rand = "0.8"

[dev-dependencies]
rand_chacha = "0.3"

Каждый крейт в рабочем пространстве имеет собственный набор зависимостей, поэтому rand, указанный в libs/neural-network/Cargo.toml, не доступен другим крейтам рабочего пространства.

Указываем ГПСЧ (генератор псевдослучайных чисел) как параметр:

use rand::RngCore;

/* ... */

pub trait SelectionMethod {
    fn select<'a, I>(&self, rng: &mut dyn RngCore, population: &'a [I]) -> &'a I
    where
        I: Individual;
}

Какая чудесная сигнатура, не правда ли?

Почему бы нам не пойти дальше и не сделать select() универсальным также для ГПСЧ?

pub trait SelectionMethod {
    fn select<'a, R, I>(
       &self,
       rng: &mut R,
       population: &'a [I],
    ) -> &'a I
    where
        R: RngCore,
        I: Individual;
}

Для начала разберемся в терминологии:

1. dyn Trait, &dyn Trait и &mut dyn Trait подразумевают динамическую диспетчеризацию (dynamic dispatch).
2. T, &T и &mut T подразумевают статическую диспетчеризацию (static dispatch).

Диспетчеризация - это способ, которым компилятор отвечает на вопрос "куда именно нам следует перейти?" для универсальных типов:

fn foo() {
   bar();
   // ^ компиляция этого вызова не составляет труда, поскольку мы всегда переходим в `bar`
}

fn bar() {
   println!("yas queen");
}

fn method(obj: &dyn SomeTrait) {
    obj.method();
    // ^ компиляция этого вызова сложнее, поскольку
    //   каждая реализация `SomeTrait` предоставляет
    //   собственную `fn method(&self) { ... }`
}

В качестве примера рассмотрим такой типаж с двумя реализациями:

trait Animal {
    fn kind(&self) -> &'static str;
}

// --

struct Chinchilla;

impl Animal for Chinchilla {
    fn kind(&self) -> &'static str {
        "chinchilla"
    }
}

// --

struct Viscacha;

impl Animal for Viscacha {
    fn kind(&self) -> &'static str {
        "viscacha"
    }
}

Если мы захотим создать функцию, которая печатает вид любого животного, мы можем сделать это двумя способами:

// С помощью статической диспетчеризации (статический полиморфизм):
fn print_kind_static<A>(animal: &A)
where
    A: Animal,
{
    println!("{}", animal.kind());
}

// С помощью динамической диспетчеризации (динамический полиморфизм, полиморфизм времени выполнения):
fn print_kind_dynamic(animal: &dyn Animal) {
    println!("{}", animal.kind());
}

fn main() {
    print_kind_static(&Chinchilla);
    print_kind_static(&Viscacha);

    print_kind_dynamic(&Chinchilla);
    print_kind_dynamic(&Viscacha);
}

На первый взгляд функции выглядят похоже - в чем разница?

print_kind_static() использует технику, называемую мономорфизацией (monomorphization), - для каждого животного, с которым вызывается функция, компилятор прозрачно генерирует специальную "скопированную" версию функции:

fn print_kind_static__chinchilla(animal: &Chinchilla) {
    println!("{}", Chinchilla::kind(animal));
}

fn print_kind_static__viscacha(animal: &Viscacha) {
    println!("{}", Viscacha::kind(animal));
}

fn main() {
    print_kind_static__chinchilla(&Chinchilla);
    print_kind_static__viscacha(&Viscacha);
}

Теперь вы понимаете, почему это называется статической диспетчеризацией - компилятор заменяет динамические типажи статическими типами.

У мономорфизации есть недостаток: она немного медленнее компилируется (компилятору приходится генерировать несколько функций вместо одной), но обычно она приводит к более быстрому и оптимизированному коду во время выполнения - это может иметь существенное значение для приложений, которые вызывают такие общие функции, скажем, миллион раз в секунду.

print_kind_dynamic(), с другой стороны, использует технику под названием vtable (virtual table - виртуальная таблица), когда для каждой реализации создается выделенная таблица сопоставлений с конкретными функциями:

// (это псевдокод для демонстрации концепции)

struct AnimalVtable {
    // Ссылка на определенную функцию `kind()`
    kind: fn(*const ()) -> &'static str,
}

const CHINCHILLA_VTABLE: AnimalVtable = AnimalVtable {
    kind: Chinchilla::kind,
};

const VISCACHA_VTABLE: AnimalVtable = AnimalVtable {
    kind: Viscacha::kind,
};

fn print_kind_dynamic(
    animal_obj: *const (),
    animal_vtable: &AnimalVtable,
) {
    println!("{}", animal_vtable.kind(animal_obj));
}

fn main() {
    print_kind_dynamic(&Chinchilla, &CHINCHILLA_VTABLE);
    print_kind_dynamic(&Viscacha, &VISCACHA_VTABLE);
}

Поскольку все реализации могут быть описаны через AnimalVtable, print_kind_dynamic() не нужно мономорфизировать - в зависимости от базового типа компилятор просто передаст другую виртуальную таблицу.

Недостатком такого подхода является то, что при каждом вызове функции print_kind_dynamic() мы должны проходить через эту дополнительную "прокси таблицу", что теоретически делает ее более медленной, чем print_kind_static(), однако в большинстве случаев разница несущественна.

Возвращаясь к исходному вопросу: почему не сделать where R: RngCore?

Поскольку мы не будем вызывать этот метод миллион раз в секунду, игра не стоит свеч.

Реализация:

pub struct RouletteWheelSelection;

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(&self, rng: &mut dyn RngCore, population: &'a [I]) -> &'a I
    where
        I: Individual,
    {
        todo!()
    }
}

...мы можем сделать это вручную:

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(&self, rng: &mut dyn RngCore, population: &'a [I]) -> &'a I
    where
        I: Individual,
    {
        let total_fitness: f32 = population
            .iter()
            .map(|individual| individual.fitness())
            .sum();

        // Это наивный подход для целей демонстрации - более эффективная
        // реализация будет вызывать `rng` только один раз
        loop {
            let indiv = population
                .choose(rng)
                .expect("получена пустая популяция");

            let indiv_share = indiv.fitness() / total_fitness;

            if rng.gen_bool(indiv_share as f64) {
                return indiv;
            }
        }
    }
}

...но идеальным кодом будет... его отсутствие!

Если полистать документацию rand, можно найти типаж SliceRandom. Если заглянуть в него, можно найти метод choose_weighted, который делает как раз то, что нам нужно:

use rand::seq::SliceRandom;
use rand::{Rng, RngCore};

/* ... */

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(&self, rng: &mut dyn RngCore, population: &'a [I]) -> &'a I
    where
        I: Individual,
    {
        population
            .choose_weighted(rng, |individual| individual.fitness())
            .expect("получена пустая популяция")
    }
}

Помимо доверия разработчикам rand, как мы можем убедиться, что select_weighted() делает то, что нам нужно? Протестировав его!

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn roulette_wheel_selection() {
        todo!();
    }
}

Путь к TDD-нирване (test driven development - разработка через тестирование) усыпан розами, и мы вот-вот вкусим их шипы:

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;

    #[test]
    fn roulette_wheel_selection() {
        let mut rng = ChaCha8Rng::from_seed(Default::default());

        let population = vec![ /* что здесь? */ ];
        let actual = RouletteWheelSelection::new().select(&mut rng, &population);

        assert!(/* что здесь? */);
    }
}

На данный момент у нас есть две проблемы:

1. Поскольку Individual - это типаж, не очень понятно, как сымитировать его для целей тестирования?
2. Поскольку select() возвращает отдельную особь, не очень понятно, как убедиться в ее произвольности?

Начнем с начала: создание фиктивных объектов для целей тестирования называется макетированием (mocking) - и хотя для Rust существуют решения для создания макетов, я никогда не был поклонником этой концепции.

Мое предложение, не требующее каких-либо внешних крейтов, - создать специальную структуру для тестирования:

#[cfg(test)]
mod tests {
    /* ... */

    #[derive(Clone, Debug)]
    struct TestIndividual {
        fitness: f32,
    }

    impl TestIndividual {
        fn new(fitness: f32) -> Self {
            Self { fitness }
        }
    }

    impl Individual for TestIndividual {
        fn fitness(&self) -> f32 {
            self.fitness
        }
    }

    /* ... */
}

...которую мы затем можем использовать следующим образом:

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn roulette_wheel_selection() {
        /* ... */

        let population = vec![
            TestIndividual::new(2.0),
            TestIndividual::new(1.0),
            TestIndividual::new(4.0),
            TestIndividual::new(3.0),
        ];

        /* ... */
    }
}

А что насчет утверждения? Такой тест:

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn roulette_wheel_selection() {
        /* ... */

        let actual = RouletteWheelSelection::new()
            .select(&mut rng, &population);

        assert!(actual, &population[2]);
    }
}

...не внушает доверия, поскольку не доказывает, что показатели приспособленности действительно учитываются. Совершенно некорректная реализация, такая как:

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(/* ... */) -> &'a I
    where
        I: Individual,
    {
        &population[2]
    }
}

...успешно проходит такой тест!

К счастью, выход есть - поскольку мы хотим оценить вероятность, вместо того, чтобы вызывать select() один раз, мы можем сделать это несколько раз и посмотреть на гистограмму:

Ось X представляет элементы, ось Y - частоту.

#[cfg(test)]
mod tests {
    /* ... */
    use std::collections::BTreeMap;
    use std::iter::FromIterator;

    #[test]
    fn roulette_wheel_selection() {
        let mut rng = ChaCha8Rng::from_seed(Default::default());

        let population = vec![
            /* ... */
        ];

        let mut actual_histogram = BTreeMap::new();

        //          /--| Цифра 1000 взята с потолка;
        //          v  | возможно, 50 тоже подойдет
        for _ in 0..1000 {
            let fitness = RouletteWheelSelection
                .select(&mut rng, &population)
                .fitness() as i32;

            *actual_histogram
                .entry(fitness)
                .or_insert(0) += 1;
        }

        let expected_histogram = BTreeMap::from_iter([
            // (приспособленность, сколько раз эта приспособленность была выбрана)
            (1, 0),
            (2, 0),
            (3, 0),
            (4, 0),
        ]);

        assert_eq!(actual_histogram, expected_histogram);
    }
}

Обратите внимание, что при построении гистограммы мы преобразуем показатели приспособленности от f32 до i32:

let fitness = RouletteWheelSelection
    .select(&mut rng, &population)
    .fitness() as i32;

Мы должны это сделать, поскольку числа с плавающей точкой в Rust не реализуют типаж Ord, что делает невозможным их использование в качестве ключей BTreeMap:

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert(1.0, "one point zero");
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
  |
  |     map.insert(1.0, "one point zero");
  |         ^^^^^^ the trait `Ord` is not implemented for `{float}`

Дело в том, что числа с плавающей точкой, как определено стандартом IEEE 754, не являются полностью упорядоченным набором, сравнение NaN проблематично, поскольку:

NaN != NaN

На практике это означает, что если бы мы могли вставить NaN в карту, то не только не могли бы получить его обратно, но это также могло бы сломать внутренние структуры данных BTreeMap, также сделав невозможным получение любого другого элемента. Кстати, это также верно для пользовательских реализаций Ord и PartialOrd - если они не будут удовлетворять асимметрии и транзитивности, вы быстро об этом пожалеете.

cargo test (или cargo test --workspace, если вы находитесь в каталоге виртуального манифеста) возвращает:

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `{1: 98, 2: 202, 3: 278, 4: 422}`,
 right: `{1: 0, 2: 0, 3: 0, 4: 0}`'

...доказывая, что choose_weighted() работает так, как ожидается (более высокие показатели приспособленности выбираются чаще), поэтому скорректируем тест:

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn roulette_wheel_selection() {
        /* ... */

        let expected_histogram = BTreeMap::from_iter(vec![
            // (приспособленность, сколько раз эта приспособленность была выбрана)
            (1, 98),
            (2, 202),
            (3, 278),
            (4, 422),
        ]);

        /* ... */
    }
}

Вуаля - мы проверили непроверяемое! Подготовив отбор, вспомним, на чем мы остановились:

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */

        (0..population.len())
            .map(|_| {
                // TODO отбор
                // TODO скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

Теперь нам нужно выяснить, как передать туда SelectionMethod - я вижу два подхода:

1. С помощью параметра:

impl GeneticAlgorithm {
    pub fn evolve<I, S>(
        &self,
        population: &[I],
        selection_method: &S,
    ) -> Vec<I>
    where
        I: Individual,
        S: SelectionMethod,
    {
        /* ... */
    }
}

2. С помощью конструктора:

pub struct GeneticAlgorithm<S> {
    selection_method: S,
}

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    pub fn new(selection_method: S) -> Self {
        Self { selection_method }
    }

    pub fn evolve<I, S>(&self, population: &[I]) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */
    }
}

Сталкиваясь с такими дилеммами, я задумываюсь о том, как часто пользователям придется менять этот объект.

Популяция обычно меняется при каждом вызове evolve(), поэтому ее удобно принимать через параметр. С другой стороны, алгоритм отбора обычно остается одинаковым для всей симуляции, поэтому пользователям будет удобнее предоставлять его через конструктор.

Теперь мы почти готовы вызвать метод отбора:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(&self, population: &[I]) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */

        (0..population.len())
            .map(|_| {
                let parent_a = self.selection_method.select(rng, population);
                let parent_b = self.selection_method.select(rng, population);

                // TODO скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

...единственное, чего нам не хватает, это ГПСЧ:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(&self, rng: &mut dyn RngCore, population: &[I]) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */
    }
}

Вам может быть интересно, почему мы передаем rng через аргумент, а не через конструктор, ведь генератор произвольных чисел не будет меняться для каждой популяции!

Не все так просто, рассмотрим другие способы написания этого кода:

1. Принимаем собственный ГПСЧ через конструктор:

pub struct GeneticAlgorithm<R> {
    rng: R,
}

impl<R> GeneticAlgorithm<R>
where
    R: RngCore,
{
    pub fn new(rng: R) -> Self {
        Self { rng }
    }
}

2. Принимаем заимствованный ГПСЧ через конструктор:

pub struct GeneticAlgorithm<'r> {
    rng: &'r mut dyn RngCore,
}

impl<'r> GeneticAlgorithm<'r> {
    pub fn new(rng: &'r mut dyn RngCore) -> Self {
        Self { rng }
    }
}

Первый подход я бы предложил в C# или Java, но не в Rust, потому что если мы переместим rng в конструктор, то не сможем использовать его в других местах приложения:

fn main() {
    let rng = /* ... */;
    let ga = GeneticAlgorithm::new(rng);

    // О нет, мы больше не можем использовать этот `rng`!
    if rng.gen_bool() {
        /* ... */
    } else {
        /* ... */
    }
}

Вы можете сказать, что то же самое происходит с SelectionMethod:

fn main() {
    let sp = RouletteWheelSelection::new();
    let ga = GeneticAlgorithm::new(sp);

    // О нет, мы больше не можем использовать этот `sp`!
    if sp.something() {
        /* ... */
    }
}

...но, на мой взгляд, разница в том, что Rng - это более универсальный типаж, который вполне может использоваться вне GeneticAlgorithm, чего нельзя сказать о SelectionMethod.

Что касается варианта &mut dyn RngCore, я считаю его худшим - он требует уникального заимствования (&mut) rng, так что он не только "блокирует" ГПСЧ на время жизни генетического алгоритма:

fn main() {
    let rng = /* ... */;
    let ga = GeneticAlgorithm::new(&mut rng);

    // О нет, мы по-прежнему не можем использовать этот `rng`!
    let population = if rng.gen_bool() {
        /* ... */
    } else {
        /* ... */
    };

    ga.evolve(population);
}

...но также ломает другие допустимые варианты использования, такие как:

struct Simulation {
    rng: ChaCha8Rng,
    ga: GeneticAlgoritm<'whats_this_lifetime??>,
}

impl Simulation {
    pub fn new_chacha() -> Self {
        let rng = ChaCha8Rng::from_seed(Default::default());
        let ga = GeneticAlgorithm::new(&mut rng);

        Self { rng, ga } // упс
    }
}

Разработка: скрещивание

Теперь, когда мы выбрали двух особей-родителей, пришло время для скрещивания.

Скрещивание (также известное как рекомбинация) берет двух особей и смешивает их, создавая новое решение:

По сравнению с простым созданием новых произвольных особей, скрещивание пытается сохранить знания. Идея в том, что скрещивание двух хороших особей обычно приводит к особи, которая является одновременно новой и, по крайней мере, такой же хорошей, как родительские особи. Это позволяет исследовать пространство поиска без риска потерять лучшие найденные на данный момент решения.

Как и в реальном мире, скрещивание на самом деле происходит не у отдельных особей, а скорее в их хромосомах - модное слово, обозначающее "кодирование решения":

Хромосома (также называемая генотипом, хотя я убежден, что биологам не нравится, когда эти понятия смешиваются) обычно состоит из генов, и ее структура зависит от решаемой задачи. Иногда хромосому удобно моделировать как битовый набор:

...иногда удобнее, чтобы хромосома содержала строку:

...или воспользуемся тем, что у нас есть - набором f32, представляющим веса нейронной сети:

#[derive(Clone, Debug)]
pub struct Chromosome {
    genes: Vec<f32>,
}

Вместо того, чтобы делать гены общедоступными (через pub genes​), мы предоставим несколько функций, позволяющих заглянуть внутрь хромосомы - это называется инкапсуляцией:

impl Chromosome {
    pub fn len(&self) -> usize {
        self.genes.len()
    }

    pub fn iter(&self) -> impl Iterator<Item = &f32> {
        self.genes.iter()
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut f32> {
        self.genes.iter_mut()
    }
}

Пользуясь случаем, рассмотрим некоторые интересные типажи стандартной библиотеки:

1. Типаж Index позволяет использовать оператор индексации [] для наших типов:

use std::ops::Index;

/* ... */

// ---
// | Это тип выражения внутри квадратных скобок,
// |
// | например, если мы реализуем `Index<&str>`, то сможем написать:
// |   chromosome["yass"]
// ------- v---v
impl Index<usize> for Chromosome {
    type Output = f32;

    fn index(&self, index: usize) -> &Self::Output {
        &self.genes[index]
    }
}

2. Типаж FromIterator позволяет использовать .collect() в наших типах:

// ---
// | Это тип элемента, который должен предоставить итератор для совместимости
// | с нашей хромосомой
// |
// | (иногда говорят, что это тип, который итератор *возвращает* (yields))
// |
// | Поскольку наша хромосома состоит из чисел с плавающей точкой, здесь
// | мы также ожидаем получить такие числа
// -------------- v-v
impl FromIterator<f32> for Chromosome {
    fn from_iter<T: IntoIterator<Item = f32>>(iter: T) -> Self {
        Self {
            genes: iter.into_iter().collect(),
        }
    }
}

3. Наконец, типаж IntoIterator работает противоположным образом - преобразует тип в итератор:

impl IntoIterator for Chromosome {
    type Item = f32;
    type IntoIter = std::vec::IntoIter<f32>;

    fn into_iter(self) -> Self::IntoIter {
        self.genes.into_iter()
    }
}

Для чего нужен std::vec::IntoIter<f32>?

Итератор - это просто тип, реализующий типаж Iterator:

struct Fibonacci {
    prev: u32,
    curr: u32,
}

impl Default for Fibonacci {
    fn default() -> Self {
        Self { prev: 0, curr: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        let next = self.prev + self.curr;

        self.prev = self.curr;
        self.curr = next;

        Some(self.prev)
    }
}

fn main() {
    for number in Fibonacci::default().take(10) {
        println!("{}", number);
    }
}

Итак, для того, чтобы преобразовать тип в итератор, нужно знать целевой итерируемый тип. В нашем случае, поскольку Chromosome - это всего лишь оболочка для Vec, целевой тип - std::vec::IntoIter, что компилятор даже может нам подсказать:

struct Chromosome {
    genes: Vec<f32>,
}

impl IntoIterator for Chromosome {
    type Item = f32;
    type IntoIter = (); // мы намеренно используем здесь неправильный тип

    fn into_iter(self) -> Self::IntoIter {
        self.genes.into_iter()
    }
}

error[E0308]: mismatched types
   |
   | /* ... */
   |
   = note: expected unit type `()`
                 found struct `std::vec::IntoIter<f32>`

Однако вывести этот тип компилятору не всегда так просто, поскольку в нем учитываются все комбинаторы, такие как .filter() или .map():

struct Somethinger {
    values: Vec<f32>,
}

impl IntoIterator for Somethinger {
    type Item = f32;
    type IntoIter = ();

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .filter(|value| *value > 0.0)
            .map(|value| value * 10.0)
    }
}

error[E0308]: mismatched types
   |
   | /* ... */
   |
   = note: expected unit type `()`
                 found struct `Map<Filter<std::vec::IntoIter<f32>, {closure}>, {closure}>`

Ночной Rust предлагает удобное решение этой проблемы - impl_trait_in_assoc_type:

#![feature(impl_trait_in_assoc_type)]

struct Somethinger {
    values: Vec<f32>,
}

impl IntoIterator for Somethinger {
    type Item = f32;
    type IntoIter = impl Iterator<Item = f32>;

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .filter(|value| *value > 0.0)
            .map(|value| value * 10.0)
    }
}

...что по сути говорит: "Компилятор, выведи тип самостоятельно, пожалуйста".

Поскольку мы используем стабильную цепочку инструментов, мы не можем использовать эту функцию, но, к счастью, нам и не нужно.

Как я сказал несколько минут назад, скрещивание на самом деле происходит не у отдельных особей, а скорее в их хромосомах, что приводит нас к следующему:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(/* ... */) -> Vec<I>
    where
        I: Individual,
    {
        (0..population.len())
            .map(|_| {
                let parent_a = self.selection_method.select(rng, population).chromosome();
                let parent_b = self.selection_method.select(rng, population).chromosome();

                /* ... */
            })
            .collect()
    }
}

/* ... */

pub trait Individual {
    fn fitness(&self) -> f32;
    fn chromosome(&self) -> &Chromosome;
}

/* ... */

#[cfg(test)]
mod tests {
    /* ... */

    impl Individual for TestIndividual {
        fn fitness(&self) -> f32 {
            self.fitness
        }

        fn chromosome(&self) -> &Chromosome {
            panic!("не поддерживается для TestIndividual")
        }
    }

    /* ... */
}

Что касается самого скрещивания, мы могли бы реализовать множество алгоритмов. Обычно лучше попробовать несколько и посмотреть, какой лучше всего подходит для решения конкретной задачи. Однако для простоты мы воспользуемся универсальным скрещиванием (uniform crossover), который можно описать с помощью одного рисунка:

Как и прежде, начнем с типажа:

pub trait CrossoverMethod {
    fn crossover(
        &self,
        rng: &mut dyn RngCore,
        parent_a: &Chromosome,
        parent_b: &Chromosome,
    ) -> Chromosome;
}

...и примитивной реализации:

pub struct UniformCrossover;

impl CrossoverMethod for UniformCrossover {
    fn crossover(
        &self,
        rng: &mut dyn RngCore,
        parent_a: &Chromosome,
        parent_b: &Chromosome,
    ) -> Chromosome {
        let mut child = Vec::new();
        let gene_count = parent_a.len();

        for gene_idx in 0..gene_count {
            let gene = if rng.gen_bool(0.5) {
                parent_a[gene_idx]
            } else {
                parent_b[gene_idx]
            };

            child.push(gene);
        }

        child.into_iter().collect()
    }
}

Ваш внутренний критик, возможно, заметил некоторые недостатки этого кода – и они действительно имеются!

Сначала добавим утверждение:

impl CrossoverMethod for UniformCrossover {
    fn crossover(/* ... */) -> Chromosome {
        assert_eq!(parent_a.len(), parent_b.len());

        /* ... */
    }
}

Во-вторых, воспользуемся комбинатором .zip(), который нам уже встречался в предыдущей статье:

impl CrossoverMethod for UniformCrossover {
    fn crossover(/* ... */) -> Chromosome {
        assert_eq!(parent_a.len(), parent_b.len());

        parent_a
            .iter()
            .zip(parent_b.iter())
            .map(|(&a, &b)| if rng.gen_bool(0.5) { a } else { b })
            .collect()
    }
}

Как аккуратно!

Обратите внимание, как, реализова