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

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

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

Пример использования метода гирлянд

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

На первом шаге мы получим гирлянду синонимов слова часы:

часы — будильник — секундомер — хронометр.

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

Технология эвристического обучения

На третьем шаге получаем следующую комбинацию синонимов и случайных объектов:

часы с кассетой,

часы с подснежником,

часы на транспаранте,

часы в постели, часы в войлоке,

будильник с кассетой,

будильник для постели,

будильник с войлоком,

секундомер с кассетой и т.д.

4. На четвертом шаге получим таблицу случайных объектов и

CЛУЧАЙНЫЙ ОБЪЕКТ	ПРИЗНАКИ
Подснежник	Голубой, маленький, пахучий
Уличная реклама	Большой, тяжелый, красочный.
Войлок	Плотный, колючий, теплый
Кассета	Пластмассовая, хрупкая, музыкальная.
Постель	Чистая, мягкая, теплая, широкая.

5. Комбинируя модернизируемый предмет и его синоним с признаками случайных объектов получаем:

будильник с запахом,

красочный секундомер чистые часы,

колючий будильник и т.д.

6. на данном шаге будем генерировать гирлянды свободных ассоциаций, основой которых будут признаки случайных объектов:[1]

ПРИЗНАК	ГИРЛЯНДА АССОЦИАЦИЙ
Тяжелый	Гиря — спорт — соревнования — призы
Пластмассовый	Пластмасса — ручка — бумага — огонь
Красочный	Журнал — компьютер — дискеты — программы
Хрупкий	Стекло — стакан — вода — дождь
Пахучий	Духи — дамы — цветы — весна
Голубой	Небо — солнце — лето — жара

7. Синтезируя гирлянду ассоциаций и синонимы модернизируемого предмета, получим следующие комбинации:

спортивные часы, призовые часы,

8. На данном шаге не будем продолжать процесс генерирования идей т.к. их уже достаточно.

9. Выбирая из многих идей только рациональные и убирая решения, которые уже воплощены в жизнь[2] (будильник с кассетой, часы с музыкой, женские часы, подводные часы, спортивные часы, часы в ручке и т.д.), получим следующие комбинации:

[RU] Эвристика. Творческие задачи и их решение. Георгий Незабитовский

будильник с запахом,

10. На последнем этапе выбор решений должны производить представители «производства».

Эвристические приемы послужили основой для создания эвристически – интуитивно — ассоциативных методов активизации творческого мышления. Такие методы можно рассматривать как общие предписания по выполнению тех или иных эвристических приемов, а с точки зрения их использования для развития задатков и способностей творческой личности — как готовые упражнения для тренировок.

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

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

Созданием таких программ занимается эвристическое программирование. Оно основано, главным образом, на двух моментах: на воссоздании некоторых интеллектуальных человеческих действий и анализе специфических свойств и особенностей решаемой проблемы. Эвристическая программа — это программа для ЭВМ, использующая эвристика (правила, стратегии, методы или приемы, повышающие эффективность системы, которая пытается найти решения сложных задач).

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

КЛАССЫ РЕШЕНИЙ	ПРИМЕР	ПРИМЕЧАНИЕ
Строгий	Пит — человек -Все люди смертны- Пит — смертен	Это единственное решение
Строгий и эвристический (смешанный)	Пит смертен -Все люди смертны- Пит — человек	Один из возможных вариантов ответа. Ведь Пит может быть и гориллой, к примеру
Эвристический	Пит — человек -Пит — смертен -Все люди смертны	Вывод представляет собой одну из возможных гипотез

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

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

Эвристика и человек

Л. Дж. Фогель писал: «Автоматизация, позволив заменить более низкие уровни функционирования человека работой машин, испытывает некоторые трудности из — за отсутствия глубокого понимания того, что делает человек, принимающий решение.

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

28 марта 1979 г. ранним утром на атомной электростанции «Тримайл Айлэнд» в США в зале управления раздался сигнал тревоги. Сначала операторы посчитали, что это незначительная мелкая неисправность, однако через несколько минут ситуация стала резко ухудшаться.

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

Комиссия, созданная тогдашним президентом США Дж. Картером, пришла к выводу, что основной причиной, приведшей к тяжелым последствиям, стали неправильные действия операторов. А это, в свою очередь, было вызвано тем, что комиссия охарактеризовала на удивление кратко: «неразбериха». Действительно, в течение первых нескольких минут сработало 100 — 200 предупредительных сигналов. Начальник смены Билл Зев позднее писал: «Я заметил, что загорелись все, почти все сигналы аварийного предупреждения. » Отсутствие хорошей системы обработки информации, растерянность и неподготовленность операторов к такой ситуации сделали свое черное дело, однако, к счастью, все окончилось хорошо.

Заключение

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

Быстродействие современных ЭВМ позволяет проводить широкий круг эвристических исследований. За рубежом и в бывшем СССР эвристике посвящалось большое число работ.

Интерес к ней стабильно растет из года в год, теперь мне это понятно.

Список литературы

Столяров А.М. Эвристические приемы и методы активизации творческого мышления. — М: «ВНИИПИ»., 1988.

Столяров А.М. Методологические основы изобретательского творчества. — М: «ВНИИПИ»., 1989.

И.Т.Фролова., Философский словарь- 4-е изд. — М.: «Политиздат»., 1981., — 445 с.

Курс лекций., НКИ., Ладилова М.В., 2002.

Немов Р.С., учебник по Психологии 1 часть/ М., «Владос»., 2000.

Гетманова А.Д., учебник по Логике., М., «Добросовет»., 2000.

В.Э. Фигурнов., IBM PC., М., ИНФРА-М., 1996.

А.П. Журавлёв, Н.А. Павлюк., Язык и компьютер., М., «Просвещение»., 1989.

Управление персоналом., учебник., Т.Ю.Базаров, Б.Л. Ерёмина М.,1998.

Управление персоналом., Энциклопедический словарь., А.Я Кибанова., М., 1998.

Конфликт: семь шагов к миру., Ч.Ликсон., СПб., 1997.

[1] Таблица предоставлена по данным А. Коновича

[2] Курс лекций НКИ., 2002

Об этом полезно знать:

Административная юрисдикция: понятие, признаки, виды производств Административная юрисдикция — установленная правовыми нормами деятельность органов государственного управления и их должностных лиц.
Действие нормативных актов во времени, в пространстве и по кругу лиц Пределы действия нормативных актов по предмету опре­деляются кругом общественных отношений.
Монитор, его характеристики, виды мониторов Монитор (видеомонитор, дисплей) — устройство отображения текстовой и графической информации на экране.
Краткий словарь философских терминов Философия — это культура разумного мышления, которое осуществляется в рационально-понятийной форме.
МЕТОД МОЛЕКУЛЯРНЫХ ОРБИТАЛЕЙ Метод МО является более совершенным методом описания строения молекул.

Источник: studopedia.ru

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

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

· использование интуитивного метода – метод решения может вытекать из практики прошлых действий, которая себя оправдала в большинстве случаев;

· заданием экспертного варианта – задача управления облегчается, если специалист предлагает опорный вариант решения задачи; вблизи его можно проверить изменение критерия эффективности при варьировании отдельных параметров;

· заменой одной задачи на другую – в этом случае модель не будет строго отражать существо рассматриваемой ситуации, но для выработки решения можно использовать алгоритм решения выбранной задачи;

· сужением области исследования – поиск оптимального варианта может упроститься, если ввести дополнительные ограничивающие условия.

Этот методпринятия оптимального решения, основанный на «здравом смысле», применяется, по существу, наряду с любым другим способом выбора наилучшего варианта действий их возможных. Однако особое значение он имеет при отсутствии полной уверенности, что перечень возможных вариантов действий выявлен с исчерпывающей полнотой, а решаемая проблема определена слабо или полностью не определена. /21/

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

· определяется главная цель действий;

· устанавливается тип главной цели действий;

· интуитивно выбирается некоторый вариант действий для достижения цели. При удачном выборе варианта действий главная цель достигается;

· если выбор варианта неудачен, то так же проверяется второй способ действий, затем, если нужно, — третий и т.д., пока не будет найден способ, позволяющий достичь главной цели;

· если все возможные варианты проверены, а достижение главной цели не гарантируется, то из нее выделяются частные цели, которые классифицируются по типам. Для их достижения выбираются соответствующие способы действий так, как при поиске способа достижения главной цели;

· если какие-то частные цели не могут быть достигнуты ни одним из проанализированных вариантов, то каждую из них делят на частные цели более низкого класса, для которых вновь отыскиваются способы достижения. Этот процесс следует продолжать до тех пор, пока не будет найден способ достижения главной цели или не будет установлено, что все частные цели или значимая часть главной цели действий могут быть достигнуты. Эвристический алгоритм, изображенный на рис.6.6, одинаков для поиска способа действий как для достижения главной цели, так и частной цели любого уровня, стоящей перед ЛПР. |21|

Рис.6.6 Примерный порядок действий при выборе лучшего варианта

эвристическим способом

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

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

Глава 11. Реализация принятых решений

Источник: infopedia.su

Большая Энциклопедия Нефти и Газа

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

Эвристическая программа , решающая задачи символического интегрирования в объеме первого курса университета. [2]

Эвристическая программа , решающая задачи символического интегрирования в объеме первого курса университета, в сб. [3]

Любая сильная эвристическая программа содержит множество различных методов и приемов. На каждом этапе процесса решения задачи машина должна сначала решить, какой аспект задачи должен быть исследован, а затем — какой метод для этого должен быть применен. Здесь имеется ситуация выбора, так как обычно мы не можем позволить себе опробовать все возможности.

Для того чтобы иметь дело с какой-то целью или задачей, а значит, и выбрать соответствующий метод, нужно прежде всего определить, какого типа эта задача. Таким образом, необходимость выбора среди возможных действий заставляет нас снабдить машину способами классификации или средствами их создания. Чрезвычайно важно, чтобы машина располагала такими способами классификации, которые реально осуществимы. Но термин осуществимый может быть определен только по отношению к конкретному внешнему миру, с которым машине придется иметь дело, и по отношению к пригодным для него методам. Отличительные особенности, которые не могут быть использованы, не заслуживают распознавания; и методы обычно бесполезны без классификационных схем, помогающих определить, когда они применимы. [4]

Эвристическая программа балансирования сборочного конвейера была проверена на ряде задач различной сложности и дала хорошие результаты. [5]

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

Эти эвристические программы упорядочены произвольно, и первой программе выдается требование породить тест. [7]

Как ранние эвристические программы согласуются с этими определениями. Если мы в качестве примера рассмотрим программу Логик-теоретик [117], станет ясно, что она удовлетворяет последним трем условиям почти так же, как и алгоритм. [8]

Сложность эвристических программ требует более мощного языка, чем язык элементарных машинных команд. [9]

Разработка эвристических программ носит сугубо специфический характер, требует для своего создания большой и трудоемкой работы по наблюдению за объектами исследования и моделирования. [10]

Особенностью эвристических программ является то, что поиск начинается в условиях, когда неизвестен алгоритм и отсутствует информация о возможности решения. Стратегия поиска, который осуществляется специальной программой, изменяется в зависимости от тех или иных пробных действий. Таким образом, применяется тактика проб и ошибок с использованием специальных приемов, позволяющих сократить поиск. Эти приемы или правила называются эвристики. Программа, построенная на эвристических принципах, не гарантирует полного успеха во всех теоретически мыслимых ситуациях, однако в большинстве встречающихся случаев приводит к успешному решению. Этим эвристический алгоритм отличается от обычного. [11]

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

Большинство лучших эвристических программ стремятся просто смоделировать процессы рассуждения человека-эксперта, что не столь просто, но другого пути к успеху нет. [13]

В эвристическую программу легко включить программы для обработки дерева целей И-ИЛИ ( такого, как в SAINT), которое часто оказывается полезным в сложных схемах достижения целей. [14]

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

Источник: www.ngpedia.ru

Эвристика: что это простыми словами, методы эвристики

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

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

Что такое эвристика?

Эвристика (от др.греч. «εὑρίσκω» (heuristiko) — находить и открывать) – это научная область, которая изучает и анализирует созидательную деятельность человека, то есть умение приносить подлинную пользу: материальную, моральную, техническую и другое. Эвристика представляет собой симбиоз из элементов психологии, математики, философии, физики, теории об искусственном интеллекте, лингвистики структурного типа и теории информации. Эвристику можно трактовать по-разному, в зависимости от области её применения. В общем понимании слова –

В разных изданиях можно встретить разные трактовки термина «эвристика», вот, к примеру:

• «Словарь терминов и понятий по обществознанию» (Лопухов, 2013) – эвристика здесь объясняется, как искусство изобретать, методология находить всё новое, используя при этом фантазийный образ, наводящие вопросы, гипотезы, метод интуитивно-художественного поиска и другое;
• «Новая философская энциклопедия» (2010) – педагогическая эвристика, как способ обучения через собственный поиск, формирование продуктивно-познавательных качеств мышления. Педагогическая эвристика служит базовой подготовкой для учащихся к реальной деятельности в различных сферах. Эта форма обучения тесно связана с именем философа Сократа, и считается родственной таким приёмам, как «сократическая беседа»;
• «Словарь практического психолога» (Головин, 1998) – в этом издании эвристика имеет сразу два объяснения. В широком понимании, под этим термином подразумевается наука о творчестве. В более современной трактовке, эвристика представляет симбиоз теоретических и практических методов, касающихся устройства избирательного поиска для решения сложных задач. Эвристика содержит мотивационно-эмоциональные процессы, которые способствуют ограниченному поиску в условиях большого количества вариантов.

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

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

Методы эвристики

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

Учитывая тот факт, что эвристика – это молодая наука, она пока лишена многих фундаментальных понятий. К примеру, это проявляется по отношению определения эвристического метода. Однако, несмотря на некоторые «погрешности», существуют методы, которые во многом могут помочь современному человеку выстроить правильный алгоритм действий при решении личных, или профессиональных проблем. Вот самые яркие примеры эвристических методов:

1. Метод коллективного поиска — это довольно распространённая практика в больших компаниях. Иначе этот метод ещё называют «мозговым штурмом». В чём заключается его особенность? Задача поставлена не перед одним конкретным человеком, например, руководителем, а перед всем коллективом. Каждый сотрудник вносит свою лепту, предлагая своё видение ситуации и вариант решения задачи. Метод коллективного поиска подразумевает сбор всей этой информации, её систематизацию, подробный анализ и отбор лучших предложений;
2. Метод эвристических вопросов – его иначе можно назвать методом наводящих вопросов по типу кто, что, когда, зачем, почему и так далее. Это помогает упорядочить всю имеющуюся информацию, и отсеять ненужное. Это может помочь увидеть ситуацию под совершенно другим углом;
3. Метод проб и ошибок – люди не любят ошибаться, это вызывает у них чувства незначимости собственных предположений. Чаще всего такое мышление формируется со школьной скамьи, где возможность допустить ошибку для многих приравнивается к унижению. Метод проб и ошибок позволяет воспринимать каждый промах, как опыт и возможность увидеть исключение из правил;
4. Метод свободных ассоциаций – здесь подразумевается коллективное решение проблемы, где применяются ассоциации и метафоры. Возникающие в ходе обсуждений нестандартные сравнения и образы могут помочь обнаружить не замеченные ранее грани предмета, или явления;
5. Метод личной аналогии – при решении проблемы, эмпатический метод позволяет поставить человеку себя на место исследуемого объекта. Это помогает воспринять ситуацию по-другому, с точки зрения именно «наблюдаемого». Один из ярких примеров — это метод следователей «думать, как преступник»;
6. Метод функционального анализа – здесь подразумевается, что при исследовании в приоритет ставится не суть объекта, или явления, а его функции и их характеристика. Функции могут приносить пользу, наносить вред, или быть нейтральными. Если отбросить в сторону привычные рамки, в которых ранее применялись эти функции, и попытаться найти им новое применение – это может способствовать оригинальным решениям;
7. Метод синектики – чтобы найти самое оптимальное решение проблемы, в первую очередь, выдвигаются различные предложения (иногда откровенно противоречивые). Далее происходит анализ каждого варианта и выделение самых приемлемых. В основе этого метода так же лежит принцип аналогии;
8. Метод морфологического анализа – напоминает поиск кода к сейфу. Человеку имеет известные компоненты – цифры, ему необходимо найти неизвестный компонент – последовательность этих цифр. Этот поиск предполагает огромное количество комбинаций, и на то, чтобы найти одну верную, необходимо большое количество времени.

История развития эвристики

Отцом-основателем самой сути эвристики считают Сократа. Он имел особенный подход при обучении своих последователей. Для того, чтобы человек смог познать суть предмета, или явления, великий философ использовал наводящие вопросы. Это позволяло ученику выстроить логическую цепочку, и в правильной последовательности «осознать» суть вещи. Подобные диалоги назывались «сократическими беседами» именно они по мнению многих легли в основу эвристических методов.

Метод Сократа неоднократно был описан и развит в трудах многих известных деятелей. В числе таких: Архимед, Г. Галилей, Ф. Бекон и другие. Эвристику с педагогической точки зрения, рассматривали в своих трудах Ж.-Ж Руссо и Л. Н. Толстой. Оба автора пришли к выводу, что ребёнок должен познавать новое, через призму собственного опыта.

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

Новый толчок развития эвристика получила в прошлом столетии, этому способствовало изобретение электронной вычислительной машины. Создание ЭВМ способствовало упрощению и ускорению поиска правильного решения, ведь компьютер, на основе полученных от программиста моделей и алгоритмов, мог подобрать правильный ответ.

Заключение

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

Источник: dnevnik-znaniy.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оно живет

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

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

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

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

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

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

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

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

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

Дмитрий Любарский (теперь на Хабре: MityaLsky)
Департамент разработки технологий

UPD от 0:42 31.05.2012: Появилась вторая часть.

• разработка
• эвристика
• сложные системы

Источник: habr.com