А.М. Сунгурский – Сто шагов в неизвестное (страница 4)
Здесь важно различать две неизвестности. Генетика может описать длительное состояние популяции, но не всегда способна назвать событие, погубившее её последних представителей. А самая молодая найденная кость даёт позднюю подтверждённую дату присутствия, но не свидетельство смерти последнего животного. Новые находки способны передвинуть границу.
Датировки 1993 года заставили искать объяснение столь разным срокам исчезновения мамонтов. Общая картина вымирания должна учитывать и условия, в которых островная популяция смогла сохраняться ещё тысячи лет.
6. 1994. Почему привычный путь к доказательству может не привести к цели
Проверить готовое решение часто легче, чем найти его. Если нам предъявили расписание, можно последовательно убедиться, что два занятия не назначены в одну аудиторию на одно время. Построить подходящее расписание с множеством ограничений бывает гораздо труднее. Это бытовой вход в один из центральных вопросов теоретической информатики: насколько различаются поиск и проверка?
Математики выражают вопрос через классы задач P и NP. Для задач из P существует алгоритм, время работы которого ограничено некоторой степенью размера входных данных. Для задач из NP положительный ответ имеет свидетельство, проверяемое за такое время. Когда о таких алгоритмах говорят «быстро», это условное сокращение. Даже степень может быть слишком высокой для практики, но различие между степенным и экспоненциальным ростом принципиально при увеличении задачи. Вопрос P и NP состоит в том, можно ли любую задачу с быстро проверяемым свидетельством положительного ответа также быстро решить.
Можно было бы попытаться доказать трудность задачи, рассматривая вычисление как схему из простых логических элементов. Каждый элемент выполняет небольшую операцию, а вся сеть преобразует входные биты в ответ. Быстрый алгоритм можно представить семейством схем, размер которых растёт не быстрее некоторой фиксированной степени размера входа. Если для какой-либо задачи из NP доказать, что таких схем недостаточно, то и быстрого алгоритма для неё не существует. Это был бы способ доказать различие P и NP, установив строгую нижнюю границу вычислительной сложности. Нижняя граница означает, что меньше ресурсов не хватит, каким бы изобретательным ни был конструктор в рамках модели.
Но как доказать, что большая схема действительно неизбежна, а не просто более короткую пока не нашли? Александр Разборов и Стивен Рудич исследовали возможности самих методов доказательства. В работе Natural Proofs они выделили общие свойства методов, уже давших результаты для ограниченных видов схем. При определённом криптографическом предположении оказалось, что методы с этой совокупностью свойств не способны установить нужные сильные нижние границы для общих схем.
«Естественное доказательство» здесь — специальный термин. Он не означает всякое понятное рассуждение и не делит математику на естественную и противоестественную. Среди существенных требований — возможность эффективно распознавать используемое свойство функции и его распространённость среди большого множества функций. При этом скорость проверки свойства измеряют относительно размера полной таблицы ответов функции, а не длины одного её входа. Для функции от n входных битов таблица содержит 2 в степени n ответов. Поэтому проверка, быстрая относительно всей таблицы, может требовать огромного времени по сравнению с длиной входа. Теорема относится к точно определённому классу подходов, поэтому её вывод нельзя расширять на любые будущие доказательства.
Откуда в вопросе о доказательствах появилась криптография? Для защиты информации полезны объекты, которые выглядят случайными для ограниченного вычислителя, хотя построены по короткому правилу. Если у наблюдателя достаточно ресурсов, он иногда сможет обнаружить структуру; если ресурсов недостаточно, различение должно оставаться недоступным. Это и есть одна из идей вычислительной псевдослучайности.
Предположим, что найдено достаточно быстро проверяемое свойство, которое встречается у заметной доли функций, но отсутствует у функций с небольшими схемами. Подходящую псевдослучайную функцию можно быстро вычислить по ключу — значит, она допускает небольшую схему и этого свойства у неё нет. У случайно выбранной функции свойство, напротив, иногда будет обнаруживаться. Так проверка свойства дала бы способ различать эти два случая. Если же существуют псевдослучайные функции со стойкостью, требуемой в теореме, такое различение недоступно даже при ресурсах этой проверки. Получается противоречие: либо криптографическое предположение неверно, либо метода доказательства с перечисленными свойствами не существует.
Это ограничение условно. Авторы не доказали, что криптографическое предположение истинно, и не решили вопрос P и NP. Они установили: при сформулированном предположении некоторый широкий путь к сильному результату перекрыт. В математике такой вывод обладает полноценным содержанием, потому что точно обозначает, какие утверждения могут одновременно быть верны.
Можно сравнить его с исследованием местности перед строительством дороги. Инженер ещё не проложил маршрут, но доказал, что дороги определённого типа не смогут пересечь препятствие при заданных условиях. Это знание предотвращает повторение одинаковой неудачи. Придётся либо отказаться от части привычных свойств метода, либо исследовать само условие, создающее препятствие.
В 2007 году работа Разборова и Рудича была отмечена премией Гёделя. Авторы показали, что препятствие может скрываться не только в трудности самой задачи, но и в устройстве привычных способов доказательства.
Для читателя вне математики здесь остаётся полезное различие: отсутствие найденного решения не доказывает невозможность, но и многократное применение привычного метода не гарантирует, что он вообще способен привести к цели.
7. 1995. Граница, которая допускает ошибку
Пусть на диаграмме нанесены два вида объектов: точки одного вида отмечены синим, другого — красным. Если группы хорошо разделены, между ними можно провести прямую так, чтобы все синие точки оказались с одной стороны, а красные — с другой. По этой границе можно классифицировать и новый объект: достаточно посмотреть, на чьей стороне окажется его точка. Но какую прямую выбрать? Известные точки можно правильно разделить несколькими способами. Если новая точка при одном варианте границы окажется на синей стороне, а при другом — на красной, результат классификации будет зависеть от выбора прямой.
Задача обучения состоит не только в воспроизведении уже показанных меток. Нужно выбрать правило, которое будет работать на ещё неизвестных случаях. Это различие между запоминанием и обобщением лежит в основе статистической теории обучения, в развитии которой Владимир Вапник сыграл большую роль ещё в советский период вместе с Алексеем Червоненкисом.
Работа Коринны Кортес и Вапника 1995 года относится к следующему, зарубежному этапу. Они работали в AT&T Bell Laboratories в США и предложили важную форму метода опорных векторов для данных, которые нельзя идеально разделить. Вапник родился в 1936 году в Узбекской ССР, СССР.
Один принцип выбора границы — оставить вокруг неё как можно более широкий свободный зазор. В двумерном рисунке это полоса между двумя группами точек. В пространстве множества признаков геометрия становится многомерной, но идея сохраняется. Чем дальше точка от границы, тем больше её нужно сдвинуть, чтобы она оказалась на другой стороне и получила другую метку.
Ближайшие к разделению примеры особенно важны. Они определяют, насколько широко можно раздвинуть края полосы, не затронув данные. Каждый пример представлен вектором — набором числовых признаков. Отсюда название «опорные векторы»: положение границы опирается на определённые обучающие объекты. Это математическое описание их роли, а не утверждение, что остальные наблюдения всегда бесполезны.
Однако реальные данные редко оказываются послушным рисунком. Измерения шумят, признаки неполны, а метки иногда ошибочны. Если любой ценой провести границу так, чтобы она без исключений согласовалась со всеми примерами, можно получить хрупкое и чрезмерно сложное правило. Правило, подогнанное под каждую такую особенность учебного набора, может хуже классифицировать новые объекты.
Мягкий зазор допускает, что некоторые обучающие точки окажутся внутри разделительной полосы или даже на стороне другой группы. При обучении уравновешивают две цели: сделать полосу шире и уменьшить общий штраф за такие нарушения. Параметр модели определяет, насколько сильно штраф влияет на выбор границы.
Есть и другая трудность: группы могут быть вложены одна в другую, так что прямая в исходных координатах бессильна. Тогда помогает переход к более богатому набору признаков. Можно, например, учитывать не только координаты, но и их сочетания. После такого преобразования нелинейная граница исходного рисунка может соответствовать линейному разделению в новом пространстве.