 |
По теме 4 изучаются лекции 11-14. Выполняются практические задания, представленные в отдельных файлах. После изучения темы выполняется Тест 2.
|
|
|
|
По теме 4 изучаются лекции 11-14. Выполняются практические задания, представленные в отдельных файлах. После изучения темы выполняется Тест 2.
Лекция 11. Индуктивный вывод и обобщение. Задача машинного обучения
1. Индуктивный вывод. Объекты обобщения. Описание набором признаков.
2. Классификация задач машинного обучения
3. Алгоритмы обучения «без учителя»: метод потенциалов, MAXMIN, метод к средних.
Человек, решающий задачу выбора целесообразного поведения в той или иной ситуации, прежде всего анализирует ситуацию с точки зрения существенных и несущественных обстоятельств, влияющих на принимаемое решение. Процесс выделения существенных для данной задачи обстоятельств можно представить как разбиение входных ситуаций на классы, обладающие тем свойством, что все ситуации из одного класса требуют одних и тех же действий. Оценка входной ситуации человеком происходит на основе совокупности сигналов, поступающих от его органов чувств. На основании этих сигналов мозг вырабатывает команды, которые обеспечивают реакцию человека на ситуацию. Сигналы поступают от рецепторов (зрительных, тактильных и т. п. ); совокупность таких сигналов формирует представление человека о ситуации.
Вычислительная машина, на которой моделируется аналогичный процесс, должна обладать возможностью получать описание входной ситуации от внешних «рецепторов», в виде различных наборов данных. Очевидно, объем информации, который получает компьютер, неизмеримо меньше объемов информации, с которыми имеет дело человек; кроме того такая информация будет представлена исключительно в численной форме. Для того, чтобы эффективно оценить, относятся ли различные ситуации к одному классу, или, по-другому, к понятию, интеллектуальная система должна иметь возможность рассмотреть и оценить ряд конкретных примеров таких ситуаций, включенных в обучающее множество.
|
|
|
Обучение на основе примеров является типичным случаем индуктивного обучения и широко используется в системах искусственного интеллекта (машинное обучение). На основе предъявленных примеров (и, возможно, контрпримеров) интеллектуальная система должна сформировать общее понятие, охватывающее примеры и исключающее контрпримеры. Источником примеров, на которых осуществляется обучение, может быть учитель – то есть лицо, которое заранее знает концепцию строящегося понятия, и подбирает наиболее удачные обучающие выборки. Источником примеров для обучения может быть внешняя среда, с которой взаимодействует интеллектуальная система. В этом случае обучающие выборки формируются случайным образом, в зависимости от внешних факторов. Обучение на таких выборках существенно сложнее. Наконец, источником примеров для обучения может стать сама интеллектуальная система. Например, в случае взаимодействия интеллектуального робота с внешней средой действия самого робота могут привести к созданию обучающей выборки, то есть образуется множество сходных ситуаций с известными результатами, которые можно затем обобщить.
Если обучающие выборки содержат только положительные примеры формируемого понятия, обучение на таких примерах может привести к построению чрезмерно общих индуктивных понятий. Такие понятия смогут охватить все предъявленные примеры, но бесполезно с их помощью пытаться различить два близких объекта, принадлежащих на самом деле разным классам. Гораздо эффективнее использовать для обучения множество, содержащее как положительные, так и отрицательные примеры некоторого понятия. При этом снижается риск получения чрезмерно общих индуктивных описаний.
|
|
|
Для системы машинного обучения принципиально важным является вопрос, что же поступает на вход системы, в каком виде предъявляются примеры понятия, включенные в состав обучающего множества. Все рассмотренные ниже методы решения задач индуктивного построения понятий базируются на концепции признакового описания примера понятия: любой элемент обучающей выборки, который может быть представлен в системе, полностью определяется набором свойств, или признаков; такое задание объекта исследования называется признаковым описанием объекта. В исследовании не рассматривается случай, когда необходимо сгруппировать по классам объекты, характерной чертой которых является наличие структуры: примером таких объектов могут быть химические соединения, кристаллические решетки, графы и т. п. Также мы не будем рассматривать случай, когда описание объектов классификации задано в виде формул исчисления предикатов первого порядка (описание ситуаций, семантических сетей, и т. п. ). Подобные модели описания объектов крайне интересны, но их рассмотрение выходит за рамки данной книги.
Традиционно объекты, рассматриваемые в рамках интеллектуальной системы, задаются в виде набора признаков. Описания различных объектов отличаются значениями признаков. Под обобщением обычно понимается переход от рассмотрения единичного объекта о или некоторой совокупности объектов О к рассмотрению обобщенного понятия D, которое:
а) отображает характерные для этого множества логические отношения между значениями признаков,
б) является достаточным для разделения объектов, принадлежащих множеству, и объектов, ему не принадлежащих с помощью некоторого правила распознавания.
Для описания объекта будем использовать признаки А1, А2, …, Аn. Каждый объект о Î О характеризуется набором конкретных значений этих признаков (атрибутов) о ={a1, a2, …, an}, где ai- значение i-го признака. Такое описание объекта называют признаковым описанием; признаками могут служить цвет, размер, форма, скорость, вес, цена и т. п. Обозначим через DOM(Ai) множество допустимых значений i-го признака: aiÎ DOM(Ai).
|
|
|
Формирование понятий по сути является процессом выделения закономерностей, свойственных множествам объектов.
Виды признаков.
Основой для работы любой системы индуктивного формирования понятий является множество векторов признаков, описывающих объекты. Входной вектор Х содержит компоненты xi, называемые далее признаками, или атрибутами объекта. Значения, которые могут принимать признаки объекта, относятся к трем основным типам: количественные, или числовые, качественные и шкалированные. То, какие значения принимают признаки, может оказать большое влияние на процесс обобщения.
В случае числовых признаков на множестве значений признаков может быть введена метрика, позволяющая дать количественную оценку значения признака. Это значит, что различные значения признаков можно сравнивать между собой в количественном плане. Часто такие значения являются результатом измерений физических величин, таких, как длина, вес, температура и т. п.
В случае, если признаки могут иметь качественный характер, но при этом их значения можно упорядочить друг относительно друга, говорят, что такие значения образуют ранговую или порядковую шкалу. Примерами таких шкал порядка могут быть ряды типа {большой, средний, маленький} или {горячий, теплый, холодный}. С помощью таких шкал порядка можно судить, какой из двух объектов является наилучшим, но нельзя оценить, сколь близки или далеки эти объекты по некоторому критерию.
Третий случай заключается в том, что значения признаков имеют чисто качественный характер, связать эти значения между собой не удаётся. Примерами таких значений могут быть цвет ={красный, желтый, зеленый} или материал = {стекло, дерево, пластмасса, железо}.
Рассмотрим пример задания обучающей выборки с разными типами признаков. Ниже представлена выборка описаний состояний нескольких больных, страдающих некоторым заболеванием, а также состояний людей, не страдающих этим заболеванием.
Пример обучающей выборки Т а б л и ц а. 1
|
|
|
Выборка K 
:
| Возраст | Пол | Стадия болезни | Что болит | Температура | Прочие ощущения | |
| Пожилой | Жен. | Средн. | Голова | 36, 6 | Озноб | |
| Пожилой | Муж. | Средн. | Голова | 36, 4 | Озноб | |
| Пожилой | Муж. | Поздн. | Голова | 36, 7 | Озноб | |
| Средний | Жен. | Начал. | Голова | 37, 8 | Никаких | |
| Пожилой | Жен. | Начал. | Нет | 38, 0 | Нет аппетита | |
| Пожилой | Муж. | Начал. | Спина | 36, 3 | Нет аппетита | |
| Пожилой | Муж. | Начал. | Нет | 36, 6 | Нет аппетита | |
| Пожилой | Муж. | Начал. | Голова | 38, 2 | Озноб |
Выборка K 
:
| Возраст | Пол | Стадия болезни | Что болит | Температура | Прочие ощущения | |
| Молодой | Муж. | - | Нет | 36, 6 | Никаких | |
| Средний | Жен. | Средн. | Живот | 37, 7 | Тошнота | |
| Пожилой | Жен. | Начал. | Руки | 36, 7 | Никаких | |
| Пожилой | Муж. | Поздн. | Ноги | 36, 4 | Нет аппетита |
Каждая строка в таблице соответствует одному объекту классификации. Любой объект характеризуется семью признаками, среди которых есть количественные (температура), качественные (пол, что болит) и шкалированные (например, возраст). Выборки такого типа являются исходными данными для алгоритмов распознавания и классификации.
Признаки, характеризующие объект, можно рассматривать как детерминированные и вероятностные. Детерминированными признаками будем называть признаки, принимающие конкретные числовые значения. Достаточно часто для определения близости двух объектов используют значения признаков, не совпадающие с действительными, а предварительно подвергают эти значения масштабированию.
Приближенные, (размытые) признаки характерны тем, что при измерении значения такого признака возможны погрешности, то есть нельзя с уверенностью сказать, каково значение признака. Для приближенных признаков в качестве меры близости может быть использован риск, связанный с решением о принадлежности объекта классу.
Рассмотрим подробнее различные подходы к решению задачи об отнесении объекта к некоторому классу.
Самым простым вариантом системы, решающей задачу распознавания, являются системы без обучения. В таких системах заранее известны классы, к которым могут относиться предъявляемые объекты, а также критерии отнесения объекта к классу. Примером такой системы может служить система автоматического контроля качества деталей. Предположим, что деталь характеризуется двумя признаками: это длина и диаметр. Существует два класса деталей - годные и бракованные. Деталь считается годной, если ее параметры удовлетворяют условиям: длина =100±5 мм,
диаметр = 8±0, 5 мм. Таким образом, нам известны как сами классы, так и критерии отнесения предъявленной детали к каждому из классов.
|
|
|
Более сложными являются системы с обучением. В системах с обучением не задан алгоритм разделения предъявляемых объектов на классы. Процесс создания и оптимизации такого алгоритма и называется обучением. Для обучения используется определенный набор объектов, называемый далее обучающим множеством или обучающей выборкой. Мы ставим цель рассмотреть прежде всего системы с обучением.
В системах с обучением структура алгоритмов, классифицирующих объекты, тесно связана с видом информации, представленной в обучающей выборке. Будут рассмотрены два варианта. В первом случае исходная информация, на основании которой создаётся искомый алгоритм, представлена в виде обучающего множества, не разделенного на классы. Это значит, что для объектов обучающего множества не задано, к каким классам они принадлежат. Таким образом, заранее неизвестны не только характеристики классов, но и их количество. Задача обучения сводится к разделению объектов выборки на группы объектов, " сходных" друг с другом (классы). Процесс построения алгоритма, разделяющего затем объекты по степени их сходства, называется обучением " без учителя". Примером задач такого типа могут быть задачи классификации растений, химических соединений, обработка статистических исследований и т. п.
В другом случае исходная информация представлена в виде множества объектов, для каждого из которых известно, к какому из классов он отнесён. При этом нам неизвестны критерии отнесения объектов к какому-либо классу. В случае, если в выборку вошли не все примеры классов, можно считать, что число классов также неизвестно. Здесь задача обучения состоит в построении алгоритма, позволяющего отнести предъявленный объект к одному из известных классов. Процесс построения такого алгоритма назовем управляемым обучением, или обучением " с учителем". Будем считать, что алгоритм распознавания построен правильно, если для любого объекта из обучающей выборки он даёт правильный результат.
Частным случаем алгоритмов обучения с учителем является задача формирования единственного обобщенного понятия на основе предъявленного множества примеров и контрпримеров данного понятия. Действительно, если объекты обучающей выборки относятся к классам К1, К2, …Кn, мы можем рассмотреть отдельно задачу построения алгоритма распознавания для класса Кi, считая при этом объекты, принадлежащие классам К1, …Ki-1, Ki+1, …, Kn - контрпримерами.
|
|
|
