ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 511
Скачиваний: 23
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Языки представления. Язык представления служит для описания понятий, примеров и базовых знаний.
Можно выделить ряд логических языков, пригодных для этой цели:
язык логики высказываний, язык атрибутивной логики, язык хорнов- ских клауз и, наконец, языки второго порядка.
Логика высказываний. В исчислении высказываний примеры и понятия описываются с помощью конъюнкций булевых констант, кото- рые соответствуют индивидуальным свойствам (значениям атрибутов)
понятий. Иногда могут использоваться и другие логические связки,
такие как отрицания и дизъюнкции.
216
Гл. 5. Приобретение знаний и машинное обучение
С помощью таких средств легко описываются лишь простые поня- тия, что существенно ограничивает применимость методов машинного обучения для задач реального уровня сложности.
Атрибутивная логика. Основная идея атрибутивной логики со- стоит в том, что понятия и примеры характеризуются атрибутами из предварительно заданных множеств. Отличие от исчисления высказы- ваний состоит в том, что атрибуты здесь могут принимать различные значения из соответствующих множеств.
Примеры в атрибутивной логике часто представляются в виде таб- лиц, в которых каждая строка содержит описание некоторого примера,
а каждая колонка — множество значений некоторого атрибута.
Среди атрибутов могут быть булевы, численные, символьные и смешанно-значные атрибуты, а области значений атрибутов обычно ограничены базовыми знаниями.
Как язык описания, атрибутивная логика является значительно более пригодной для задач реального уровня сложности, нежели исчис- ление высказываний. По этой причине атрибутивная логика привлекла внимание разработчиков ряда методов машинного обучения, таких как алгоритм TDIDT [104] или AQ [105, 106].
Некоторые из таких алгоритмов мы рассмотрим ниже, а пока на- помним основные понятия языка хорновских клауз.
Язык клауз Хорна. Язык хорновских клауз принадлежит классу языков первого порядка.
Напомним, что клауза есть выражение вида B
1
, B
2
, ... , B
m
←
← A
1
, ... , A
n
, где B
1
, B
2
, ... , B
m суть атомарные формулы, n > 0 и m > 0. Атомарные формулы A
1
, ... , A
n суть совместные посылки кла- узы, а B
1
, B
2
, ... , B
m суть альтернативные заключения. (Множество клауз совместно, если оно истинно в одной из моделей языка.)
Если клауза содержит переменные x
1
, x
2
, ..., x k
, то она соот- ветствует формуле с квантором всеобщности: ∀x
1
, ∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
, если A
1
∧ ... ∧ A
n
).
Если n = 0, то клаузу следует интерпретировать так: ∀x
1
,
∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
). Если m = 0, то интерпретация такова:
¬∃x
1
, ¬∃x
2
, ..., ¬∃x k
(A
1
∧ ... ∧ A
n
).
Если n = m = 0, то клауза является тождественно ложным выска- зыванием и записывается .
Если клауза содержит не более одной атомарной формулы в заклю- чении, т. е. m 6 1, то клауза называется клаузой Хорна или хорновской клаузой.
Индуктивный характер обучения. Обучение концепту можно представить как поиск в пространстве описаний, при котором в каче-
5.3. Приобретение знаний из примеров
217
стве основных поисковых операторов выступают операторы обобщения
и специализации.
Обобщение применяется к множеству самых специфичных описа- ний S при появлении нового положительного примера. Отрицательный же пример может потребовать специализации множества самых общих
описаний G. Этот принцип лежит в основе семейства методов, назы- ваемых алгоритмами пространства версий и построенных на идее по- степенной редукции пространства текущих версий описания концепта.
Автор метода Митчелл [107]; более свежий трактат на эту тему можно найти у Хирша [108]. В работе [109] описан более ранний метод, при котором обучение концепту рассматривается как последовательность обобщений и специализаций одной гипотезы.
Ниже мы будем прямо или косвенно иметь дело с этими двумя операторами. К примеру, описание в терминах клауз Хорна можно обобщить, превратив константу в переменную или опустив условие.
Так, клаузу:
p(X, Y ) : −q(X, 2), r(Y , 2)
можно обобщить до p(X, Y ) : −q(X, Z), r(Y , Z)
или до p(X, Y ) : −q(X, 2).
Одна из первых попыток систематизации операторов обобщения была предпринята в [110].
Правильный подбор операторов поиска, наряду с выбором языка представления, является ключевой задачей разработчика обучающейся программы. Рассмотрим теперь некоторые вводные соображения о су- ществовании выводов в индуктивном обучении языкам.
Индукция в обучении языкам. Пусть E — конечный алфавит.
Словом ω будем называть любой элемент E
∗
, где E
∗
— множество всех последовательностей конечной длины из элементов E. Через |ω| обо- значим длину ω. Любое подмножество множества E
∗
будем называть языком в E.
Язык L называется рекурсивным, если для любого слова ω ∈ E
∗
можно эффективно вычислить отношение ω ∈ L. Семейство L язы- ков, состоящее из L
1
, L
2
, ... , называется индексированным семейством рекурсивных языков, если для каждого слова ω и языка L
i можно вычислить функцию ϕ(i, ω), такую что ϕ(i, ω) = 1, если ω ∈ L
i
, и
ϕ(i, ω) = 0 в противном случае.
Ниже всякое семейство языков будем считать индексированным.
Введем понятия полного и положительного представления языка.
218
Гл. 5. Приобретение знаний и машинное обучение
Определение 5.3.1. Полным представлением языка L называется последовательность пар hω
1
, τ
1
i, hω
2
, τ
2
i, ..., где τ
i равно 0 или 1. Иначе говоря, L = {ω|ω = ω
i
, τ = 1}, E
∗
\L = {ω|ω = ω
i
, τ = 0}.
Положительным представлением языка L называется последова- тельность слов ω
1
, ω
2
, ..., т. е.
L = {ω|ω = ω
i
},
при этом допускается повторение слов. Среди данных выделяются полные данные и положительные данные. Полные данные — данные,
как подтверждающие, так и опровергающие гипотезу, положительные данные — данные подтверждающие гипотезу.
Индексированное семейство рекурсивных языков, как правило, поз- воляет осуществлять выводы из полных данных, но не всегда позволяет осуществлять выводы из положительных данных.
Существование выводов из положительных данных.
Определение 5.3.2. Пусть Γ = L
1
, L
2
, ... — семейство языков. Ко-
нечным свидетельством
L
i называется множество T
i
, удовлетворяю- щее следующим условиям:
1) T
i
— ограниченное подмножество L
i
;
2) не существует L
j
, включающего T
i и являющегося строгим под- множеством L
i
Определение 5.3.3. Будем говорить, что семейство языков
Γ = L
1
, L
2
, ... удовлетворяет условию 1, если существует процедура,
которая для любого i перечисляет элементы конечного свидетельства
L
j
. Можно показать, что необходимым и достаточным условием суще- ствования индуктивных выводов из положительных данных в семей- стве языков Γ = L
1
, L
2
является условие 1.
Индуктивный вывод из положительных данных в семействе языков
Γ = L
1
, L
2
, ... при удовлетворении Γ условию 1 выглядит следующим образом.
Пусть s
1
, s
2
, ..., s n
— входные данные, имеющиеся на входе машины вывода. Представим их в виде S
n
= {s|s = s i
, i = 1, 2, ... , n}. В силу условия 1 машина выводов должна выдать наибольшее целое j, такое что t j
⊆ L
j
. Если j 6 n, то Γ, удовлетворяющего условию 1, не суще- ствует, то полагаем T
i
= S
n
5.3.2. Поиск.
Поиск в пространстве обобщений. Предположим, выбран неко- торый язык представления. Обучающаяся система «желает» обучиться некоторому концепту по множеству положительных и отрицательных примеров. Даже если описания основаны на атрибутивной логике,
5.3. Приобретение знаний из примеров
219
пространство всех различимых концептов оказывается чрезвычайно велико. Десять атрибутов, каждый с пятью возможными значениями,
дают 5 10
= 9 765 625 векторов. Любое подмножество таких векторов может соответствовать некоторому концепту, а это означает, что с по- мощью этих атрибутов можно определить 2 9 765 625
концептов. В более сложных языках это число растет еще быстрее, даже если размер про- странства представления может быть ограничен какими-либо базовыми знаниями.
Для того чтобы справиться со сложностными проблемами, обу- чающаяся система, главным образом, прибегает к комбинации двух мощных приемов: индукции и эвристического поиска. Последующие подразделы посвящены обсуждению соответствующих методов и ана- лизу фундаментальных принципов рассуждений, которые используются в обучающихся системах.
Полный перебор. Широко распространенной парадигмой в обуче- нии концептам является поиск в пространстве описаний, разрешенных в языке представления обучаемой системы. Методы такого поиска хорошо исследованы в искусственном интеллекте и достаточно ясны.
В общем случае, процесс поиска исследует состояния в простран- стве поиска в соответствии со следующим:
• Начальное состояние — отправная точка поиска. В машинном обучении начальные состояния часто соответствуют самым спе- цифичным описаниям концептов, т. е. положительным примерам.
• Терминальный критерий — цель, которая должна быть достигну- та. Состояния, удовлетворяющие терминальному критерию, назы- ваются конечными состояниями. В машинном обучении терми- нальным критерием может быть требование того, чтобы описанию удовлетворяли все положительные примеры и не удовлетворял не один отрицательный.
• Операторы поиска выполняют поиск от состояния к состоянию.
В машинном обучении таковыми являются, в основном, результа- ты обобщения и/или специализации описаний концептов.
• Стратегия поиска определяет, при каких условиях и к какому состоянию может быть применен оператор.
Двумя фундаментальными стратегиями систематического поиска являются поиск «сначала вглубь» и поиск «сначала вширь» (the depth-
first search and breadth-first search). Чтобы понять, в чем их суть, пред- ставим пространство всех возможных состояний как ориентированный граф, вершины которого соответствуют индивидуальным состояниям,
а ребра — операторам поиска.
При поиске «сначала вглубь» оператор применяется к начальному состоянию S
1
и происходит переход к состоянию S
2
. Если текущее
220
Гл. 5. Приобретение знаний и машинное обучение
состояние не распозналось как конечное, то оператор снова приме- няется к текущему состоянию, переводя систему в новое состояние.
Если таким образом не удается больше перейти в новое состояние,
а конечное состояние все еще не достигнуто, система откатывается
к предыдущему состоянию и пытается применить другой оператор.
Если это невозможно, система откатывается еще дальше, до тех пор пока не будет найдено состояние, к которому будет применим ка- кой-либо из операторов. Если такое состояние не находится, поиск завершается. Описанный принцип проиллюстрирован на рис. 5.1. Числа в квадратиках указывают порядок прохождения состояний.
Рис. 5.1. Поиск «сначала вглубь»
Поиск «сначала вширь» представляет собой подход, дополнитель- ный к первому. Сначала все операторы по очереди применяются к на- чальному состоянию. Затем полученные в результате состояния прове- ряются. Если некоторые из них распознаются как конечное состояние,
алгоритм останавливается. В противном случае операторы применя- ются ко всем последующим состояниям, затем опять к последующим состояниям, и так до тех пор, пока не будет выполнен терминальный критерий. Этот принцип проиллюстрирован на рис. 5.2.
Заметим, что в отличие от поиска «сначала вглубь», поиск «сначала вширь» не предполагает бэктрекинга, что слегка упрощает задачу.
С другой стороны, при поиске приходится хранить много промежу- точных состояний, а это приводит к снижению вычислительной эф- фективности системы, что особенно заметно в больших поисковых пространствах.
Эвристический поиск. Для увеличения эффективности поиска в больших поисковых пространствах используют эвристики. Задача эвристик — выбрать из имеющихся операторов такой, который макси- мально приблизит поиск к конечному состоянию. Для этого некоторая
5.3. Приобретение знаний из примеров
221
Рис. 5.2. Поиск «сначала вширь»
оценочная функция должна дать оценку каждого из достигнутых со- стояний. Предположим, что оценочная функция задана.
Алгоритм поиска «сначала лучшее»:
1. Назовем начальное состояние лучшим состоянием и пусть мно- жество текущих состояний состоит из одного этого состояния.
2. Если лучшее состояние удовлетворяет заданному терминальному критерию, конец (лучшее состояние есть решение поиска).
3. Применить к лучшему состоянию все применимые операторы, по- родив множество новых состояний, которые добавляются к мно- жеству текущих состояний.
4. Оценить все текущие состояния. Определить, какое из них —
лучшее, и перейти к шагу 2.
Этот алгоритм отличается от алгоритма «сначала вширь» тем, что он всегда работает только с самым перспективным состоянием и, тем самым, хотелось бы надеяться, ускоряет поиск. Плата за это — опас- ность попадания в локальный максимум оценочной функции.
Работу алгоритма можно продемонстрировать на следующем приме- ре [110].
Пример. Обучаемый пытается вывести описание концепта из мно- жества восьми положительных и отрицательных примеров, описанных значениями атрибутов, как показано в табл. 5.13; «(+)» означает «по- ложительный пример», а «(–)» означает «отрицательный пример». До- пустим, имеются два оператора: «специализировать текущее описание путем добавления конъюнкции» и «обобщить текущее описание путем добавления дизъюнкции».
Пусть начальное состояние — «любое описание». Применением оператора специализации (обобщение здесь не имеет смысла) будут
222
Гл. 5. Приобретение знаний и машинное обучение
Т а б л и ц а 5.13. Положительные и отрицательные примеры для обучения кон- цептам
Пример at1
at2
at3
Классификация e1
a x
n
(+)
e2
b x
n
(+)
e3
a y
n
(–)
e4
a z
n
(–)
e5
a y
m
(+)
e6
b y
n
(–)
e7
b y
m
(+)
e8
a x
m
(+)
получены следующие описания:
at1 = a; at1 = b; at2 = x; at2 = y; at2 = z; at3 = m и at3 = n.
Среди них at2 = x и at3 = m не удовлетворяют ни одному (–) и,
вероятно, получат наибольшее значение некоторой разумной оценочной функции. Предположим, что по какой-то причине более предпочти- тельным является at2 = x, которое и станет лучшим описанием.
Поскольку некоторым плюсам в таблице теперь не соответствует никакое описание, обучаемый попытается применить операторы поиска к лучшему описанию. Применение оператора специализации только ухудшает положение, так как уменьшает число описываемых поло- жительных примеров. Однако путем обобщения этого описания до at2 = x ∨ at2 = y можно увеличить число описываемых положительных примеров. Предположим, оценочная функция подтверждает, что это описание лучше, чем at2 = x.
Новое описание удовлетворяет всем положительным примерам, од- нако, с другой стороны, удовлетворяет также двум отрицательным примерам. Таким образом, на следующем шаге описание специализи- руется до at2 = x ∨ [(at2 = y) ∧ X], где X — это любой из следующих конъюнктов: at = a; at1 = b; at3 = m и at3 = n.
Среди новых состояний лучшим является at2 = x ∨ [(at2 =
= y) ∧ (at3 = m)]. Поскольку оно удовлетворяет всем положительным примерам и ни одному отрицательному, поиск завершается.
Поиск «сначала лучшее» может потребовать больших затрат памя- ти, поскольку хранит все порождаемые состояния. Более экономичным подходом является лучевой поиск, при котором в каждый момент времени хранятся только N лучших состояний.
Алгоритм «лучевого» поиска:
1. Пусть начальное состояние есть лучшее состояние.
5.3. Приобретение знаний из примеров
223 2. Если лучшее состояние удовлетворяет некоторому терминально- му критерию, конец.
3. Если число текущих состояний больше N, то оставить только N
лучших состояний и удалить все остальные.
4. Применить операторы поиска к лучшему состоянию и добавить полученные состояния к множеству текущих состояний.
5. Оценить все состояния и перейти к шагу 2.
Популярный частный случай алгоритма «лучевого» поиска задается
N = 1, — его иногда называют алгоритмом восхождения на гору.
Название призвано подчеркнуть сходство с альпинистами, которые стремятся найти кратчайший путь и всегда выбирают самые крутые маршруты.
5.3.3. Индуктивный алгоритм построения деревьев решений
(TDIDT). Здесь мы рассмотрим классический вариант top–down ин- дукции для построения деревьев решений [104]. Коротко можно ска- зать, что в его основе лежит принцип «разделяй и властвуй». Стро- ится дерево решений, рекурсивно разделяющее области пространства примеров на подобласти таким образом, что каждая вершина дерева соответствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потомки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждая такая вершина (лист)
помечается меткой, которая обозначает множество примеров, принадле- жащих соответствующей области. Каждая внутренняя вершина класса
(т. е. вершина, не обозначающая ничего, кроме самой себя) соответ- ствует какому-либо значению некоторого атрибута.
TDIDT обычно включает два шага — построение новых ветвей и редукцию, т. е. удаление ветвей. На первом шаге дерево решений строится так, чтобы в максимальной степени соответствовать обу- чающей выборке. На втором шаге этот «изоморфизм» превращается в «гомоморфизм»; так редукция дерева приводит к уменьшению числа его вершин.
Алгоритм построения новых ветвей. Пусть
S — полное множе- ство примеров.
Шаг 1. Поиск «лучшего» атрибута A
i
;
Шаг 2. Расщепление множества S на подмножества S
1
, S
2
, ..., S
n
,
так, чтобы все примеры из подмножества S
j имели одинаковые значения v ij атрибута A
i
;
Шаг 3. Для каждого множества S
j
: если все примеры в S
j принадле- жат одному и тому же классу C
k
(имеющему ту же метку класса),
то создать лист дерева решений и пометить меткой этого класса.
Иначе перейти к 1, положив S = S
j
Можно выделить ряд логических языков, пригодных для этой цели:
язык логики высказываний, язык атрибутивной логики, язык хорнов- ских клауз и, наконец, языки второго порядка.
Логика высказываний. В исчислении высказываний примеры и понятия описываются с помощью конъюнкций булевых констант, кото- рые соответствуют индивидуальным свойствам (значениям атрибутов)
понятий. Иногда могут использоваться и другие логические связки,
такие как отрицания и дизъюнкции.
216
Гл. 5. Приобретение знаний и машинное обучение
С помощью таких средств легко описываются лишь простые поня- тия, что существенно ограничивает применимость методов машинного обучения для задач реального уровня сложности.
Атрибутивная логика. Основная идея атрибутивной логики со- стоит в том, что понятия и примеры характеризуются атрибутами из предварительно заданных множеств. Отличие от исчисления высказы- ваний состоит в том, что атрибуты здесь могут принимать различные значения из соответствующих множеств.
Примеры в атрибутивной логике часто представляются в виде таб- лиц, в которых каждая строка содержит описание некоторого примера,
а каждая колонка — множество значений некоторого атрибута.
Среди атрибутов могут быть булевы, численные, символьные и смешанно-значные атрибуты, а области значений атрибутов обычно ограничены базовыми знаниями.
Как язык описания, атрибутивная логика является значительно более пригодной для задач реального уровня сложности, нежели исчис- ление высказываний. По этой причине атрибутивная логика привлекла внимание разработчиков ряда методов машинного обучения, таких как алгоритм TDIDT [104] или AQ [105, 106].
Некоторые из таких алгоритмов мы рассмотрим ниже, а пока на- помним основные понятия языка хорновских клауз.
Язык клауз Хорна. Язык хорновских клауз принадлежит классу языков первого порядка.
Напомним, что клауза есть выражение вида B
1
, B
2
, ... , B
m
←
← A
1
, ... , A
n
, где B
1
, B
2
, ... , B
m суть атомарные формулы, n > 0 и m > 0. Атомарные формулы A
1
, ... , A
n суть совместные посылки кла- узы, а B
1
, B
2
, ... , B
m суть альтернативные заключения. (Множество клауз совместно, если оно истинно в одной из моделей языка.)
Если клауза содержит переменные x
1
, x
2
, ..., x k
, то она соот- ветствует формуле с квантором всеобщности: ∀x
1
, ∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
, если A
1
∧ ... ∧ A
n
).
Если n = 0, то клаузу следует интерпретировать так: ∀x
1
,
∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
). Если m = 0, то интерпретация такова:
¬∃x
1
, ¬∃x
2
, ..., ¬∃x k
(A
1
∧ ... ∧ A
n
).
Если n = m = 0, то клауза является тождественно ложным выска- зыванием и записывается .
Если клауза содержит не более одной атомарной формулы в заклю- чении, т. е. m 6 1, то клауза называется клаузой Хорна или хорновской клаузой.
Индуктивный характер обучения. Обучение концепту можно представить как поиск в пространстве описаний, при котором в каче-
5.3. Приобретение знаний из примеров
217
стве основных поисковых операторов выступают операторы обобщения
и специализации.
Обобщение применяется к множеству самых специфичных описа- ний S при появлении нового положительного примера. Отрицательный же пример может потребовать специализации множества самых общих
описаний G. Этот принцип лежит в основе семейства методов, назы- ваемых алгоритмами пространства версий и построенных на идее по- степенной редукции пространства текущих версий описания концепта.
Автор метода Митчелл [107]; более свежий трактат на эту тему можно найти у Хирша [108]. В работе [109] описан более ранний метод, при котором обучение концепту рассматривается как последовательность обобщений и специализаций одной гипотезы.
Ниже мы будем прямо или косвенно иметь дело с этими двумя операторами. К примеру, описание в терминах клауз Хорна можно обобщить, превратив константу в переменную или опустив условие.
Так, клаузу:
p(X, Y ) : −q(X, 2), r(Y , 2)
можно обобщить до p(X, Y ) : −q(X, Z), r(Y , Z)
или до p(X, Y ) : −q(X, 2).
Одна из первых попыток систематизации операторов обобщения была предпринята в [110].
Правильный подбор операторов поиска, наряду с выбором языка представления, является ключевой задачей разработчика обучающейся программы. Рассмотрим теперь некоторые вводные соображения о су- ществовании выводов в индуктивном обучении языкам.
Индукция в обучении языкам. Пусть E — конечный алфавит.
Словом ω будем называть любой элемент E
∗
, где E
∗
— множество всех последовательностей конечной длины из элементов E. Через |ω| обо- значим длину ω. Любое подмножество множества E
∗
будем называть языком в E.
Язык L называется рекурсивным, если для любого слова ω ∈ E
∗
можно эффективно вычислить отношение ω ∈ L. Семейство L язы- ков, состоящее из L
1
, L
2
, ... , называется индексированным семейством рекурсивных языков, если для каждого слова ω и языка L
i можно вычислить функцию ϕ(i, ω), такую что ϕ(i, ω) = 1, если ω ∈ L
i
, и
ϕ(i, ω) = 0 в противном случае.
Ниже всякое семейство языков будем считать индексированным.
Введем понятия полного и положительного представления языка.
218
Гл. 5. Приобретение знаний и машинное обучение
Определение 5.3.1. Полным представлением языка L называется последовательность пар hω
1
, τ
1
i, hω
2
, τ
2
i, ..., где τ
i равно 0 или 1. Иначе говоря, L = {ω|ω = ω
i
, τ = 1}, E
∗
\L = {ω|ω = ω
i
, τ = 0}.
Положительным представлением языка L называется последова- тельность слов ω
1
, ω
2
, ..., т. е.
L = {ω|ω = ω
i
},
при этом допускается повторение слов. Среди данных выделяются полные данные и положительные данные. Полные данные — данные,
как подтверждающие, так и опровергающие гипотезу, положительные данные — данные подтверждающие гипотезу.
Индексированное семейство рекурсивных языков, как правило, поз- воляет осуществлять выводы из полных данных, но не всегда позволяет осуществлять выводы из положительных данных.
Существование выводов из положительных данных.
Определение 5.3.2. Пусть Γ = L
1
, L
2
, ... — семейство языков. Ко-
нечным свидетельством
L
i называется множество T
i
, удовлетворяю- щее следующим условиям:
1) T
i
— ограниченное подмножество L
i
;
2) не существует L
j
, включающего T
i и являющегося строгим под- множеством L
i
Определение 5.3.3. Будем говорить, что семейство языков
Γ = L
1
, L
2
, ... удовлетворяет условию 1, если существует процедура,
которая для любого i перечисляет элементы конечного свидетельства
L
j
. Можно показать, что необходимым и достаточным условием суще- ствования индуктивных выводов из положительных данных в семей- стве языков Γ = L
1
, L
2
является условие 1.
Индуктивный вывод из положительных данных в семействе языков
Γ = L
1
, L
2
, ... при удовлетворении Γ условию 1 выглядит следующим образом.
Пусть s
1
, s
2
, ..., s n
— входные данные, имеющиеся на входе машины вывода. Представим их в виде S
n
= {s|s = s i
, i = 1, 2, ... , n}. В силу условия 1 машина выводов должна выдать наибольшее целое j, такое что t j
⊆ L
j
. Если j 6 n, то Γ, удовлетворяющего условию 1, не суще- ствует, то полагаем T
i
= S
n
5.3.2. Поиск.
Поиск в пространстве обобщений. Предположим, выбран неко- торый язык представления. Обучающаяся система «желает» обучиться некоторому концепту по множеству положительных и отрицательных примеров. Даже если описания основаны на атрибутивной логике,
5.3. Приобретение знаний из примеров
219
пространство всех различимых концептов оказывается чрезвычайно велико. Десять атрибутов, каждый с пятью возможными значениями,
дают 5 10
= 9 765 625 векторов. Любое подмножество таких векторов может соответствовать некоторому концепту, а это означает, что с по- мощью этих атрибутов можно определить 2 9 765 625
концептов. В более сложных языках это число растет еще быстрее, даже если размер про- странства представления может быть ограничен какими-либо базовыми знаниями.
Для того чтобы справиться со сложностными проблемами, обу- чающаяся система, главным образом, прибегает к комбинации двух мощных приемов: индукции и эвристического поиска. Последующие подразделы посвящены обсуждению соответствующих методов и ана- лизу фундаментальных принципов рассуждений, которые используются в обучающихся системах.
Полный перебор. Широко распространенной парадигмой в обуче- нии концептам является поиск в пространстве описаний, разрешенных в языке представления обучаемой системы. Методы такого поиска хорошо исследованы в искусственном интеллекте и достаточно ясны.
В общем случае, процесс поиска исследует состояния в простран- стве поиска в соответствии со следующим:
• Начальное состояние — отправная точка поиска. В машинном обучении начальные состояния часто соответствуют самым спе- цифичным описаниям концептов, т. е. положительным примерам.
• Терминальный критерий — цель, которая должна быть достигну- та. Состояния, удовлетворяющие терминальному критерию, назы- ваются конечными состояниями. В машинном обучении терми- нальным критерием может быть требование того, чтобы описанию удовлетворяли все положительные примеры и не удовлетворял не один отрицательный.
• Операторы поиска выполняют поиск от состояния к состоянию.
В машинном обучении таковыми являются, в основном, результа- ты обобщения и/или специализации описаний концептов.
• Стратегия поиска определяет, при каких условиях и к какому состоянию может быть применен оператор.
Двумя фундаментальными стратегиями систематического поиска являются поиск «сначала вглубь» и поиск «сначала вширь» (the depth-
first search and breadth-first search). Чтобы понять, в чем их суть, пред- ставим пространство всех возможных состояний как ориентированный граф, вершины которого соответствуют индивидуальным состояниям,
а ребра — операторам поиска.
При поиске «сначала вглубь» оператор применяется к начальному состоянию S
1
и происходит переход к состоянию S
2
. Если текущее
220
Гл. 5. Приобретение знаний и машинное обучение
состояние не распозналось как конечное, то оператор снова приме- няется к текущему состоянию, переводя систему в новое состояние.
Если таким образом не удается больше перейти в новое состояние,
а конечное состояние все еще не достигнуто, система откатывается
к предыдущему состоянию и пытается применить другой оператор.
Если это невозможно, система откатывается еще дальше, до тех пор пока не будет найдено состояние, к которому будет применим ка- кой-либо из операторов. Если такое состояние не находится, поиск завершается. Описанный принцип проиллюстрирован на рис. 5.1. Числа в квадратиках указывают порядок прохождения состояний.
Рис. 5.1. Поиск «сначала вглубь»
Поиск «сначала вширь» представляет собой подход, дополнитель- ный к первому. Сначала все операторы по очереди применяются к на- чальному состоянию. Затем полученные в результате состояния прове- ряются. Если некоторые из них распознаются как конечное состояние,
алгоритм останавливается. В противном случае операторы применя- ются ко всем последующим состояниям, затем опять к последующим состояниям, и так до тех пор, пока не будет выполнен терминальный критерий. Этот принцип проиллюстрирован на рис. 5.2.
Заметим, что в отличие от поиска «сначала вглубь», поиск «сначала вширь» не предполагает бэктрекинга, что слегка упрощает задачу.
С другой стороны, при поиске приходится хранить много промежу- точных состояний, а это приводит к снижению вычислительной эф- фективности системы, что особенно заметно в больших поисковых пространствах.
Эвристический поиск. Для увеличения эффективности поиска в больших поисковых пространствах используют эвристики. Задача эвристик — выбрать из имеющихся операторов такой, который макси- мально приблизит поиск к конечному состоянию. Для этого некоторая
5.3. Приобретение знаний из примеров
221
Рис. 5.2. Поиск «сначала вширь»
оценочная функция должна дать оценку каждого из достигнутых со- стояний. Предположим, что оценочная функция задана.
Алгоритм поиска «сначала лучшее»:
1. Назовем начальное состояние лучшим состоянием и пусть мно- жество текущих состояний состоит из одного этого состояния.
2. Если лучшее состояние удовлетворяет заданному терминальному критерию, конец (лучшее состояние есть решение поиска).
3. Применить к лучшему состоянию все применимые операторы, по- родив множество новых состояний, которые добавляются к мно- жеству текущих состояний.
4. Оценить все текущие состояния. Определить, какое из них —
лучшее, и перейти к шагу 2.
Этот алгоритм отличается от алгоритма «сначала вширь» тем, что он всегда работает только с самым перспективным состоянием и, тем самым, хотелось бы надеяться, ускоряет поиск. Плата за это — опас- ность попадания в локальный максимум оценочной функции.
Работу алгоритма можно продемонстрировать на следующем приме- ре [110].
Пример. Обучаемый пытается вывести описание концепта из мно- жества восьми положительных и отрицательных примеров, описанных значениями атрибутов, как показано в табл. 5.13; «(+)» означает «по- ложительный пример», а «(–)» означает «отрицательный пример». До- пустим, имеются два оператора: «специализировать текущее описание путем добавления конъюнкции» и «обобщить текущее описание путем добавления дизъюнкции».
Пусть начальное состояние — «любое описание». Применением оператора специализации (обобщение здесь не имеет смысла) будут
222
Гл. 5. Приобретение знаний и машинное обучение
Т а б л и ц а 5.13. Положительные и отрицательные примеры для обучения кон- цептам
Пример at1
at2
at3
Классификация e1
a x
n
(+)
e2
b x
n
(+)
e3
a y
n
(–)
e4
a z
n
(–)
e5
a y
m
(+)
e6
b y
n
(–)
e7
b y
m
(+)
e8
a x
m
(+)
получены следующие описания:
at1 = a; at1 = b; at2 = x; at2 = y; at2 = z; at3 = m и at3 = n.
Среди них at2 = x и at3 = m не удовлетворяют ни одному (–) и,
вероятно, получат наибольшее значение некоторой разумной оценочной функции. Предположим, что по какой-то причине более предпочти- тельным является at2 = x, которое и станет лучшим описанием.
Поскольку некоторым плюсам в таблице теперь не соответствует никакое описание, обучаемый попытается применить операторы поиска к лучшему описанию. Применение оператора специализации только ухудшает положение, так как уменьшает число описываемых поло- жительных примеров. Однако путем обобщения этого описания до at2 = x ∨ at2 = y можно увеличить число описываемых положительных примеров. Предположим, оценочная функция подтверждает, что это описание лучше, чем at2 = x.
Новое описание удовлетворяет всем положительным примерам, од- нако, с другой стороны, удовлетворяет также двум отрицательным примерам. Таким образом, на следующем шаге описание специализи- руется до at2 = x ∨ [(at2 = y) ∧ X], где X — это любой из следующих конъюнктов: at = a; at1 = b; at3 = m и at3 = n.
Среди новых состояний лучшим является at2 = x ∨ [(at2 =
= y) ∧ (at3 = m)]. Поскольку оно удовлетворяет всем положительным примерам и ни одному отрицательному, поиск завершается.
Поиск «сначала лучшее» может потребовать больших затрат памя- ти, поскольку хранит все порождаемые состояния. Более экономичным подходом является лучевой поиск, при котором в каждый момент времени хранятся только N лучших состояний.
Алгоритм «лучевого» поиска:
1. Пусть начальное состояние есть лучшее состояние.
5.3. Приобретение знаний из примеров
223 2. Если лучшее состояние удовлетворяет некоторому терминально- му критерию, конец.
3. Если число текущих состояний больше N, то оставить только N
лучших состояний и удалить все остальные.
4. Применить операторы поиска к лучшему состоянию и добавить полученные состояния к множеству текущих состояний.
5. Оценить все состояния и перейти к шагу 2.
Популярный частный случай алгоритма «лучевого» поиска задается
N = 1, — его иногда называют алгоритмом восхождения на гору.
Название призвано подчеркнуть сходство с альпинистами, которые стремятся найти кратчайший путь и всегда выбирают самые крутые маршруты.
5.3.3. Индуктивный алгоритм построения деревьев решений
(TDIDT). Здесь мы рассмотрим классический вариант top–down ин- дукции для построения деревьев решений [104]. Коротко можно ска- зать, что в его основе лежит принцип «разделяй и властвуй». Стро- ится дерево решений, рекурсивно разделяющее области пространства примеров на подобласти таким образом, что каждая вершина дерева соответствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потомки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждая такая вершина (лист)
помечается меткой, которая обозначает множество примеров, принадле- жащих соответствующей области. Каждая внутренняя вершина класса
(т. е. вершина, не обозначающая ничего, кроме самой себя) соответ- ствует какому-либо значению некоторого атрибута.
TDIDT обычно включает два шага — построение новых ветвей и редукцию, т. е. удаление ветвей. На первом шаге дерево решений строится так, чтобы в максимальной степени соответствовать обу- чающей выборке. На втором шаге этот «изоморфизм» превращается в «гомоморфизм»; так редукция дерева приводит к уменьшению числа его вершин.
Алгоритм построения новых ветвей. Пусть
S — полное множе- ство примеров.
Шаг 1. Поиск «лучшего» атрибута A
i
;
Шаг 2. Расщепление множества S на подмножества S
1
, S
2
, ..., S
n
,
так, чтобы все примеры из подмножества S
j имели одинаковые значения v ij атрибута A
i
;
Шаг 3. Для каждого множества S
j
: если все примеры в S
j принадле- жат одному и тому же классу C
k
(имеющему ту же метку класса),
то создать лист дерева решений и пометить меткой этого класса.
Иначе перейти к 1, положив S = S
j