Вступление
С ростом мощности компьютеров становится возможным создание сложных моделей и их обучение с использованием большого количества данных: вот почему большие данные и машинное обучение так популярны в наши дни.
«Больше данных лучше, чем лучшие алгоритмы», наиболее распространенный способ улучшить модели машинного обучения - увеличить объем данных, чтобы они отражали разнообразие и выбросы, делая их менее предвзятыми.
Среди популярных моделей записи данных просто используются как независимые точки, другими словами, как векторы признаков в многомерном пространстве. Однако во многих случаях не одни только точки, которые могут быть связаны со связями.
Таким образом, можно организовать точки данных в виде графика и использовать информацию, скрытую в их связях, для улучшения алгоритмов машинного обучения. В этой статье на примере показано, как связать текст с изображениями в CAPTCHA, построив графическую модель и запустив ее на больших данных.
Проблема и теория
Текст-изображение CAPTCHA
Практически каждый веб-сайт использует CAPTCHA для предотвращения автоматических атак. CAPTCHA - это своего рода тест, позволяющий отличить машины от людей, который обычно основан на сложных проблемах машинного обучения.
Одним из распространенных типов CAPTCHA является проблема сопоставления текста и изображения. Ниже приведен пример из Google reCAPTCHA:
Веб-сайт Китайской железной дороги также использует такую CAPTCHA, но это еще сложнее:
«Текст» китайский, и это часть изображения!
CAPTCHA просит пользователя выбрать все изображения, относящиеся к данному тексту. С традиционными алгоритмами машинного обучения это сложно из-за отсутствия размеченных данных и большого количества категорий.
Однако с помощью крупномасштабного графа ее можно решить с помощью метода обучения без учителя с точностью более 80% при выборе всех связанных изображений.
Подозрительное совпадение
Прежде чем показывать решение, давайте сначала поговорим об интересной теме. Во многих средних школах Китая щенячья любовь запрещена: однажды пойманные «влюбленные» будут наказаны. Некоторые учителя являются хорошими «детективами» в поиске подпольных отношений, и обычно используется одно правило:
На улице или в школе, если я встречаю одну пару учеников, появляющихся вместе в одиночестве, это подозрительно; и если я увижу это дважды, отношения почти подтверждаются.
Это то, что называется «подозрительным совпадением». По предположению учителя, ученики «независимы», поэтому пары учеников должны появляться случайным образом, как верхние грани двух бросков игральных костей. Чем больше одна пара учеников появляется вместе, тем меньше вероятность того, что они «независимы».
Чтобы справиться с этим правилом, действительно популярно «двойное свидание» (а также «тройное свидание» или «свидание на вечеринке»).
Вернемся к самой CAPTCHA. CAPTCHA можно разделить на две части: текст и изображения. Предлагаемая задача - связать текст и изображения. Текст можно рассматривать как любовника A1, а изображения - как других учеников A2, B, C, D, E… У них разные отношения. Например, текстовое «тигр» и изображения тигра такие же, как любовник A1 и A2, но текстовое «мыло» и изображения тигра совершенно не связаны. Теперь, чтобы машины было сложно решить, текст, целевые изображения и несвязанные изображения смешиваются в одну CAPTCHA, как на «вечеринке».
Давайте подумаем, как генерируется CAPTCHA. Предположим, у нас есть несколько категорий: гусь, пляж, самолет, машина. И каждая категория содержит несколько изображений. Самый простой способ создать CAPTCHA:
- выберите категорию, скажем, пляж
- выберите хотя бы одно изображение из категории пляжей
- случайным образом выбирать изображения из других категорий
- смешайте текст категории и все выбранные изображения в одну CAPTCHA
В качестве примера возьмем CAPTCHA Китайской железной дороги: предположим, что есть 10 категорий по 100 изображений для каждой, всего 1000 изображений. То есть, чтобы выбрать изображения для «пляжа», есть только 100 вариантов для связанного изображения и 900 вариантов для несвязанного изображения.
Подумайте с другой стороны: если есть 1000 CAPTCHA с текстом «пляж», то среди CAPTCHA есть не менее 1000 изображений пляжа, а это означает, что каждое изображение в категории пляж будет появляться в среднем не менее 10 раз. Напротив, изображения, не относящиеся к пляжу, появляются в среднем не более (1000 * 8–1000) / 900 = 7,78 раз. Между этими двумя ожиданиями большой разрыв. На самом деле, поскольку обычно существует несколько правильных вариантов, много категорий и изображений, разрыв еще больше.
Точно так же связанные изображения имеют более высокую вероятность попасть в одну и ту же CAPTCHA, чем несвязанные изображения (подозрительное совпадение). Согласно результатам выборки 2 миллионов CAPTCHA Китайской железной дороги, если два изображения появляются в одной и той же CAPTCHA дважды, у них есть 66% вероятность попасть в одну категорию. А если два изображения появятся вместе 3 раза, вероятность 98%.
Учитывается не только совпадение двух изображений, но и совпадение текста и изображений также о чем-то говорит. На следующем изображении показан пример:
Текст означает «нажмите на гуся всех». Предположим, мы подсчитали, сколько раз на каждом изображении появляется «гусь»:
Очевидно, первое и третье изображения во втором ряду, которые появлялись 10 раз с «гусем», скорее всего, будут ответом.
Теоретически, при достаточной выборке, эта CAPTCHA может быть решена путем подсчета одновременного появления пар текст-изображение.
Однако в действительности это невозможно из-за большого размера библиотеки изображений: для m категорий и n изображений существует m * n пар. Для этого типа CAPTCHA n обычно очень велико.
К счастью, мы можем получить больше от совместного появления изображения и изображения и самих изображений.
Как упоминалось ранее, пары изображений, в которых оба изображения находятся в одной категории, имеют более высокую вероятность появиться в одной и той же CAPTCHA, чем несвязанные пары изображений. Чем больше двух изображений появляются одновременно, тем больше вероятность, что они принадлежат к одной категории.
Кроме того, само изображение содержит много информации. На следующем изображении показан пример «визуального сходства»:
Все изображения листьев лотоса выглядят зелеными: с точки зрения компьютера два вектора изображений находятся на меньшем расстоянии друг от друга, чем до других изображений. На практике выходной сигнал слоя FC7 ImageNet используется для представления изображения, а не исходного вектора RGB.
Ниже приведены примеры подобия косинуса выходного сигнала FC7:
Теперь существует три типа подключений:
- Совместное появление текста и изображения
- Сочетание изображения и изображения
- Визуальное сходство изображения и изображения
Граф может быть построен на основе трех типов информации: каждое изображение представляет собой вершину с вектором вероятности меток (совпадение текста и изображения), и есть ребра с двумя атрибутами (совпадение изображения и изображения и визуальное сходство) среди вершин.
Помните, что указанные выше три измерения не являются 100% надежными, особенно для изображений и пар, которые появлялись только что несколько раз: это может быть шум из-за совпадений и выбросов.
Проблему CAPTCHA можно описать так:
- Правильно маркируйте изображения
- Выберите изображения с пометкой
На графике проблема оказывается: как связать текст (метку) и изображения на основе связей.
Данные выборки ограничены. Чтобы максимально использовать информацию, два атрибута могут быть объединены вместе с функцией сопоставления, которая поддерживает положительный вес краев, связанный с подсчетом совпадений изображения и изображения и визуального сходства.
Напомним вывод о совместном появлении текста и изображения: чем больше текста и изображения совпадают, тем более вероятно, что пары текст-изображение или изображение-изображение связаны. Следовательно, мы можем присвоить значение достоверности меткам на вершине на основе количества совпадений и распространить его через взвешенное ребро. Это идея алгоритма распространения меток.
Теперь CAPTCHA была решена теоретически неконтролируемым методом с помощью графической модели. Обратите внимание, что это онлайн-алгоритм: все значения могут быть обновлены онлайн.
Инженерные решения
Давайте посмотрим на проблему с инженерной стороны: как реализовать этот алгоритм?
Согласно оценке, на веб-сайте Китайской железной дороги для генерации CAPTCHA используется более 200 миллионов изображений из более чем 500 категорий.
По старинке инженерам нужно реализовать с нуля:
- Управляйте изображениями с помощью базы данных "ключ-значение"
- Напишите кучу кода для реализации алгоритма, и есть много вещей, о которых нужно позаботиться:
- Согласованность данных
- Параллельные вычисления
- Эффективность ввода / вывода
- …
Это большие данные: многие проблемы становятся немаловажными при масштабировании данных, и большую часть времени инженерам приходится заново изобретать колеса, чтобы соответствовать их конкретным требованиям.
К счастью, с расцветом рынка графовых баз данных были поставлены некоторые промышленные базы данных для предоставления общих решений для хранения и вычислений.
Яркой новой звездой должна стать компания TigerGraph, в которой я работаю, чей движок изначально реализован на C ++ с возможностью обработки миллиардов вершин и ребер, запросов и обновлений в реальном времени. Вершины и ребра представляют собой вычислительную единицу, что означает, что некоторые операции, такие как уменьшение карты и обход за n шагов, могут быть легко выполнены, а производительность хорошо настроена, что позволяет занести традиционные платформы в историю: задачи, которые должны были занять несколько дней в автономном режиме. обработка теперь может производиться в реальном времени.
TigerGraph выпустил бесплатную версию для разработчиков, которую можно скачать по адресу https://www.tigergraph.com/developer/.
В конце концов
Всплеск данных и вычислительной мощности открыл новую область баз данных: SQL и NoSQL, реляционные и графические, транзакционные и аналитические, все они выполняют важные роли в разных областях.
Что касается графовой базы данных, она определенно становится все более популярной в приложениях для борьбы с отмыванием денег, предотвращения мошенничества в реальном времени, оптимизации логистики цепочки поставок, вычисления оценки влияния / риска и других новых областей.
Ссылка:
Учимся ассоциировать слова и изображения с помощью крупномасштабного графика: https://arxiv.org/abs/1705.07768
