Победите Убийцу Зодиака с помощью машинного обучения (пытаясь…)

Предыстория:

Zodiac Killer — это прозвище серийного убийцы из района залива Сан-Франциско, действовавшего в конце 90-х. Местная пресса получила четыре различных загадочных сообщения, отправленных непосредственно с Зодиака, предположительно содержащих информацию, которая может привести к раскрытию его истинной личности, а также к планам будущих атак. Каждое зашифрованное сообщение состоит из ряда символов зашифрованного текста, как показано ниже. В 1969 году шифротекст Зодиака 408 был успешно расшифрован школьным учителем с помощью гомофонического шифра замены. Это метод шифрования, при котором один и тот же символ открытого текста может представлять более одного символа зашифрованного текста. Например, символы «ϕ» и «‹» могут переводиться как буква «а». Несмотря на взлом шифра 408, осталось разгадать еще три зодиакальных шифра. Опечатки и случайные слова усложняют нашу работу, но, используя информацию из шифра 408, у нас могут появиться некоторые идеи.

Идея:

Недавняя попытка разгадать шифр 340 предложила использовать обратный омофонический шифр. Обратный гомофонный шифр имеет дополнительное свойство, состоящее в том, что символ зашифрованного текста может представлять один или несколько символов открытого текста. На практике это означает, что оба символа 'ϕ' и '‹' могут переводиться как 'a' и/или 'f '. Это создает дополнительную проблему при расшифровке, поскольку нахождение одного возможного представления символа зашифрованного текста в открытом тексте не гарантирует, что тот же самый английский символ открытого текста будет правильным для следующего появления этого символа зашифрованного текста. Теперь наша задача состоит в том, чтобы найти обратное гомофонное отображение зашифрованного текста, которое даст нам решение шифра 340.

Формализовать проблему:

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

Следующая таблица представляет собой способ представления зашифрованного текста Zodiac 340. Для каждого из индексов (i) зашифрованного текста перечисленные совпадения представляют предыдущие индексы, которые имеют тот же самый символ зашифрованного текста. Например, символ с индексом i = 102 также встречается с индексами 47 и 22. После того, как мы сгенерировали предполагаемое решение в виде открытого текста, мы можем проверить, совпадают ли индексы с одинаковыми символами зашифрованного текста. В идеале мы хотели бы создать решения, минимизирующие количество используемых обратных омофонов. Возможно, мы можем использовать это как метод подсчета очков. (подробнее об этом позже).

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

Ящик для инструментов:

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

SVM: машина опорных векторов — это модель машинного обучения, хорошо подходящая для нашей задачи НЛП по определению того, является ли фраза «английской» или нет. Чтобы помочь визуализировать, как работает SVM; представьте себе комнату на следующий день после дня рождения. Когда-то в комнате было много летающих шаров разного размера, но теперь некоторые шары упали на землю, а остальным удалось подняться к потолку. Предположим, мы хотим определить, какие воздушные шары плавают, а какие утонули. Если мы посмотрим на комнату сверху вниз, мы увидим множество разных кругов, но не сможем сказать, какие воздушные шары находятся на земле, кроме тех, что на потолке. Если изменить нашу точку зрения, чтобы стоять на земле и смотреть в комнату, мы могли легко увидеть, где находятся воздушные шары. Переключив нашу перспективу с двухмерной на трехмерную, мы можем найти разделение между нашими воздушными шарами и провести классификацию. SVM проецирует вектор признаков в многомерное пространство, а затем находит разделяющую гиперплоскость, которая служит границей решения. В контексте нашей проблемы мы должны обучить SVM на векторах признаков правильного английского языка, а также на тарабарщине.

Чтобы создать вектор признаков положительного класса (оценка: 1), мы будем использовать сегменты длиной 136 символов (без пробелов) из Brown Corpus, набора данных на английском языке. Для нашего отрицательного класса (оценка 2) мы случайным образом перемешаем корпус Брауна на уровне слов, а затем выберем сегменты одинаковой длины.

Нашему SVM нужен способ построения нашего набора данных, чтобы найти деление. Следовательно, функции, которые являются строками, мало полезны для нашей SVM. В результате нам нужно будет выполнить дополнительный шаг обработки данных, прежде чем мы будем готовы ввести данные в нашу модель. Некоторые слова в предложении указывают на больший контекст относительно смысла предложения, чем другие. Кроме того, некоторые слова могут встречаться с высокой частотой, но мало влиять на общий контекст предложения. TfidfVectorizer — это стратегия NLP, которая поможет нам определить значение появления слова в документе. На практике это будет подчеркивать слова вроде «убить» над «то» для нашего Убийцы Зодиака. Мы будем использовать TfidfVectorizer в нашем наборе функций, чтобы помочь нашей SVM контекстуализировать непрерывную строку в отдельные слова с разной релевантностью. Затем мы можем использовать train_test_split от scikit-learn, чтобы разделить наши данные на набор для обучения и набор для тестирования. Давайте проверим результаты:

Результаты нашей первой модели кажутся многообещающими. Мы успешно выполнили наше первое ограничение и создали модель, которая сообщает нам, является ли фраза правильно сформированной или «английской». Напомним, что у нас есть набор данных словаря Zodiac Killer, а также транскрипция одного из его расшифрованных шифров. Мы хотим использовать эти данные для создания новых фраз, которые он мог бы сказать. Затем мы можем оценить возможную фразу, подсчитав количество использованных обратных омонимов (в соответствии с таблицей 1) и повторяя это несколько раз, мы можем приблизиться к действительно жизнеспособному решению! Теперь генерируем предполагаемые сообщения Зодиака.

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

Во фразе, сгенерированной ИНС выше, мы видим, что пары слов кажутся связанными друг с другом. «Как › оно» и « оно достигло» разумны, однако «это › это» не очень похоже на английский язык. Специальный тип сети, называемый рекуррентной нейронной сетью, помогает решить эти проблемы, вводя память. Результаты некоторых узлов возвращаются в сеть на следующем временном шаге в качестве входных данных для других узлов. В случае приведенной выше фразы сеть вряд ли выбрала бы слово «это», чтобы следовать за «это, есть». Специальная RNN, называемая сетью с краткосрочной памятью (LSTM), реализует более длинную память с добавленной способностью случайным образом забывать прошлые вложения.

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

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

Будущая работа:

Хотя нам не удалось успешно взломать шифр Зодиака 340, мы смогли проверить наши возможности машинного обучения на захватывающей проблеме НЛП. В конце концов, наша модель смогла воспроизвести довольно болезненные и творческие фразы, которые вполне мог произнести Зодиакальный Убийца. Одним из основных недостатков нашего подхода является то, что LSTM не может включать оценки из нашего расчета в Таблице 1. Вместо того, чтобы подгонять свои решения для сопоставления индексов, необходимых для зашифрованного текста, единственной основой LSTM является начальное слово. Будущая работа будет включать в себя разработку модели, которая может интегрировать предыдущие оценки результатов.