автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Теория машинного обучения в решетках формальных понятий

1. Введение.

1.1. Теория упорядоченных множеств и теория решеток

1.2. Анализ формальных понятий (АФП).

1.3. Машинное обучение.

1.4. ДСМ-метод.

1.5. Теория алгоритмической сложности.

2. Гипотезы и классификации: теоретико- решеточная и теоретико-графовая интерпретации, связь с родственными понятиями.

2.1. Основные определения: гипотезы и классификации.

2.2. Теоретико-решеточная интерпретация гипотез и классификаций.

2.3. Теоретико-графовая интерпретация гипотез.

2.4. Теоретико-графовая интерпретация классификаций —

2.5. Гипотезы и родственные понятия из анализа данных и искусственного интеллекта.

2.5.1. Гипотезы и импликации в АФП.

2.5.2. Импликации и зависимости в реляционных базах данных.

2.5.3. Пространство версий между минимальными гипотезами и минимальными посылками.

2.5.4. Гипотезы, решетки понятий и деревья решений.

3. Алгоритмические проблемы порождения понятий, гипотез и классификаций.

3.1. Число всех формальных понятий.

3.2. Число минимальных гипотез.

3.3. Задачи распознавания для понятий с ограничениями на размер.

3.4. Задачи распознавания для гипотез с ограничениями на размер.

3.5. Сложность классификации и проверки критерия достаточного основания.

3.6. Алгоритмы порождения формальных понятий, решеток понятий, гипотез и классификаций.

3.6.1. Алгоритм Замыкай-по-Одному.

3.6.2. Алгоритм порождения решетки понятий.

3.6.3. Алгоритмы порождения гипотез и минимальных гипотез.

3.6.4. Пошаговый алгоритм для вычисления минимальных гипотез.

3.6.5. Вычисление классификаций и проверка критерия достаточного основания.

3.6.6. Вычисление предгипотез и обобш;енных гипотез.

4. Устойчивость формальных понятий и гипотез.

4.1. Мотивация и прецеденты.

4.2. Индексы устойчивости: определения и основные свойства.

4.3. Изменение устойчивости с ростом числа примеров.

4.4. Алгоритмическая сложность вычисления индексов устойчивости.

4.5. Алгоритм с полиномиальной задержкой для вычисления индексов устойчивости.

4.6. Приближенное вычисление индексов устойчивости

5. Узорные структуры и их проекции.

5.1. Узорные структуры: определение и связь с формальными контекстами.

5.2. Вычисления в узорных структурах.

5.3. Проекции узорных структур.

5.4. Порождение гипотез в проекциях.

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

Во-первых, это область математических средств ДСМ-метода автоматического порождения гипотез [45, 46, 47, 48, 49, ?, 57]. С одной стороны, ДСМ-метод представляет из себя теорию правдоподобного вывода, формализованную в виде бесконечнознач-ной логической теории первого порядка с кванторами по кортежам переменной длины [57]. В рамках этой теории возможно осуш;ествление и обоснование индуктивного и абдуктивного вывода. С другой стороны, реализация ДСМ-метода и практика его применения позволяет рассматривать его как метод машинного (автоматического) обучения [28, 30]. Принципиальная особенность ДСМ-метода как системы машинного обучения заключается в использовании понятия сходства, определяемого в виде алгебраической операции с некоторыми свойствами, в то время как для большинства методов машинного обучения типичным является определение сходства в виде метрики или отношения [30]. Кроме того, если основным принципом, лежап];им в основе методов машинного обучения, помимо нахождения ре-шаюп1;его правила, разделяю п];его положительные и отрицательные примеры, есть принцип построения минимального покрытия положительных примеров (не покрываюп];его отрицательных примеров в силу вышеуказанного принципа разделения положительных и отрицательных примеров, см. например, [115], 119]), то при сохранении идеи разделения положительных и отрицательных примеров, ДСМ-метод использует принцип нахождения максимального сходства этих примеров. Не желая принизить ценность идеи покрытия (задающего - в смысле отношения поглощения на гипотезах - нижнюю границу множества всех возможных гипотез), мы настаиваем на том, что принцип максимального сходства, некоторым образом двойственный принципу минимального покрытия, указывает на другую, верхнюю, границу множества возможных гипотез. Соотношение между этими границами можно охарактеризовать в терминах наиболее общих и наименее общих обобщений [126, 127] и пространств версий [117, 118, 98, 99, 114]. Определение гипотез и классификаций в терминах сходства имеет естественную теоретико-графовую интерпретацию в терминах трех- и четырех-дольных графов и связано с наличием в них полных двудольных подграфов с определенными свойствами.

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

Третьим источником мотивации данной работы послужила деятельность по применению ДСМ-метода в области анализа данных, имеющих "сложную", например, реляционную структуру, как в случае химических соединений [28]. Эта деятельность предполагала использование тех или иных представлений, из которых наиболее естественными являются трехмерное геометрическое представление, теоретико-графовое представление, а также представление с помощью дескрипторных языков (т.е. как множеств). Определение гипотез и классификаций на основе операции сходства позволяет работать с любым из этих представлений. Наиболее важные вопросы здесь - это проблема эффективного вычисления сходства и согласованность результатов при работе с разными представлениями. В самом деле, работа с данными о трехмерной или даже графовой структуре объектов сопряжена с высокой алгоритмической сложностью, в то время как работа с дескрипторными (теоретико-множественными) представлениями очень часто приводит к потере информации. Как создать иерархию представлений, позволяющую судить о результатах в более полном, но вычислительно менее эффективном представлении по результатам в менее полном, но более эффективном? При решении этих проблем возникли понятия узорных структур и их проекций. Проекции задают гомоморфизмы узорных структур и, тем самым, отношение сравнимости различных представлений данных.

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

• Какова комбинаторная и теоретико-решеточная природа гипотез и классификаций?

• Возможно ли эффективное вычисление гипотез и классификаций?

• Как оценивать устойчивость гипотез?

• Каково соотношение между гипотезами и классификациями в разных представлениях?

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

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

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

86], функциональных зависимостей в теории реляционных баз данных [40], моделях абдукции [66], пространствах версий [118 и деревьях решений [132]. Это определяет место гипотез среди родственных объектов из области анализа данных, теории баз данных и искусственного интеллекта.

Третий круг проблем связан с порождением множеств формальных понятий, гипотез, и классификаций. В связи с этим в главе 3 будут, во-первых, рассматриваться алгоритмы порождения множества формальных понятий и их решеток, множеств гипотез и классификаций. Во-вторых, будет рассматриваться алгоритмическая сложность задач распознавания и перечисления, связанных с порождением формальных понятий и гипотез: задачи перечисления понятий, гипотез и минимальных гипотез, задачи распознавания понятий, гипотез, и классификаций. Для задач этого типа устанавливается либо трудноразрешимость (в терминах NP- или, соответственно, #Р-полноты) либо полиномиальная вычислимость, в ряде случаев на основе использования теоретико-графовой интерпретации из главы 2.

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

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

6 Заключение

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

В процессе работы над диссертацией автором получены сле-дуюш;ие основные научные результаты.

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

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

3. Показано, что задача подсчета всех формальных понятий (а следовательно, и числа всех гипотез) #Р-полна, а следовательно #Р-полна задача определения размера решетки, заданной упорядоченным множеством ее Л- и У-неразложимых элементов. Показана также #Р-полна задачи подсчета всех минимальных (по вложению) гипотез.

4. Для некоторых задач распознавания о существовании понятий и гипотез с определенными ограничениями на размер установлена полиномиальная разрешимость, а для других - КР-полно-та.

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

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

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

1. Ахо A.B., Хопкрофт Дж.Ф., Ульман Дж.Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. -536 с.

2. Виркгоф Г. Теория решеток. М.: Наука, 1984. - 568 с.

3. М.М. Бонгард, Проблема узнавания, М., Наука, 1967.

4. М.Н. Вайнцвайг, Алгоритм обучения распознаванию образов "Кора" // Алгоритмы обучения распознаванию образов. М., Сов. радио, 1973. С. 82-91.

5. Вагин В.Н. Дедукция и обобш;ение в системах принятия решений, М.: Наука, 1988. 384 с.

6. В.Н. Вапник, А.Я. Червоненкис, Теория распознавания образов, М., Наука, 1974, 418 с.

7. Виноградов Д.В. Об одной модели вероятностного алгоритма // НТИ. Сер.2.- 1996.- N 5-6.- С. 21-27.

8. Виноградов Д.В. Формализация правдоподобных рассуждений в логике предикатов // НТИ. Сер.2. 2000. - N 11. - С. 17-20.

9. Гретцер Г. Обш;ая теория решеток. М.: Мир, 1982. - 452 с.

10. Русакова СМ. Канонические представления сходств // НТИ. Сер.2. 1987. - N9. - С.19-22

11. Русакова СМ., Финн В.К. О формализации локального и глобального сходств // НТИ. Сер.2.- 1986.- N6.- С. 16-19

12. Русакова СМ., Финн В.К. О новых средствах формализации понятия сходства // НТИ. Сер.2.-1987.- N 10.- С. 14-22

13. Русакова СМ., Кузнецов CO., Сходство в обобш;енном ДСМ-методе и алгоритмы его порождения, НТИ, Сер. 2, N 6, 1995.

14. Гэри М., Джонсон Д. Вычислительные машины и трудно-решаемые задачи.- М.: Мир, 1982.- 416 с.

15. А.И. Дмитриев, Ю.И. Журавлев, Ф.П. Кренделев, О математических принципах классификации предметов или явлений // Дискретный анализ. Новосибирск, ИМ СО АН СССР, 1966. Вып. 7. С. 3-17.

16. Дунаев В.В., Поляков О.М. Методологические аспекты реляционной теории классификации// НТИ. Сер.2 1987. -N4. - С.21-27.

17. Е.В. Дюкова, Асимптотически оптимальные тестовые алгоритмы в задачах распознавания. Проблемы кибернетики. М., наука, 1982, Вып. 39, С. 165-199.

18. Е.В. Дюкова, Ю.И. Журавлев, Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Журнал вычислительной математики и математической физики, 2000, т. 40, N 8, С. 1264-1278.

19. Ю.И. Журавлев, Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. М., Наука, 1978, Вып. 33, С. 5-68.

20. Ю.И. Журавлев, Избранные научные труды, М., Магистр, 1998

21. Забежайло М.И., Ивашка В.Г., Кузнецов СО., Михеен-кова М.А. Хазановский К.П., Аншаков О.М. Алгоритмические и программные средства ДСМ метода автоматического порождения гипотез// НТИ. Сер.2.- 1987.- N10.-С. 1-14.

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

23. Зорин П.В., Кузнецов СО. Механизм иерархической структуризации больших динамических гипертекстов, НТИ, Сер. 2 1996, N 3.

24. Зорин П.В., Кузнецов СО. Об одном подходе к автоматическому обучению гиперсети больших динамических гипертекстов. 5-я Национальная Конференция по Искусственному Интеллекту (КИИ-96), т.2, с.326-328, Казань, АИИ, 1996.

25. Кузнецов СО. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида // НТИ. Сер.2.- 1989.- N1. С.23-28.

26. Кузнецов СО. Введение в ДСМ-метод // Семиотика и информатика.- 1991.- Вып.31. С.5 - 40.

27. Кузнецов СО. Устойчивость как оценка обоснованности гипотез, получаемых на основе операционального сходства// НТИ. Сер.2 1990. - N12. - С.21-29.

28. Кузнецов СО. ДСМ-метод как система автоматического обучения // Итоги науки и техн. Сер. Информатика. 1991.- 15. С. 17-54

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

30. Кузнецов СО. Модели и методы автоматического обучения // Итоги Науки и Техники, сер. Вычислительные науки, 1991, Т.7, С.89-137.

31. Кузнецов СО. О сложности обучения и классификации, основанных на операции сходства, 3-я Национальная Конференция по Искусственному Интеллекту (КИИ-92), т.1, с.32-34, Тверь, АИИ, 1992.

32. Кузнецов СО. Быстрый алгоритм построения всех пересечений объектов из конечной полурепхетки // НТИ. Сер.2.- 1993. N1. - С. 17 - 20

33. Кузнецов СО. Алгоритмическая сложность порождения гипотез и классификаций, основанных на поиске пересечения множеств // Доклады АН. 1994. - 335, N3 - С. 300-303

34. Кузнецов СО., Финн В.К. О модели обучения и классификации, основанной на операции сходства, Обозрение Прикладной и Промышленной Математики 3, 1996, N 1, 66-90.

35. Кузнецов СО. Формальный анализ понятий с помоп];ью ДСМ-метода, 6-я Национальная Конференция по Искусственному Интеллекту (КИИ-92), т.2, с.591-592, Пуш;ино, АИИ, 1998.

36. Кузнецов СО. О некоторых вопросах анализа понятий // НТИ. Сер.2. 1999.- N 1-2. - С. 57-61.

37. Кузнецов СО., Объедков СА. Алгоритмы построения множества всех понятий формального контекста и его диаграммы Хассе // Известия Академии Наук, Теория и системы управления. 2001. N 1. - С. 120-129.

38. Кузнецов СО. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика. 2001. N 10. - С. 3-27.

39. Левит В.Е. Алгоритм поиска подматрицы максимального периметра, состоящей из единиц на 0-1 матрице // Методы передачи и обработки информации: Сб. тр. / ИППИ АН СССР. М., 1988. - С. 42-45

40. Мейер Д. Теория реляционных баз данных, Москва, Мир, 1987.

41. Поляков О.М., Дунаев В.В. Классификационные схемы: синтез через отношения// НТИ. Сер.2 1985. - N6. - С. 1521.

42. Поляков О.М. Классификационная модель данных// НТИ. Сер.2 1986. - N9. - С. 13-20.

43. Поляков О.М. О систематизации// НТИ. Сер.2 1988. -N12. - С.21-28.

44. К.В. Рудаков, Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. М., Наука, 1989, С. 176-201.

45. Финн В. К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф.Бэкона -Д.С.Милля.// Семиотика и информатика.- 1983. Вьш.20.-С.35-101

46. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техн. Сер. Теория вероятностей Мат. стат. Теор. кибернет. М.:ВИНИТИ, 1988. -28 - С.3-84

47. Финн В.К. Об обобщенном ДСМ-методе автоматического порождения гипотез // Семиотика и информатика.- 1989.-Вып.29.- С.93-123

48. Финн В. К. ДСМ-метод автоматического порождения гипотез с отношением порядка // Семиотика и информатика.- 1990.- Вып.31 С.69 - 103

49. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники. Сер. Информатика. М.: ВИНИТИ, 1991. - 15 - С.54-101

50. Финн В.К., Михеенкова М.А. О ситуационном расширении ДСМ-метода автоматического порождения гипотез // ПТИ. Сер.2.- 2000.- N 11. С. 20-30.

51. Харари Ф. Теория графов, М., Мир, 1973.

52. Чечкин А.В. Математическая информатика, М., Наука, 1991.

53. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике.- М.: Мир, 1976.- 133 с. )

54. Эфрон В. Нетрадиционные методы многомерного статистического анализа М.: Финансы и статистика, 1988.263 с.

55. A.V. Aho and J.E. Hopcroft, The Besign and Analysis of Computer Algorithms, Addison-Wesley (1974).

56. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, 1983.

57. O.M. Anshakov, V.K. Finn, and D.R Skvortsov, On axiomati-zation of many-valued logics associated with the formalization of plausible reasonings. Stud. Log., 25, No. 4, 23-47 (1989).

58. W.W. Armstrong, Dependency structure of data base relationships, in Proc. IFIP Congress, Geneva, 1974, 580-583.

59. R. Balbes and P. Dwinger, Distributive Lattices, University of Missouri Press, 1974.

60. M. Barbut and B. Monjardet, Ordre et classification, II, Hachette, Paris, 1970.

61. H.-G. Bartèl, Matematische Methoden in der Chemie, Spektrum, Heidelberg, 1996.

62. G.D. Birkhoff, Lattice Theory, Amer. Math. Soc. (1979).

63. J.P. Bordat, Calcul pratique du treillis de Galois d'une correspondance, Math. Sei. Hum., No. 96, 31-47 (1986).

64. T. Bylander, D. AUemang, M. C. Tanner, and J. R. Josephson, The computational complexity of abduction, Artif. Intell., 49, No. 1, 25-60 (1991).

65. R. Carnap, The Logical Foundations of Probability, University of Chicago Press, Chicago, 1962.

66. L. Chaudron and N. Maille, Generalized Formal Concept Analysis, in Proc. 8th Int. Conf. on Conceptual Structures, ICCS'2000, G. Mineau and B. Ganter, Eds., Lecture Notes in Artificial Intelligence, 1867, 2000, pp. 357-370.

67. M. Chein, Algorithme de recherche des sous-matrices premières d'une matrice. Bull. Math. R.S. Roumanie, No. 13, No. 1, 21-25 (1969).

68. E. F. Codd, A relational model for large shared data banks, Comm. ACM 13, 1970, 377-387.

69. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990.

70. J. Demetrovics, L. Libkin, and I. Muchnik, Functional Dependencies in relational databases: A lattice point of view, Discrete Applied Mathematics, 40, 155-185, 1992.

71. V. Duquenne and J.-L. Guigues, Families minimales d'implications informatives resultant d'un tableau de données binaires, Math. Sei. Humaines, 95, 5-18, 1986.

72. V. Duquenne, Contextual implications between attributes and some representation properties for finite lattices, In: Beiträge zur Begriffsanalyse (B. Ganter, R. Wille, and K. E. Wolff, eds.), B. I. Wissenschaft-Verlag, Mahnnheim, pp.213-239, 1987.

73. B. Efron, The Jackknife, the Bootstrap and Other Resampling Plans, CBMS-NSF Regional Conference Series in Applied Mathematics, 38, SIAM, Philadelphia, 1982.

74. M. Erné, Einführung in die Ordnungstheorie, Mannheim, B.I.-Wissenschaftsverlag, 1982.

75. S. Ferré and 0. Ridoux, A Logical Generalization of Formal Concept Analysis, in Proc. 8th Int. Conf. on Conceptual Structures, ICCS'2000, G. Minean and B. Ganter, Eds., Lecture Notes in Artificial Intelligence, 1867, 2000.

76. V.K. Finn, T. Gergely and S.O. Kuznetsov (1996), Plausible Reasoning for Open Problem Domains, Proceedings of IEEE International Symposium on Intelligent Control, Dearborn, Michigan, (USA), September 15-18, 1996, 111-116.

77. R. Freese, J. Jezek, J.B. Nation, Free Lattices, AMS, Providence, 1995.

78. J. G. Gánasela, CHARADE: A rule system learning system. In: Proc. of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87), Milan, Italy, August 23-28 (1987), 117-124, 1987.

79. J. G. Gánasela, Improvement and refinement of the learning bias semantic. In: Proc. of the 8th Europ. Conf. on Artificial Intelligence (ECAI-88), pp. 81-86, 1988.

80. B. Ganter and S.O. Kuznetsov, Stepwise Gonstruction of the Dedekind-MacNeille Completion, Proc. 6th Int. Conf. on Conceptual Structures, ICCS'98, M-L. Mugnier, M. Chein, Eds., Lecture Notes in Artificial Intelligence, 1453, 1998, pp. 295302.

81. B. Ganter and S.O. Kuznetsov, Formalizing Hypotheses with Concepts, Proc. 8th Int. Conf. on Conceptual Structures, ICCS'98, G. Mineau and B. Ganter, Eds., Lecture Notes in Artificial Intelligence, 1867, 2000, pp. 342-356.

82. B. Ganter and S.O. Kuznetsov, Pattern Structures and Their Projections, Proc. 9th Int. Conf. on Conceptual Structures, ICCS'Ol, G. Stumme and H. Delugach, Eds., Lecture Notes in Artificial Intelligence, 2120 2001, pp. 129-142.

83. B. Ganter and K. Reuter, Finding all closed sets: a general approach. Order, 8, 283-290, 1991.

84. B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999.

85. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, Freeman, 1979.

86. R. Godin, R. Missaoui, and H. AUaoui, Incremental Concept Formation Algorithms Based on Galois Lattices, Computational Intelligence, 1995.

87. E.M. Gold, Language identification in the limit // Information and Control, 1967, 10, pp. 447-474.

88. L. A. Goldberg, Efficient Algorithms for Listing Combinatorial Structures, Cambridge University Press, 1993.

89. G. Gratzer, General Lattice Theory, Birkhauser Verlag, BaselStuttgart (1978).

90. A. Guenoche, Construction du treillis de Galois d'une relation binaire, Math. Inf. Sci. Hum., No. 109, 41-53 (1990).

91. R. Gugisch, Lattice Contexts: A Generalization in Formal Concept Analysis, unpublished manuscript, 2000.

92. C.A. Gunter, T.-H. Ngair, and D. Subramanian, The Common Order-Theoretic Structure of Version Spaces and ATMSs, Artificial Intelligence 95, 357-407, 1997.

93. R. M. Haralick, The diclique representation and decomposition of binary relations, J. ACM, 21, 356-366 (1974).

94. F. Harary Graph Theory, Reading, Addision Wesley, 1969.

95. J. Hereth, G. Stumme, R. Wille, and U. Wille, Conceptual Knowledge Discovery and Data Analysis, Proc. 8th Int. Conf. on Conceptual Structures, ICCS'98, G. Mineau and B. Canter, Eds., Lecture Notes in Artificial Intelligence, 1867, 2000, pp. 421-437.

96. H. Hirsh, Generalizing Version Spaces, Machine Learning 17, 5-46, 1994.

97. H. Hirsh, N. Mishra, and L. Pitt, Version Spaces Without Boundary Sets, in Proc. of the 14th National Conference on Artificial Intelligence (AAAI97), AAAI Press/MIT Press, 1997.

98. A. Hutchinson, Algorithmic Learning, Claredon Press, Oxford, 1994.

99. D.S. Johnson, M. Yannakakis, and C.H. Papadimitriou, On Generating all Maximal Independent Sets, Information Processing Letters, 27, 119-123, 1988.

100. R. Karp and G.A. Hopcroft, 2.5-Algorithm for Maximum Matching in Bipartite Graphs, SIAM J. Comput., 2, no. 2, 225-231, 1973.

101. S.O. Kuznetsov, Mathematical aspects of concept analysis. Journal of Mathematical Science, Ser. Contemporary Mathematics and Its Applications, 18, 1654-1698, 1996.

102. S.O. Kuznetsov, Concepts, Hypotheses, and Forecasts: An Algorithmic Complexity Perspective, Proceedings of the Workshop on Applied Semiotics (W30), European Conference on Artificial Intelligence (ECAI-96), Budapest, August 14-18, 1996, 17-22.

103. S.O. Kuznetsov, On Computing the Size of a Lattice and Related Decision Problems, Order, 2001, 18(4), pp. 313-321.

104. M. Liquiere and J. Sallantin, Structural Machine Learning with Galois Lattice and Graphs, Proc. Int. Conf Machine Learning ICML'98, 1998.

105. D. Maier, The Theory of Relational Batabases, Comput. Sci. Press, Potomac, MD, 1983.

106. H3. H. Mannila, K.J. Ràihâ, The Design of Relational Databases, Addison Wesley, 1992.

107. C. Mellish, The Description Identification Problem, Artificial Intelligence 52, 151-167, 1991.

108. R.S. Michalski and R.E. Stepp, Learning from Observation: Conceptual Clustering. In: R. S. Michalski, J. G. Carbonell, and T. M. Mitchell (eds.). Machine Learning: an Artificial Intelligence Approach Tioga, Palo Alto, California, 41-81, 1983.

109. R.S. Michalski, Theory and Methodology of Inductive Learning, Artif. Intel., 1983, vol. 20, no. 2.

110. T. Mitchell, Version Space: An Approach to Concept Learning, PhD thesis, Stanford University, 1978.

111. T. Mitchell, Generalization as Search, Artificial Intelligence 18, no. 2, 1982.

112. T. Mitchell, Machine Learning, Mc Graw Hill, 1997.

113. M.L. Mugnier, On Generalization/Specialization for Conceptual Graphs, J. of Experimental and Theoretical Artificial Intelligence, 7, pp. 325-344, 1995.

114. M.-L. Mugnier and M. Chein, Représenter des connaissances et raisonner avec des graphes. Revue d'Intelligence Artificielle, 10(1), 1996, pp. 7-56.

115. M.-L. Mugnier, Knowledge Representation and Reasonings Based on Graph Homomorphisms, in Proc. 8th Int. Conf. on Conceptual Structures, ICCS'2000, G. Mineau and B. Canter, Eds., Lecture Notes in Artificial Intelligence, 1867, 2000, pp. 172-192.

116. E. M. Norris, An algorithm for computing the maximal rectangles in a binary relation, Rev. Roum. de Math. Pures Appliquées, 23, No. 2, 243-250 (1978).

117. C. H. Papadimitriou and M. Yannakakis, The Complexity of Facets (and Some Facets of Complexity), J. Comp. Sys. ScL, 28, pp.244-259, 1984.

118. N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, Efficient Minining of Association Rules Based Using Closed Itemset Lattices, J. Inf. Systems, 24, 1999, pp. 25-46.

119. C D . Plotkin, A Note on Inductive Generalization, in Machine Intelligence, 1970, no. 3, pp. 153-163.

120. G.D. Plotkin, A Further Note on Inductive Generalization, in Machine Intelligence, 1971, no. 6, pp. 101-124.

121. S. Prediger, Simple Concept Graphs: A Logic Approach, in Proc. 6th Int. Conf on Conceptual Structures, ICCS'98, M. -L.Mugnier, M. Chein, Eds., Lecture Notes in Artificial Intelligence, 1453, 1998, pp. 225-239.

122. E. Prisner, Bicliques in Graphs I: Bounds on Their Number, Combinatorica 20(1), 2000, pp. 109-117.

123. P. Pudlak and F. Springsteel, Complexity in mechanized hypothesis formation, Theor. Comp. Sei, 8, No. 2, 203-225 (1979).

124. M.R. Quilllian, Semantic Memory, in Semantic Information Processing, M. Minsky, ed., MIT Press, Cambridge, Mass., 1968, p.227-270.

125. J.R. Quinlan, Induction on Decision Trees, Mach. Learn., 1, No. 1, 81-106 (1986).

126. J. Schmidt, Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Menge, Arch. Math., 7, No.4, 241-249 (1956).

127. D. Schutt, Abschätzungen für die Anzahl der Begriffe von Kontexten, Diplomarbeit TH Darmstadt, Darmstadt, 1988.

128. M. Skorsky, Endliche Verbände Biagramme und Eigenschaften, Dissertation, TH Darmstadt, 1992, Shaker Verlag.

129. E.N. Smirnov and P.J. Braspenning, Version Space Learning with Instance-Based Boundary Sets, in H. Prade, ed., Proceedings of the 13th European Conference on Artificial Intelligence, J. Wiley Chichester, 460-464, 1998.

130. R.J. Solomonoff, A formal theory of inductive inference // Information and Control, 1964, 7, pp. 1-22, 224-254.

131. J. F. Sowa, Conceptual Structures Information Processing in Mind and Machine, Reading, M.A.: Addison-Wesley, 1984.

132. L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, 8, No. 2, 189-201 (1979).

133. L. G. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM J. Comput, 8, no. 3, 410-421, 1979.

134. L.G. Valiant, A theory of the learnable // Commun. ACM, 1984, 27, no 11, pp. 1134-1142.

135. M. Wild, Implicational bases for finite closure systems. In: Arbeitstagung, Begriffsanalyse und Künstliche Intelligenz (W. Lex, ed.), 147-169, (1991).

136. R. Wille, Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts, In: Ordered Sets (I. Rival, ed.), Reidel, Dordrecht-Boston, 445-470, 1982.

137. R. Wille, Concept lattices and conceptual knowledge systems, Comput. Math. AppL, 23, No. 6-9, 493-515 (1992).