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

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

Обучающая выборка Образ 1
Стандартная модель данных для - student2.ru Проверочная выборка Образ 1
Обучающая выборка Образ 2
Проверочная выборка Образ 2
 
Стандартная модель данных для - student2.ru Контрольная выборка Образ 1
Образ 2

Стандартная модель данных для - student2.ru

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

образу

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

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

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

История:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

задачи.

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

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

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

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

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

Стандартная модель данных для - student2.ru

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

Стандартная модель данных для - student2.ru

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

Стандартная модель данных для - student2.ru Стандартная модель данных для - student2.ru

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

Стандартная модель данных для - student2.ru

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

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

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

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

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

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

задачи:

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

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

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

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

Стандартная модель данных для - student2.ru 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. Задача обучения с учителем. Стандартная модель данных РО для ДА. Обучающая, проверочная и контрольная выборка. Блок схема

Стандартная модель данных для - student2.ru

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

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

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

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

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

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

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

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

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

Стандартная модель данных для - student2.ru Обучающая выборка Образ 1 ρ об=100%
Проверочная выборка Образ 1 ρ пр<100%
Обучающая выборка Образ 2 ρ об=100%
Проверочная выборка Образ 2 ρ пр<100%
 
Стандартная модель данных для - student2.ru Контрольная выборка ρ контр<100% Образ 1
Образ 2

Стандартная модель данных для - student2.ru

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

Стандартная модель данных для - student2.ru Стандартная модель данных для - student2.ru Знает ПК и учитель, к какому

да
нет
Стандартная модель данных для - student2.ru Стандартная модель данных для - student2.ru
F(x), вычисление ошибки ρ пр: ρ пр>ρ0?    
Знает только учитель, к какому образу относятся объекты
Стандартная модель данных для - student2.ru образу относятся объекты-

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

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

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

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

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

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

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

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

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

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

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

Стандартная модель данных для - student2.ru

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

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

Стандартная модель данных для - student2.ru

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

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

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

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

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

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

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

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

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

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

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

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

Стандартная модель данных для - student2.ru Математическая модель нейрона

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

Стандартная модель данных для - student2.ru

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

функцией Стандартная модель данных для - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стандартная модель данных для - student2.ru на плоскости:

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

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

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

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

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

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

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

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

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

Стандартная модель данных для - student2.ru

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

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

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

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

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

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

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

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

Наши рекомендации