Приближенные средства установления сходств для ДСМ-метода автоматического порождения гипотез тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Шашкин, Леонид Олегович

• Шашкин, Леонид Олегович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Шашкин, Леонид Олегович

Введение

Глава 1. Задача оптимизации множества ДСМ-гипотез и возможные пути ее решения

1.1. ДСМ-метод автоматического порождения гипотез, абдуктивное объяснение как критерий ценности результата

1.2. Методы решения комбинаторных задач, направленный и случайный поиск

1.3. Генетические алгоритмы и условия их успешного применения

Глава 2. Разработка процедур эволюционного поиска сходств

2.1. Пути преодоления проблем классического генетического алгоритма

2.2. Удаление гипотез в процессе преобразования решений

2.3. Объединение решений как метод передачи информации

2.4. Взаимодействие процедур и выбор значений параметров

Глава 3. Результаты эксперимента и их интерпретация

3.1. Фармакология

3.2. Медицинская диагностика

Введение диссертации (часть автореферата) на тему «Приближенные средства установления сходств для ДСМ-метода автоматического порождения гипотез»

Актуальность темы исследования

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

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

Поскольку средства выдвижения гипотез в ДСМ-методе представляют собой совокупность переборных алгоритмов, возникают ограничения, связанные с величиной используемых массивов данных. Количество порожденных ДСМ-системой гипотез зависит от особенностей конкретной ситуации (количества и вида примеров,, а также настроек алгоритма ДСМ-метода) и в некоторых случаях оказывается чрезмерно большим.

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

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

Целью работы является разработка алгоритма, реализующего приближенные средства выбора оптимального множества ДСМ-гипотез.

Для реализации указанной цели в диссертационной работе решались следующие задачи:

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

• анализ различных методов решения комбинаторных задач;

• исследование работы классического генетического алгоритма и выявление условий его успешного применения;

• обоснование необходимости модификации классического генетического алгоритма для решения задачи оптимизации множества ДСМ-гипотез;

• разработка алгоритма поиска, основанного на эволюционной модели.

Предметом диссертационного исследования являются алгоритмы решения комбинаторных задач.

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

• продемонстрирована ограниченность возможностей генетических алгоритмов при решении оптимизационных задач;

• разработан эволюционный алгоритм поиска, учитывающий структуру ДСМ-гипотез;'

• выполнена экспериментальная проверка работоспособности различных методов поиска, включая разработанный алгоритм, на нескольких массивах эмпирических данных;

• проанализированы результаты тестирования алгоритма обработки множества ДСМ-гипотез.

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

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

• обоснована необходимость использования знаний об особенностях решаемой задачи для успешного применения эволюционных алгоритмов;

• предложен метод поиска оптимального подмножества множества ДСМ-гипотез;

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

Практическая значимость работы состоит в следующем:

• разработанный алгоритм позволяет получить сокращенный^ список гипотез, упрощающий работу эксперта в процессе выявления причинно-следственных связей;

• выбор оптимального множества гипотез позволяет сократить перебор при применении ДСМ-системой правил второго рода (вывода по аналогии);

• результаты анализа особенностей работы эволюционных алгоритмов могут быть использованы при создании программных систем.

Апробация работы. Основные положения диссертационной работы были изложены на Двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010г., г. Тверь, Россия).

Публикации. По теме диссертационного исследования опубликовано 6 работ, среди которых 3 работы в ведущих рецензируемых научных журналах, рекомендованных ВАК.

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

Заключение диссертации по теме «Теоретические основы информатики», Шашкин, Леонид Олегович

Результаты работы эволюционного алгоритма, начальные решения - все множество (—)-гипотез (данные медицинской диагностики)

Количество Объяснено Доопределено гипотез (-)-примеров (т)-примеров Частота

Исходное множество гипотез 38 8 2

Решение идентификаторы гипотез)

84} 1 8 2 93

72, 84} 2 8 2 1

84, 101} 2 8 2 1

84, 90} 2 8 2 5

Среднее значение 1,07 8 2

Наименьшее и наибольшее значения

Мт,Мах] [1,21 [В, 81 [2, 2]

Ср. кв. отклонение 0,26 0 0

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

Таким образом, изучение примеров из разных областей показало, что множество порожденных ДСМ-системой гипотез может быть значительно сокращено без ухудшения его существенных характеристик. Выбор абдукции в качестве критерия при оценке множеств гипотез оказался достаточно продуктивным. Подмножества гипотез, отобранные на основании их способности объяснять исходные факты, как правило, позволяли также доопределить максимальное количество (т)-примеров.

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

Во всех рассмотренных случаях разработанный эволюционный алгоритм в своей работе использовал только множество исходных положительных или отрицательных примеров; Дополнительное , использование (т)-примеров для оценки множеств гипотез при селекции решений увеличивает долю решений (если она уже не равна 100%); пригодных для применения в выводах по аналогии.

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

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

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

Заключение

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

Основные научные и практические результаты, полученные автором диссертационного исследования, заключаются в следующем.

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

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

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

4. Разработаны вероятностные процедуры поэтапной модификации множеств, предназначенные для работы с множеством ДСМ-гипотез.

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

6. Получено эмпирическое подтверждение преимущества разработанного эволюционного алгоритма перед классическим генетическим и жадным алгоритмами при оптимизации множества гипотез, порожденных ДСМ-системой.

Список литературы диссертационного исследования кандидат технических наук Шашкин, Леонид Олегович, 2010 год

1. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез //НТИ. Сер. 2. 1999. N 1-2. С. 45-53.

2. Блинова В.Г., Добрынин Д.А. Языки представления химических структур в интеллектуальных системах для конструирования лекарств // НТИ. Сер. 2. 2000. N 6. С. 14-21.

3. Блинова В.Г., Решетникова В.В., Булычев Ю.Н., Добрынин Д.А. Интеллектуальный анализ цитотоксической активности химических соединений с помощью стратегий ДСМ-метода // НТИ Сер. 2. 2010. N6. С. 14-23.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. М.: ФИЗМАТЛИТ, 2006. -320 с.

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. - 432 с.

6. Забежайло М.И. О характеристиках переборных задач, возникающих при автоматическом порождении гипотез ДСМ-методом // НТИ. Сер. 2. 1988. N1.0. 28-31.

7. Кузнецов С.О. Сложность алгоритмов обучения и классификации, основанных на поиске пересечения множеств // НТИ. Сер. 2. 1991. N 9. С. 8-9.

8. Курейчик В.М., Родзин С.И. Эволюционные вычисления: генетическое и эволюционное программирование // Новости искусственного интеллекта. 2003. N5. С. 13-19.

9. Ю.Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудинского. М.: Горячая линия - Телеком, 2006. - 452 с.

10. Финн В.К. Синтез познавательных процедур и проблема индукции // НТИ. Сер. 2. 1999. N 1-2. С. 8-45.

11. Харчевникова Н.В., Блинова В.Г., Добрынин Д.А., Нович М., Врачко М. Интеллектуальный анализ канцерогенности химических соединений с помощью стратегий ДСМ-метода // НТИ. Сер. 2. 2009. N11. С. 18-23.

12. Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning // McGraw-Hill, USA, 1989.

13. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control andArtificial Intelligence. USA: University of Michigan, 1975.

14. Публикации автора по теме диссертации

15. Публикации в изданиях, рекомендованных ВАК

16. Балдин Е.В., Шашкин Л.О. Генетические алгоритмы: возможности и ограничения // НТИ. Сер. 2. 2000. N 8. С. 19-33.

17. Шашкин Л.О. Применение методов эволюционного моделирования для оптимизации множества ДСМ-гипотез // Искусственный интеллект и принятие решений, N 3, 2010. С. 33-39.

18. Шашкин Л.О. Сравнение приближенных способов поиска сходств для ДСМ-метода//НТИ. Сер. 2. 2010. N 12. С. 9-13.701. Другие публикации

19. Балдин Е.В., Шашкин JI.O. Об эффективности генетических алгоритмов // Математические методы решения инженерных задач. -М.: МО РФ, 1999. С. 5-11.

20. Шашкин JI.O. Применение генетических алгоритмов к оптимизационным задачам // Математика и практика; Математика и культура. М.: Редакция журнала «Самообразование» и МФ «Семигор», 2000. С. 50-58.