Вдохновлено недавним Hola Javascript Challenge. Упаковывать алгоритм в 64кб не будем, но зато точность получим пристойную.
Подразумевается, что читатель представляет себе в общих чертах принципы работы LSTM. Если нет, то стоит ознакомиться с этим замечательным туториалом.
Задача челленджа — разработать алгоритм, умещающийся со всеми сопутствующими данными в 64кб, способный отличить принадлежащее данному словарю слово от случайно сгенерированных мусорных последовательностей.
Мне показалось, что такие данные — замечательная игровая площадка для равлечений в области deep learning, особенно для изучения рекуррентных нейросетей. Будем относиться к словам как к абстрактным последовательностям символов и попробуем заставить нейросеть извлечь из них какие-то внутренние правила, их определяющие. Мы не будем пытаться сложить нашу модель в 64 килобайта, но зато получим заметно более интересную точность — 0.92+.
Давайте посмотрим на исходные данные чуть подробнее:
Словарь
Пример тесткейса
Переформулируем нашу задачу следующим образом: решаем задачу бинарной классификации последовательностей, причем все последовательности класса true будут входить в тренировочный набор. Да, данные в тестовом наборе могут пересекаться с тренировочными, но только для положительных примеров. Негативные примеры будут уникальными.
Первый этап — обработка данных. С положительными примерами все просто — все «хорошие» слова лежат в словаре. Нужно лишь собрать достаточно много негативных примеров. Для их сборки можно воспользоваться тесткейсами от hola, можно использовать их же генератор (можно найти здесь), ну или написать свой. Я собирал негативные примеры для обучения обращаясь в API.
Прежде чем составлять датасет для обучения, давайте сначала немного изучим словарь хороших примеров и отфильтруем «лишнее». Главное, что нас интересует — максимальная длина последовательности, хочется ее минимизировать (в разумных пределах, конечно).
Построим распределение числа слов по длине:
Да, подавляющее большинство хороших слов короче 21 символа.
Самое длинное слово в датасете шокирует: Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's (попробуйте прочитать вслух с первого раза!). Не думаю, что мы многое потеряем, если откажемся от рассмотрения подобных кадавров. Обрежем хорошие примеры до максимальной длины в 22 символа. Негативные примеры тогда, естественно, тоже будем рассматривать только той же длины.
Хорошие слова — 600+к слов, максимальная длина — 22
Плохие слова — 3+кк уникальных слов, максимальная длина — 22.
Плохих слов собрал с запасом — чуть больше, чем 3 миллиона уникальных последовательностей — это действительно достаточно много.
Далее будет использоваться реализация Bidirectional LSTM на Keras с использованием TensorFlow в качестве бэкенда.
Примерно следующим образом выглядела эволюция архитектуры сетей в процессе экспериментов:
Первая поптыка. Простейшая, базовая LSTM. Входные последовательности вкладываются в тензоры размерности batch_size*MAX_LENGTH*hidden_neurons и пропускаются через ячейки LSTM. Вывод LSTM собирается плотным слоем на 2 выхода, по одному для каждого класса, соответствующим образом рассчитывается итоговый класс. Тренируем на всем словаре хороших слов, и на в два раза большем числе плохих (такая пропорция позволяет выровнять ошибки первого/второго рода).
Такой подход позволяет добиться приблизительно 0.80 точности в каждом из классов. 0.80 — совсем немного, из такой сложной модели нам хотелось бы вытащить больше.
Вторая попытка. Попробуем поднять точность с помощью изменения learning rate в процессе обучения. В keras есть удобный механизм callback-ов, который достаточно неплохо для этого подходит. Будем совершенно топорным образом рубить lr в 10 раз, если на конец эпохи сеть не начнет показывать результаты лучше на валидационном наборе. Возможные реализации подобного метода обсуждаются здесь. Код, предлагаемый пользователем jiumem почти работает. Результаты его минорной модификации для корректной работы с TensorFlow под спойлером:
Использование этого коллбэка с архитектурой, предложенной ранее позволяет поднять точность классификации до 0.83. Не впечатляет.
Третья попытка, финальная Наткнулся на упоминание интересной архитектуры — Bidirectional LSTM. Фактически, обходим последовательность два раза двумя сетями, одна читает справа-налево, другая — наоборот. Подобные конструкции успешно использовались в области speech recognition. Давайте построим сеть того же размера, 500 ячеек, но двунаправленную.
Так же будем использовать lr annealing, на тех же данных.
Этот подход позволил стабильно получать точность 0.91-0.93 на валидационных данных, составленных из случайно выбранных 200к слов, из которых половина — положительные примеры из исходного словаря, а оставшиеся — уникальные, случайно выбранные негативные примеры, не встречавшиеся в тренировочном наборе. Этот результат уже вполне неплох, и стабильно улучшить его, не повышая время обучения мне пока не удалось.
Можно попробовать натравить обученную модель на все собранные данные (да, это не совсем корректно, так как большую часть негативных примеров модель могла увидеть во время обучения). Сделаем это и построим красивую confusion matrix:
Небольшое лирическое отступление: считалось все на GTX960. Последняя сеть начинает сходиться в районе 13 эпохи, одна эпоха считается почти 50 минут.
Получили точность выше 90% за достаточно разумное время. Да, в 64 килобайта такую модель никак не уложить, но, тем не менее, это достаточно интересная демонстрация способности LSTM улавливать внутреннюю структуру в последовательностях, или даже ее отсутствие.
Подразумевается, что читатель представляет себе в общих чертах принципы работы LSTM. Если нет, то стоит ознакомиться с этим замечательным туториалом.
Задача челленджа — разработать алгоритм, умещающийся со всеми сопутствующими данными в 64кб, способный отличить принадлежащее данному словарю слово от случайно сгенерированных мусорных последовательностей.
Мне показалось, что такие данные — замечательная игровая площадка для равлечений в области deep learning, особенно для изучения рекуррентных нейросетей. Будем относиться к словам как к абстрактным последовательностям символов и попробуем заставить нейросеть извлечь из них какие-то внутренние правила, их определяющие. Мы не будем пытаться сложить нашу модель в 64 килобайта, но зато получим заметно более интересную точность — 0.92+.
Давайте посмотрим на исходные данные чуть подробнее:
Словарь
Пример тесткейса
Переформулируем нашу задачу следующим образом: решаем задачу бинарной классификации последовательностей, причем все последовательности класса true будут входить в тренировочный набор. Да, данные в тестовом наборе могут пересекаться с тренировочными, но только для положительных примеров. Негативные примеры будут уникальными.
Обработка данных
Первый этап — обработка данных. С положительными примерами все просто — все «хорошие» слова лежат в словаре. Нужно лишь собрать достаточно много негативных примеров. Для их сборки можно воспользоваться тесткейсами от hola, можно использовать их же генератор (можно найти здесь), ну или написать свой. Я собирал негативные примеры для обучения обращаясь в API.
Прежде чем составлять датасет для обучения, давайте сначала немного изучим словарь хороших примеров и отфильтруем «лишнее». Главное, что нас интересует — максимальная длина последовательности, хочется ее минимизировать (в разумных пределах, конечно).
Построим распределение числа слов по длине:
Да, подавляющее большинство хороших слов короче 21 символа.
Самое длинное слово в датасете шокирует: Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's (попробуйте прочитать вслух с первого раза!). Не думаю, что мы многое потеряем, если откажемся от рассмотрения подобных кадавров. Обрежем хорошие примеры до максимальной длины в 22 символа. Негативные примеры тогда, естественно, тоже будем рассматривать только той же длины.
Отфильтрованные данные
Хорошие слова — 600+к слов, максимальная длина — 22
Плохие слова — 3+кк уникальных слов, максимальная длина — 22.
Плохих слов собрал с запасом — чуть больше, чем 3 миллиона уникальных последовательностей — это действительно достаточно много.
Учим нейросеть
Далее будет использоваться реализация Bidirectional LSTM на Keras с использованием TensorFlow в качестве бэкенда.
Примерно следующим образом выглядела эволюция архитектуры сетей в процессе экспериментов:
Первая поптыка. Простейшая, базовая LSTM. Входные последовательности вкладываются в тензоры размерности batch_size*MAX_LENGTH*hidden_neurons и пропускаются через ячейки LSTM. Вывод LSTM собирается плотным слоем на 2 выхода, по одному для каждого класса, соответствующим образом рассчитывается итоговый класс. Тренируем на всем словаре хороших слов, и на в два раза большем числе плохих (такая пропорция позволяет выровнять ошибки первого/второго рода).
model = Sequential()
model.add(Embedding(len(char_list), 500, input_length=MAX_LENGTH, mask_zero=True))
model.add(LSTM(64, init='glorot_uniform', inner_init='orthogonal',
activation='tanh', inner_activation='hard_sigmoid',
return_sequences=False))
model.add(Dense(len(labels_list)))
model.add(Activation('softmax'))
Такой подход позволяет добиться приблизительно 0.80 точности в каждом из классов. 0.80 — совсем немного, из такой сложной модели нам хотелось бы вытащить больше.
Вторая попытка. Попробуем поднять точность с помощью изменения learning rate в процессе обучения. В keras есть удобный механизм callback-ов, который достаточно неплохо для этого подходит. Будем совершенно топорным образом рубить lr в 10 раз, если на конец эпохи сеть не начнет показывать результаты лучше на валидационном наборе. Возможные реализации подобного метода обсуждаются здесь. Код, предлагаемый пользователем jiumem почти работает. Результаты его минорной модификации для корректной работы с TensorFlow под спойлером:
LR Annealing Callback for Keras+TF
class LrReducer(Callback):
def __init__(self, patience=0, reduce_rate=0.1, reduce_nb=5, verbose=1):
super(Callback, self).__init__()
self.patience = patience
self.wait = 0
self.best_score = float("inf")
self.reduce_rate = reduce_rate
self.current_reduce_nb = 0
self.reduce_nb = reduce_nb
self.verbose = verbose
def on_epoch_end(self, epoch, logs={}):
current_score = logs['val_loss']
print("cur score:", current_score, "current best:", self.best_score)
if current_score <= self.best_score:
self.best_score = current_score
self.wait = 0
self.current_reduce_nb = 0
if self.verbose > 0:
print('---current best val accuracy: %.3f' % current_score)
else:
if self.wait >= self.patience:
self.current_reduce_nb += 1
if self.current_reduce_nb <= self.reduce_nb:
lr = self.model.optimizer.lr.initialized_value()
self.model.optimizer.lr.assign(lr*self.reduce_rate)
else:
if self.verbose > 0:
print("Epoch %d: early stopping" % (epoch))
self.model.stop_training = True
self.wait += 1
Использование этого коллбэка с архитектурой, предложенной ранее позволяет поднять точность классификации до 0.83. Не впечатляет.
Третья попытка, финальная Наткнулся на упоминание интересной архитектуры — Bidirectional LSTM. Фактически, обходим последовательность два раза двумя сетями, одна читает справа-налево, другая — наоборот. Подобные конструкции успешно использовались в области speech recognition. Давайте построим сеть того же размера, 500 ячеек, но двунаправленную.
Bidirectional LSTM in Keras
hidden_units = 500
left = Sequential()
left.add(Embedding(len(char_list), hidden_units, input_length=MAX_LENGTH, mask_zero=True))
left.add(LSTM(output_dim=hidden_units, init='uniform', inner_init='uniform',
forget_bias_init='one', return_sequences=False, activation='tanh',
inner_activation='sigmoid'))
right = Sequential()
right.add(Embedding(len(char_list), hidden_units, input_length=MAX_LENGTH, mask_zero=True))
right.add(LSTM(output_dim=hidden_units, init='uniform', inner_init='uniform',
forget_bias_init='one', return_sequences=False, activation='tanh',
inner_activation='sigmoid', go_backwards=True))
model = Sequential()
model.add(Merge([left, right], mode='sum'))
model.add(Dense(len(labels_list)))
model.add(Activation('softmax'))
Так же будем использовать lr annealing, на тех же данных.
Этот подход позволил стабильно получать точность 0.91-0.93 на валидационных данных, составленных из случайно выбранных 200к слов, из которых половина — положительные примеры из исходного словаря, а оставшиеся — уникальные, случайно выбранные негативные примеры, не встречавшиеся в тренировочном наборе. Этот результат уже вполне неплох, и стабильно улучшить его, не повышая время обучения мне пока не удалось.
Можно попробовать натравить обученную модель на все собранные данные (да, это не совсем корректно, так как большую часть негативных примеров модель могла увидеть во время обучения). Сделаем это и построим красивую confusion matrix:
Время обучения
Небольшое лирическое отступление: считалось все на GTX960. Последняя сеть начинает сходиться в районе 13 эпохи, одна эпоха считается почти 50 минут.
Заключение
Получили точность выше 90% за достаточно разумное время. Да, в 64 килобайта такую модель никак не уложить, но, тем не менее, это достаточно интересная демонстрация способности LSTM улавливать внутреннюю структуру в последовательностях, или даже ее отсутствие.