Грязное программирование с чистой душой: разработка эвристических систем (часть 1)

Химики любят говорить, что химия занимается исследованием грязных веществ чистыми методами, физика — чистых веществ грязными методами, а физическая химия, дескать, исследует грязные вещества грязными методами. В областях, традиционно относящихся к искусственному интеллекту или смежных с ними (распознавание образов, решение NP-трудных задач, обработка текста и т.д.), большинство задач являются грязными. Т.е. плохо поддающимися формальному описанию и не имеющими четких критериев правильности решения. Не знаю, как выкручиваются химики, а программистам редко удается порешать такие задачи, не запачкавшись. Программирование грязных задач тоже грязно, и здесь грязное — не значит плохое. Эта статья не о том, как сохранить чистоту и стерильность. Эта статья о том, как, вооружившись ломом мужеством и терпением, погрузиться в глубинные литосферные слои и выжить.

Итак, предположим, что вам необходимо разработать систему, демонстрирующую сложное поведение (например, переводящую бабушек через дороги, или, в порядке экзотики, распознающую текст на изображении). Если вам кажется, что задача недостаточно грязная, попытайтесь написать работающую систему, улучшить качество ее работы, насколько это возможно, а затем улучшить еще сильнее. Желательно, если при этом не ухудшится быстродействие, идеально — если улучшится.

Наука умеет много гитик?

Существует два устойчивых мифа о том, как следует решать сложные задачи плохоформализуемого вида.

Миф 1. Великая сила математики

Распространено заблуждение, что в мире сложных задач все учтено могучим ураганом математики. В представлении многих программисты, занимающиеся решением ИИ-подобных задач, — яйцеголовые ученые в белых халатах, проводящие почти все время за грифельной доской и решающие зубодробительные криволинейные интегралы. Спешу огорчить, что математические методы, хотя и крайне полезные в интересных случаях, имеют удручающе ограниченную область применения. Скорее, правильным подходом было бы попытаться вычленить поддающиеся переднему краю науки подзадачи и использовать их решения в качестве отдельных компонентов системы. Например, для простых случаев неплохо изучена задача кластеризации объектов, т.е. разбиения их на группы, и разработаны основанные на фундаменте теории вероятностей/математической статистики методы для ее решения, где встречаются очаровательно смотрящиеся на грифельной доске формулы. На том же теоретическом фундаменте основана многообещающая и интенсивно исследующаяся в последнее время методология построения сложных систем — байесовские сети. Но в целом математические шестеренки слишком красивы и плотно подогнаны друг к другу, чтобы их не заклинило от попавших в них крупных комьев грязи. Рано или поздно приходится снимать халат и выходить из тиши кабинета.

Миф 2. Все решит Большая Нейронная Сеть

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

Принципиальная ограниченность «красивых» подходов в том, что все они слишком зависят от каких-либо симпатичных предположений. Например, для задачи классификации предположения могут состоять в том, что множество признаков объектов подчиняется смешанному гауссовому распределению, или что эти признаки независимы друг от друга. В случае нейронных сетей было бы замечательно, чтобы признаки были хотя бы приблизительно линейно разделимы. На худой конец, пусть признаки будут линейно разделимы в другом, хотя бы и неявно определенном пространстве.

В реальной жизни объекты почему-то очень не хотят нас слушаться и вечно выходят за отведенные тем или иным методом рамки. Тут-то и выясняется: чтобы адаптировать теоретическую красотулю к суровой действительности, приходится очень сильно напрягать мозги, мучительно настраивая систему или модифицируя выбранный способ решения. А когда исходные посылки начинают трещать по швам, приходится отказываться от родной и полюбившейся за годы страданий системы и обращаться к конкурентным подходам.

Эвристическое программирование

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

Итак, на определенном этапе развития программа, решающая по-настоящему грязную задачу, фактически превращается в экспертную систему, написанную на языке программирования общего назначения (если удалось обойтись специализированным языком, то речь идет об экспертной системе в классическом понимании этого термина, но суть рассуждений от этого не меняется). Неотъемлемой чертой такой программы — экспертной системы является обилие эвристик, явно выраженных в коде. Эвристики представляют собой сомнительные с точки зрения научной обоснованности действия, правила и критерии, что-нибудь наподобие if( word.LettersCount() >= 4 ) {…}. Кусок программы, составленный из эвристик, сам является эвристикой следующего уровня, и так далее до уровня всей системы. Такой код легко узнать по именам переменных, методов и классов. Всякие suspiciousImage, looksLikeTable(), GoodTextExtractor. Выдают также и комментарии:

«скрытый текст штрафуем мягко: искать его непросто», «картинку порвать страшно, поэтому резать запрещаем почти всеми объектами».

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

В дальнейшем в этой статье характеристики «эвристическое» и «грязное» применительно к программированию являются взаимозаменяемыми.

Оно живет

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

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

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

Ситуация очень напоминает рожденный эволюцией геном. Бессмысленно выяснять, вреден ли данный ген на основании абстрактных рассуждений. Важно, повышает ли ген вероятность особи выжить. В программе, как и в геноме, обязательно возникают сложные и нетривиальные взаимодействия эвристик/генов. Известно, что наличие первой группы крови повышает вероятность заболеть холерой, но понижает чувствительность к малярии. Таким образом, полезность набора генов группы крови зависит от места проживания человека. В эвристической программной системе повсеместны ничуть не менее причудливые и неожиданные зависимости.

Итак, система становится пугающе сложной. Возникает соблазн принять ее такой, какая она есть, и развивать исключительно в соответствии с принципом общей полезности, как это делает эволюция с геномом. Если у вас в запасе пара миллиардов лет и ресурсы размером с планету, то такой подход вполне годится, и вторую часть статьи можно не читать. Простым же смертным может стать интересно, существует ли способ как-то преодолеть рост сложности. Краткий ответ: универсального рецепта нет, но надо стараться. Более подробные рассуждения — во второй части.

Дмитрий Любарский
Департамент разработки технологий

Автор: ABBYYTeam