Выбросьте кодовую таблицу! «Взлом» азбуки Морзе с помощью RNN

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

AI Frontline: азбука Морзе — это сигнальный код, который включается и выключается, выражая различные английские буквы, цифры и знаки препинания в различных сочетаниях. Он был изобретен в 1837 году. Азбука Морзе является ранней формой цифровой связи, но она отличается от современных двоичных кодов, которые используют только состояния 0 и 1. Он имеет пять кодов: точки, тире, паузы между точками и тире, каждое слово Умеренные паузы между и длинные паузы между предложения.

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

В качестве альтернативы мы можем построить модель кодер-декодер, чтобы угадывать (почти) все слова! Как мазохисты, мы, конечно, выберем последнее. С учетом сказанного давайте сфотографируем боевого коня Дон Кихота, Росинанта, и начнем его путешествие, чтобы сражаться с ветряными мельницами.

Границы AI: Rocinante, испанский, редкий [транслитерация], имя лошади, на которой едет Дон Кихот в Дон Кихоте.

Вот проблема под рукой:У нас есть несколько кодирующих последовательностей и соответствующие понятные примеры. Используя эти примеры, мы должны изучить некоторые шаблоны и использовать эту информацию, чтобы предсказать, каким может быть новый закодированный токен (слово). В отличие от обычных задач регрессии, где мы предсказываем числовые результаты, у нас есть некоторые проблемы обучения последовательностей с временной структурой данных. Это прямой намек на то, что рекуррентная нейронная сеть (RNN) может быть полезна (это RNN для речи и речевых данных, а также комбинация CNN для данных изображений и RNN для букв изображений). Грубо говоря, это класс задач: сюда входит и машинный перевод, вдохновением здесь служит структура модели. См. [1] для получения дополнительной информации по этой теме. Из-за нехватки места мы не будем вдаваться в теорию RNN, но для краткого введения в эту тему, пожалуйста, обратитесь к серии статей в [2].

Если вам интересно, можно ли решить эту проблему по-другому, ответ: ДА. Метод Монте-Карло с цепями Маркова дает аналогичные результаты. В этом случае мы будем следовать процедуре, упомянутой в первом примере прекрасной статьи [3].

AI Frontline: Основная идея алгоритма Монте-Карло с цепями Маркова (сокращенно MCMC) состоит в том, чтобы найти цепь Маркова в определенном пространстве состояний, чтобы стабильное распределение цепи Маркова было нашим целевым распределением p(x). Таким образом, когда мы совершаем случайное блуждание в этом пространстве состояний, время пребывания каждого состояния x пропорционально целевой вероятности p (x). При выборке с помощью MCMC мы сначала вводим эталонное распределение q(x), которое легко выбрать, получаем выборку-кандидата y из q(x) в процессе каждого шага выборки, а затем решаем, следует ли принять выборку в соответствии с Определения этого принципа состоит в том, чтобы гарантировать, что то, что мы получаем первоначально, точно подчиняется распределению p(x).

Цепь Маркова, названная в честь Андрея Маркова (А.А.Марков, 1856-1922), представляет собой дискретно-событийный случайный процесс с марковскими свойствами в математике. В этом процессе, учитывая текущее знание или информацию, прошлое (т. е. текущее предыдущее историческое состояние) не имеет значения для предсказания будущего (т. е. текущего будущего состояния).

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

Грубо говоря, мы хотим предсказать выходную последовательность (y_1,...,y_m) из входной последовательности (x_1,...,x_n), что включает изучение условной вероятности.

Передовой ИИ: условная вероятность относится к вероятности того, что событие А произойдет, если другое событие Б уже произошло. Условная вероятность выражается как: P (A | B), читается как «вероятность A при условии B». Условные вероятности можно рассчитать с помощью деревьев решений. Ошибка условной вероятности заключается в предположении, что P(A|B) примерно равно P(B|A).

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

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

где h — вектор контекста. Наконец, условная вероятность в правой части приведенного выше уравнения может быть рассчитана с использованием функции softmax, которая принимает в качестве входных данных вектор символов y_{i-1},...,y_1, закодированный горячим способом, в второй RNN Выходной и контекстный вектор рекуррентного слоя. Конкретный тип RNN, используемый здесь, — это LSTM, который эффективно преодолевает ограничения Simple-RNN, который страдает от проблемы градиента и лучше способен фиксировать долгосрочные зависимости.

Frontiers of AI: Simple-RNN — это простейшая рекуррентная нейронная сеть, которая является основой LSTM. Simple-RNN имеет те же уровни прямой и обратной связи, что и BP. Но Simple-RNN вводит рекуррентный механизм, основанный на времени (состоянии).

Мы введем специальный символ (11) для обозначения пробела между кодами каждой буквы. Например, код SOS будет представлен как: ...11---*... (заменяет ...---...). Мы делаем это для того, чтобы слова, соответствующие данному коду, были уникальными. Далее мы будем использовать английские слова из скомпилированного набора данных (words_alpha) вместо случайно сгенерированного набора букв в качестве наших данных. Чтобы получить представление о данных, посмотрите на гистограмму длин слов, показанную ниже. Как видно из гистограммы, слов длиннее 5 букв больше, чем слов короче.

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

Начнем подготовку данных с создания функции, которая кодирует входное английское слово в код Морзе и выводит его.

В целях иллюстрации мы будем генерировать данные обучения и проверки из заданных слов фиксированной длины. Здесь мы зафиксировали эту длину на 9, потому что количество слов длины 9 достаточно велико (см. гистограмму выше). Обратите внимание, что это будет означать, что выходные слова из сети будут иметь фиксированную длину, но входящие коды Морзе не обязательно будут одинаковой длины. Предположим, мы знаем, что максимальная длина каждой буквы равна 4 (на самом деле мы не используем это конкретное предположение, мы можем выбрать самый длинный код Морзе max_length_x для обучения данных.) Поэтому, если длина слова равна n, то соответствующая длина азбуки Морзе не превышает 4n+(n-1), где n-1 соответствует числу 11. Мы дополняем код пробелами слева, чтобы сделать их одинаковой длины, что означает, что наш словарь вводимых символов — {'.', '—', '*', ' '}. В общем, мы позволяем выходному словарю символов быть только буквами и специальными символами для пробелов. Возвращаясь к комментарию о сети, угадывающей длинные слова, мы имеем в виду, что сеть будет склонна угадывать меньше пробелов из-за дисбаланса, создаваемого количеством длинных слов. В приведенном ниже фрагменте кода output_list будет содержать английские слова, а input_list будет содержать заполненные азбуки Морзе.

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

Фронтлайн ИИ: одногорячее кодирование — это однократное кодирование, также известное как однобитовое эффективное кодирование.Метод заключается в использовании N-битных регистров состояния для кодирования N состояний, каждое состояние имеет свой собственный бит регистра, и в любое время, только один из них действителен.

Разделите данные, сгенерируйте обучающий набор x_train, извлеките y_train из одной четверти всего набора данных x, y, оставшиеся три четверти мы сохраним как проверочный набор x_val, y_val. Обратите внимание, что нам было бы лучше оставить часть тренировочного набора для проверки, а остальную часть — для теста, но, учитывая, что мы просто возимся с настройкой, нас больше интересует построение модели, чем настройка параметров. Теперь, когда у нас есть готовые данные для обучения и тестирования (проверки), мы можем приступить к внесению изменений в сеть.

Самый простой способ построить нейронную сеть — использовать модель Keras и последовательный API. Поскольку нам не нужна была вся мощь и гибкость TensorFlow, мы выбрали Keras.

Выбранная нами топология модели сочетает в себе мощный вариант простой RNN, называемый сетью с долговременной кратковременной памятью (LSTM).

Frontiers of AI: Long Short Term Memory Networks — тип временной рекуррентной нейронной сети, подходящей для обработки и прогнозирования важных событий во временных рядах с относительно большими интервалами и задержками. Системы, основанные на сетях долговременной кратковременной памяти, могут выполнять такие задачи, как машинный перевод, анализ видео, обобщение документов, распознавание речи, распознавание изображений, распознавание рукописного ввода, управление чат-ботами и синтезирование музыки.

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

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

Модель построена с использованием Sequential() и добавляет только один слой за раз. Первый слой LSTM принимает трехмерный тензор в качестве входных данных и просит пользователя указать входное измерение. Это можно сделать просто с помощью input_shape, указанного в коде, где первый компонент представляет количество временных шагов, а второй — количество признаков. Для нас количество признаков — это количество элементов словаря входной последовательности, равное 4, так как у нас есть «.», «-», «*» и пробельный символ «». Поскольку за один раз мы предоставляем только один вектор горячего кодирования, количество временных шагов равно max_len_x. Мы также указать количество ячеек памяти (или блоков) в слое (представленный здесь latent_dim параметр, мы используем 256), что размерность скрытого представления. Обратите внимание, что мы хотим, чтобы вернуть окончательное скрытое состояние LSTM как скрытое представление, которое содержит информацию из всех шагов по времени, то есть в полной входной последовательности. Если мы используем return_sequences = True вариант, то мы получим вывод скрытого состояния для каждого шага по времени, но содержит только информацию о последовательности до этого шага.

Это приводит к простой модели кодировщика. Мы построим аналогичный слой в качестве декодера. Но вывод приведенного выше фрагмента кода представляет собой двумерный массив. Мы преобразуем его в 3D-тензор, повторяя выходное число времени max_len_y с помощью удобного слоя RepeatVector и используем его в качестве следующего слоя LSTM (декодера). Теперь мы используем опцию return_sequences = True в этом LSTM для вывода скрытой последовательности состояний, нам нужно использовать эту информацию для прогнозирования. Для этого мы используем плотный слой TimeDistibuted, который выводит вектор длины max_len_y, и мы используем функцию активации softmax для выбора наиболее вероятных букв. Краткий обзор назначения слоя TimeDistributed см. в записи блога Джейсона Браунли: Как использовать слой TimeDistributed для сетей долговременной кратковременной памяти в Python.

https://machinelearningmastery.com/timedistributed-layer-for-long-short-term-memory-networks-in-python/

Ниже приведен краткий обзор сети и различных входных и выходных измерений.

Мы подгоняем модель к данным, обучаем ее на наборе x_train, y_train и используем x_val и y_val, чтобы увидеть, насколько хорошо мы работаем. Последним набором параметров, которые необходимо установить, являются количество эпох и размер пакета. Размер пакета — это размер обучающего набора, который проходит через сеть в алгоритме градиентного спуска, а веса в сети затем обновляются. Обычно размер пакета является максимальным, с которым может справиться память компьютера. Эпоха — это полный сеанс обучения с использованием этих пакетов обучающих данных. Здесь мы установили размер пакета 1024 и использовали эпохи 120. Как вы можете видеть на рисунке ниже, нет значительного увеличения точности после примерно 100 эпох. В общем, нужно пробовать и ошибаться, чтобы увидеть, какой параметр вступает в игру. Теперь мы используем метод fit() для подгонки модели.

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

Введите код слева, соответствующее слово посередине и предсказание справа. Если предсказание верное, слово зеленое, иначе красное.

Как видите, неправильные прогнозы тоже не так уж плохи. Мы должны напомнить себе, что взлом шифра — это не взлом кода, то есть выяснение того, что означает каждая буква. На самом деле мы можем вводить коды букв и видеть предсказанные сетью коды отдельных букв, как показано ниже, мы далеки от цели!

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

AI Frontline: шифрование Цезаря, или шифрование Цезаря, преобразование Цезаря, шифрование с преобразованием, является одним из самых простых и известных методов шифрования. Это метод шифрования с заменой, при котором все буквы в открытом тексте сдвигаются назад (или вперед) на фиксированное число в алфавите, а затем заменяются зашифрованным текстом. Например, при смещении 3 все буквы A будут заменены на D, B на E и так далее. Этот метод шифрования назван в честь Цезаря, который использовал этот метод для связи со своими генералами. Шифр Цезаря часто используется как шаг в других, более сложных методах шифрования. Шифр Цезаря также используется в современных системах ROT13. Но, как и все методы шифрования, использующие для замены алфавиты, шифр Цезаря очень легко взломать, и в практических приложениях нет гарантии безопасности связи.

References:

[1] Sequence to Sequence Learningwith Neural Networks

http://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.pdf

[2] Understanding LSTM Networks

http://colah.github.io/posts/2015-08-Understanding-LSTMs/

[3] THE MARKOV CHAIN MONTE CARLO REVOLUTION

http://www.ams.org/journals/bull/2009-46-02/S0273-0979-08-01238-X/S0273-0979-08-01238-X.pdf