Традиционные алгоритмы используются в сложных вычислительных инструментах, таких как машинное обучение. Новый подход, называемый алгоритмами с прогнозированием, использует возможности машинного обучения для улучшения алгоритмов.
Алгоритмы – фрагменты кода, которые позволяют программам сортировать, фильтровать и комбинировать данные, среди прочего – являются стандартными инструментами современных вычислений. Как крошечные шестерёнки внутри часов, алгоритмы выполняют чётко определённые задачи в более сложных программах.
Они вездесущи, и отчасти из-за этого их тщательно оптимизировали с течением времени. Например, когда программисту нужно отсортировать список, он прибегает к стандартному алгоритму «sort», который использовался десятилетиями.
Теперь исследователи по-новому смотрят на традиционные алгоритмы, используя сферу искусственного интеллекта, известную как машинное обучение. Их подход, называемый алгоритмами с прогнозированием, использует возможности инструментов машинного обучения для понимания данных, которые обрабатывают традиционные алгоритмы. Эти инструменты действительно омолодили исследования базовых алгоритмов.
Машинное обучение и традиционные алгоритмы – это «два существенно разных способа вычислений, а алгоритмы с прогнозированием – это способ связать их», – говорит Пётр Индик, учёный из Массачусетского технологического института. — «Это способ объединить эти совершенно разные темы».
Недавний всплеск интереса к этому подходу начался в 2018 году со статьи Тима Краски, специалиста по информатике из Массачусетского технологического института, и группы исследователей Google. В ней авторы предположили, что машинное обучение может улучшить хорошо изученный традиционный алгоритм, называемый фильтром Блума, который решает ясную, но сложную проблему.
Представьте, что вы управляете ИТ-отделом своей компании, и вам нужно проверить, посещают ли ваши сотрудники веб-сайты, представляющие угрозу безопасности. Наивно вы можете подумать, что вам нужно проверять каждый сайт, который они посещают, по чёрному списку известных сайтов. Если список огромен (как, вероятно, в случае с нежелательными сайтами в Интернете), проблема становится громоздкой – вы не можете проверить каждый сайт по огромному списку за крошечный промежуток времени до загрузки веб-страницы.
Фильтр Блума предлагает решение, позволяющее быстро и точно проверить, находится ли URL какого-либо конкретного сайта в чёрном списке. Он делает это, по существу, сжимая огромный список в меньший список, который предлагает некоторые конкретные гарантии.
Фильтры Блума никогда не дают ложноотрицательных результатов – если они говорят, что сайт плохой, значит, он плохой. Однако они могут давать ложные срабатывания, поэтому, возможно, ваши сотрудники не смогут посетить некоторые сайты, к которым у них должен быть доступ. Это потому, что они обменивают некоторую точность на огромное сжатие данных – трюк, называемый «сжатие с потерями». Чем больше фильтры Блума сжимают исходные данные, тем они менее точны, но тем больше места они экономят.
Для простого фильтра Блума все веб-сайты одинаково подозрительны, пока не будет подтверждено, что их нет в списке. Но не все веб-сайты созданы равными: некоторые из них с большей вероятностью, чем другие, попадают в чёрный список просто из-за таких деталей, как их домен или слова в их URL. Люди понимают это интуитивно, поэтому вы, вероятно, читаете URL, чтобы убедиться, что они безопасны, прежде чем нажимать на них.
Команда Краски разработала алгоритм, который также может применять подобную логику. Они назвали его «обученным фильтром Блума», и он сочетает в себе небольшой фильтр Блума с рекуррентной нейронной сетью (RNN) – моделью машинного обучения, которая изучает, как выглядят вредоносные URL после просмотра сотен тысяч безопасных и небезопасных веб-сайтов.
Когда обученный фильтр Блума проверяет веб-сайт, RNN действует первым и использует своё обучение, чтобы определить, находится ли сайт в чёрном списке. Если RNN говорит, что он есть в списке, обученный фильтр Блума отклоняет его. Но если RNN сообщает, что сайта нет в списке, то очередь переходит к маленькому фильтру Блума, который точно, но бездумно просматривает сжатые веб-сайты.
Поставив фильтр Блума в конце процесса и предоставив ему последнее слово, исследователи убедились, что обученные фильтры Блума по-прежнему могут гарантировать отсутствие ложноотрицательных результатов. Но поскольку RNN предварительно фильтрует истинные срабатывания, используя то, что она узнала, небольшой фильтр Блума действует скорее как резервная копия, также сводя к минимуму ложные срабатывания. Безобидный веб-сайт, который мог быть заблокирован более крупным фильтром Блума, теперь может пройти через более точный обученный фильтр Блума. По сути, Краска и его команда нашли способ воспользоваться двумя проверенными, но традиционно разными способами решения одной и той же проблемы для достижения более быстрых и точных результатов.
Команда Краски показала, что новый подход работает, но не формализовала почему. Эта задача была возложена на Майкла Митценмахера, эксперта по фильтрам Блума из Гарвардского университета, который нашёл статью Краски «новаторской и захватывающей», но в то же время совершенно неудовлетворительной. «Они проводят эксперименты, говоря, что их алгоритмы работают лучше. Но что именно это означает?» – спросил он.
В 2019 году Митценмахер выдвинул формальное определение обученного фильтра Блума и проанализировал его математические свойства, предоставив теорию, объясняющую, как именно он работает. И в то время как Краска и его команда показали, что это может сработать в одном случае, Митценмахер доказал, что это может сработать всегда.
Митценмахер также улучшил обученные фильтры Блума. Он показал, что добавление в процесс еще одного стандартного фильтра Блума, на этот раз перед RNN, может предварительно отфильтровать отрицательные случаи и упростить работу классификатора. Затем он доказал, что это улучшение, используя теорию, которую он разработал.
Первые дни алгоритмов с прогнозированием шли по этому циклическому пути – инновационные идеи, такие как изученные фильтры Блума, вдохновляют на строгие математические результаты и понимание, что, в свою очередь, приводит к новым идеям. За последние несколько лет исследователи показали, как включать алгоритмы с прогнозированием в алгоритмы планирования, проектирования чипов и поиска последовательности ДНК.
Помимо повышения производительности, эта область также продвигает подход к компьютерным наукам, который становится все более популярным: повышение эффективности алгоритмов за счет их разработки для типичных случаев.
В настоящее время учёные часто разрабатывают свои алгоритмы так, чтобы они преуспели в самом сложном сценарии – сценарии, разработанном противником, пытающимся поставить их в тупик. Например, представьте, что вы пытаетесь проверить безопасность веб-сайта на наличие компьютерных вирусов. Веб-сайт может быть безопасным, но он содержит слова «компьютерный вирус» в URL и заголовке страницы. Это достаточно запутанно, чтобы сбить с толку даже сложные алгоритмы.
Индик называет это параноидальным подходом. «В реальной жизни, – сказал он, – исходные данные обычно не генерируются злоумышленниками». Например, большинство веб-сайтов, которые посещают сотрудники, не так сложны, как наша гипотетическая вирусная страница, поэтому их будет легче классифицировать алгоритму. Игнорируя наихудшие сценарии, исследователи могут разрабатывать алгоритмы, адаптированные к ситуациям, с которыми они, вероятно, столкнутся. Например, хотя в настоящее время базы данных обрабатывают все данные одинаково, алгоритмы с прогнозированием могут привести к созданию баз данных, которые структурируют своё хранилище данных на основе их содержимого и использования.
И это все ещё только начало, поскольку программы, использующие машинное обучение для расширения своих алгоритмов, обычно делают это лишь ограниченным образом. Как и изученный фильтр Блума, большинство этих новых структур включают только один элемент машинного обучения. Краска представляет себе целую систему, состоящую из нескольких отдельных частей, каждая из которых опирается на алгоритмы с прогнозированием, и их взаимодействие регулируется компонентами с улучшенными прогнозированиями.
«Использование этого преимущества повлияет на множество различных областей», – сказал Краска.
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
