Стандартная модель данных для

Задачи обучения с учителем

Обучающая выборка Образ 1

Проверочная выборка Образ 1

Обучающая выборка Образ 2

Проверочная выборка Образ 2

Контрольная выборка Образ 1

Образ 2

Знает блок проверка и учителем к какому образу отклоняется объект

Знает ПК и учитель к какому

образу

Знает только учитель, к какому образу относятся объекты

Относятся объекты?

 

 

. История искусственного интеллекта. Проект машин пятого поколения и его результаты. Шкала оценки задач ИИ.

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

История:

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

Начало 60-х — это эпоха эвристического программирования. Предпринимались попытки отыскать общие методы решения широкого класса задач.

В 1963-70 гг. к решению задач стали подключать методы математической логики. Робинсон разработал метод резолюций, который позволяет автоматически доказывать теоремы при наличии набора исходных аксиом.

Конец 70-х годов - создание экспертных систем (ЭС). Япония объявляет о начале проекта машин V поколения, основанных на знаниях.

В 80-х годах появились первые коммерческие программные продукты. В это время стала развиваться область машинного обучения.

Проект машин пятого поколения и его результаты.

Создан в 80-е годы. Япония объявила о начале проекта машин V поколения, основанных на знаниях. Проект был рассчитан на десять лет и объединял лучших молодых специалистов крупнейших японских компьютерных корпораций.

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

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

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

Шкала оценки задач ИИ: до 60% - неуд., 60 – 75% - уд., 75 – 95% -хор., от 95% - отл.

2. Основные направления исследования в области искусственного интеллекта. Задачи искусственного интеллекта и их характерные признаки.

Направления:

· Экспертные системы, базы знаний.

· Языки программирования систем ИИ.

· Машинный перевод.

· Интеллектуальные роботы.

· Распознавание образов.

· Игры и машинное творчество

· Анализ изображений, синтез речи

· Нечёткая логика

· Нейронные сети

задачи.

o Создание полного научного описания интеллекта человека.

o Задачи, алгоритм нахождения которых неизвестен. Любую задачу можно решить методами ИИ, но есть недостаток: некоторая % вероятность.

Характерные признаки.

3. Метод черного ящика. Его применение к задачам ИИ

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

для распознавания образов:

для нейронных сетей:

для экспертных систем:

4. Основные задачи РО. Образ, объект.

Распознавание образов – это раздел искусственного интеллекта, целью которого является классификация объектов по нескольким категориям или классам.

определения:

· Образ (класс) - это множество всех объектов (либо явлений, процессов, ситуаций), сходных между собой(сгруппированных) в некотором фиксированном отношении.

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

· Объект – n-мерный вектор. Координаты вектора – признаки. Признаки считаем независимыми.

задачи:

Задача распознавания образов состоит в том, чтобы отнести новый распознаваемый объект к какому-либо классу (образу).

1. Задача обучения без учителя(TA - таксономия)

2. Задача обучения с учителем(DA – дискриминантный анализ)

3. Задача информативности – поиск существенных признаков

5. Задача обучения без учителя. Подготовка информации для задачи таксономии, определение образов таксономии.

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

· Образ – сгущение(таксон).

Входные данные:

· Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми.

· Матрица расстояний. Каждый объект описывается расстояниями до всех остальных объектов.

Определение образов:

Ro – начальное расстояние

Если |Xi-Xj|<Ro => r<Ro => объекты одного образа.

6. Модели и алгоритмы таксономии. Таксон

Таксон (кластер) – образ таксономии. Образ является сгущением. Состоит из дискретных объектов, объединяемых на основании общих свойств и признаков.

Есть 2 основных метода таксономии(кластеризации): декомпозиция (разделение, k-кластеризация) и иерархическая кластеризация.

В основном, алгоритмы метода k - кластеризации берут на вход множество S и число k. И на выход отдают разделение множества S на подмножества S1, S2,..., Sk.

1)Выбираем k произвольных попарно несовпадающих векторов и назначаем их центрами кластеров (центроидами).

2) Поиск ближайших соседей. Для каждого вектора из обучающего множества находим ближайший центроид.

3. Уточнение положений центроидов.

4. Проверка условия окончания итераций.

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

Алгоритмы:

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

Forel-2: эта модификация исходного алгоритма используется в случае, когда нужно получить в точности t-таксонов. Один из эвристических приемов для учета неустойчивых таксонов реализован в алгоритме SKAT. Алгоритм KOLLAPS применяется в задачах выделения локальных сгустков точек из фона.Алгоритм BIGFOR решает проблему работы с очень большими массивами точек.

7. Задача обучения с учителем. Стандартная модель данных РО для ДА. Обучающая, проверочная и контрольная выборка. Блок схема

Задача распознавания на основе имеющегося множества прецедентов называется классификацией с обучением (или с учителем).

Известны A*, B*: A* принадлежит A, B* принадлежит B.

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

Предполагаем, что с одной стороны от F – множество A, с другой - множество B.

Распознавание неизвестных объектов z:

если F(z)>0, => z принадлежит A,

F(z)<0, => z принадлежит B.

Стандартная модель данных РО для ДА

Таблица, в строках – объекты.

Обучающая выборка Образ 1 ρ об=100%

Проверочная выборка Образ 1 ρ пр<100%

Обучающая выборка Образ 2 ρ об=100%

Проверочная выборка Образ 2 ρ пр<100%

Контрольная выборка ρ контр<100% Образ 1

Образ 2

	Построение решающего правила F(x) ρ=100% об=100%

 

 

Знает ПК и учитель, к какому

да

нет

F(x), вычисление ошибки ρ пр: ρ пр>ρ0?

Знает только учитель, к какому образу относятся объекты

образу относятся объекты-

обучающая выборка, знает

только учитель –проверочная

 

	блок распознавания

 

 

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

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

· Контрольная выборка – набор объектов с неизвестными классами(для ПК). Для оценки качества решающего правила.

 

8. Задача информативности. Оценка размера информативного пространства для данной выборки. Теорема Вапника. Блок схема СПА и информативность независимых признаков. Оценка качества.

 

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

 

Оценка размера информативного пространства для данной выборки – поиск количества существенных признаков (Найти миниум информативного пространства).

СПА - алгоритм выбора информативной подсистемы признаков на основе известного метода случайного поиска с адаптацией.

Критерий качества ρ0 задаём в начале решения задачи.

Вес признака – частота появления в подсистемах. Если вес >=0,5 - признак информативный(существенный).

 

Теорема Вапника(следствие).

 

k – коэффициент, задаётся на входе(напр., k=3 для медицинских задач, k=10 для военных).

Если эта теорема не выполняется при решении задачи, результаты могут быть любыми.

 

Оценка качества:

Применяем 1 признак к проверочной выборке(для малого количества информации); сортируем объекты по классам; подсчитываем количество правильно распознанных объектов/ общее количество объектов - ρ к.

 

9. Задача информативности в РО. Информативные признаки

 

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

 

Оценка размера информативного пространства для данной выборки – поиск количества существенных признаков (Найти миниум информативного пространства).

СПА - алгоритм выбора информативной подсистемы признаков на основе известного метода случайного поиска с адаптацией.

Вес признака – частота появления в подсистемах. Если вес >=0,5 - признак информативный(существенный).

 

10. Математические модели задач распознавания образов.

Построение линейных решающих правил.

Теорема Новикова. Теорема Мазурова об однородных комитетах.

 

Математическая модель нейрона

В алгоритме персептрона в основу положен принцип действия нейрона. Здесь х1,х2..хi – компоненты вектора признаков, Wi – веса, F – функция активации, W0 – порог. Значение функции активации вычисляется на основе определения знака суммы

Таким образом, нейрон представляет собой линейный классификатор с дискриминантной

функцией .

Тогда задача построения линейного классификатора для заданного множества

прецедентов сводится к задаче обучения нейрона, т.е. подбора соответствующих весов

и порога. Обучение состоит в коррекции весов и порога.

Алгоритм персептрона

Алгоритм персептрона представляет собой последовательную итерационную процедуру.

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

 

Задача построения линейной разделяющей гиперповерхности(линейного решающего правила)

Главным достоинством линейного классификатора является его простота и вычислительная эффективность. Рассмотрим линейную дискриминантную функцию:

· Определение. Множество, содержащее отрезок, соединяющий две произвольные

внутренние точки, называется выпуклым.

· Определение. Выпуклая оболочка – это минимальное выпуклое множество.

· Утверждение. Два множества на плоскости линейно разделимы тогда и только

тогда, когда их выпуклые оболочки не пересекаются.

Из этого утверждения получаем следующее правило проверки разделимости множеств

на плоскости:

1) Построить выпуклые оболочки.

2) Проверить пересечение выпуклых оболочек.

Если они не пересекаются, то множества разделимы.

3) Найти ближайшую пару точек в выпуклых оболочках обоих множеств.

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

 

 

Теорема Новикова: для любой обучающей непротиворечивой непересекающейся выборки(A* Ụ B*) можно построить линейную функцию(решающее правило) за конечное время с качеством распознавания 100%. A* и B* - выпуклые непустые множества, A* принадлежит A, B* принадлежит B.

 

Однородный комитет - нечетная (по количеству) совокупность параллельных n- мерных плоскостей.

Теорема Мазурова: для любой обучающей непротиворечивой выборки(A* Ụ B*) можно построить однородный комитет за конечное время, ρ об=ρ0 заданное. A* и B* - непустые множества, A* принадлежит A, B* принадлежит B.

 

11. Задача обучения с учителем. Модели и алгоритмы дискриминантного анализа. Метод потенциальных функций. Метод комитетов. Примеры. Основные теоремы.

Задача распознавания на основе имеющегося множества прецедентов называется классификацией с обучением (или с учителем).

Известны A*, B*: A* принадлежит A, B* принадлежит B.

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

Предполагаем, что с одной стороны от F – множество A, с другой -множество B.

Распознавание неизвестных объектов z:

если F(z)>0, => z принадлежит A,

F(z)<0, => z принадлежит B.

 

Модели и алгоритмы дискриминантного анализа