PDF-лекции, страница 10

в нем встретилось незнакомое ИС слово;- не удается продолжить планирование решения, т.к. ни один оператор к очередной вершине деревапоиска неприменим;- новый факт формально противоречит одному из ранее известных.Разрешение конфликта:- поиск возможных причин (незнакомое слово – это либо действительно новое слово, либо слово сорфографической ошибкой);- их динамическое (в текущем С-сеансе) упорядочение;- выбор наилучшего способа устранения конфликта;- необходимая коррекция С-знаний (С-адаптация) или изменение входных данных (исправлениеорфографической ошибки);- С-обучение (факультативно), например, запись в словарь системы нового слова.Принцип полноты базовых знаний.

Возможность/невозможность «обучения с нуля».Проблемы полноты и репрезентативности обучающей выборки (при пополнении С-знаний).День 8.Обучение, обучающие выборкиОбучение (в психологии) – усвоение новых знаний.Новые умения и навыки приобретаются путем тренировки и упражнения.Обучение (в работах по ИИ): «любое изменение в системе, приводящее к улучшению решения задачи приее повторном предъявлении или к решению другой задачи на основе тех же данных» - Н.Саймон.Некоторые важные терминыГенеральная совокупность – вся изучаемая выборочным методом статистическая совокупностьобъектов и/или явлений общественной жизни, имеющих общие качественные признаки иликоличественные переменныеВыборка (выборочная совокупность) – часть объектов из генеральной совокупности, отобранных дляизучения, с тем чтобы сделать заключение о всей генеральной совокупности.

Для того, чтобызаключение, полученное путем изучения выборки, можно было распространить на всю генеральнуюсовокупность выборка должна обладать свойством репрезентативности.Репрезентативность (представительность) – свойство выборки отражать характеристики изучаемойгенеральной совокупности.Репрезентативная выборка – выборка, имеющая такое же распределение относительныххарактеристик, что и генеральная совокупность.Ошибки выборки – отклонение статистической структуры выборки от структуры соответствующейгенеральной совокупности.Произвольная выборка – эмпирическая выборка, не имеющая вероятностного обоснования,складывающаяся на основе случая, причем выбор каждого случая не влияет на любой другой случай.33Источник – www.glossary.ru.Символьное обучение (обучение в ПРОСТРАНСТВЕ ПОНЯТИЙ)Основные операции в пространстве понятий: обобщение, специализация.Индуктивное обучение как поиск в пространстве понятийПример:Пусть в пространство понятий входит некоторое абстрактное понятие:Object (Sizes, Colors, Shapes)и известно, что его признаки принимают такие значения:Sizes = {large, small}; Colors = {red, blue, white, green}; Shapes = {round, polygon}Индуктивное обучение в этом пространстве – поиск понятия, удовлетворяющего всем примерамобучающей выборки.Пусть, далее, у нас есть единственный обучающий пример – Object1 (small, red, round).Результатом обучения может стать пополнение пространства понятий таким новым частным случаем(«маленький красный шар»/«маленький красный мяч» и т.п.).

Это – специализация.Пусть появляется второй обучающий пример – Object2 (large, red, round).Результатом обучения может стать пополнение пространства понятий этим новым частным случаем(«большой красный шар»/«большой красный мяч» и т.п.). Это тоже – специализация.Можно выполнить и некоторые операции обобщения, построив и добавив в общее пространство новыепонятия:Object3 (X, red, round)– («красный шар»/«красный мяч» и т.п.)Object4 (X, Y, round)– («шар»/«мяч» и т.п.)Основные операции обобщения1.Замена конкретного значения понятия на переменную:ball (α, red, β) → ball (α, X, β)(«красный мяч любого размера и любой формы») → (« мяч любого цвета, любого размера илюбой формы»).2.Исключение конъюнкта:Sizes (X, small) & Colors (X, red) & Shapes (X, cube) → Colors (X, red) & Shapes (X, cube)(«красный куб малого размера») → («красный куб»)3.Добавление дизъюнкта:Colors (X, red) & Shapes (X, cube) → Colors (X, red) & (Shapes (X, cube) V Shapes (X,pyramid))(«красный куб») → («красный куб или красная пирамида»)4.Замена конкретного объекта или частного понятия общим понятием (на основе иерархии классов):Colors (X, red) → Colors (X, rainbow-color) («красный» → «цвета радуги»)Shapes (X, polyhedron) → Shapes (X, solid)(«многогранник» → «геометрическое тело»)Роль отрицательных примеров в предотвращении излишнего обобщения.В последние годы определенную популярность в работах по ИИ получил подход к моделированиюпроцессов обучения/развития на основе так называемых генетических алгоритмов.Понятие о генетических алгоритмах(Использован материал бывшего доступным в 2002 году сайта:http://www.ai.tsi.lv/ru/index.htm, Борисов А.Н.

Курс: Генетические алгоритмы, 2002)Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационныеметоды, впервые предложенные Джоном Генри Холландом в книге «Адаптация в естественных иискусственных системах» (1975). Они основываются на идее эволюции с помощью естественногоотбора, выдвинутой Дарвином.ГА работают с совокупностью "особей" - популяцией, каждая из которых представляетвозможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности"согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это34эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболееприспособленные особи получают возможность "воспроизводить" потомство с помощью"перекрестного скрещивания" с другими особями популяции.

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

В конечном итоге популяция будет сходитьсяк оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительныеоптимальные решения за относительно короткое время.ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемой проблемы.Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов для генерации новыхрешений из предыдущей популяции; 4) Целевая функция для оценки приспособленности (fitness)решений.Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в виде строки.Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строкпредставляет возможное решение задачи.Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание имутация.СелекцияОператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениямиих функции приспособленности. Существуют как минимум два популярных типа оператора селекции:рулетка и турнир.Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки.Колесо рулетки содержит по одному сектору для каждого члена популяции.

Размер i-ого секторапропорционален некоторой величине вычисляемой по формуле.При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особис низкой приспособленностью.Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей.Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи срединих.

Наиболее распространен турнирный отбор с k=2.СкрещиваниеОператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (может быть ибольше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечныйкроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точекразрыва. Точка разрыва - участок между соседними битами в строке.

Обе родительские структурыразрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителейсклеиваются и получаются два генотипа потомков.011##001#135МутацияМутация (mutation) - стохастическое изменение части хромосом. Каждый ген строки, котораяподвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген.Схема работы ГА01 собой0 итерационный#11# тех пор, пока неРабота ГА представляетпроцесс, который0 продолжаетсядо11выполнятся заданноечисло поколений или какой-либо иной критерийостанова.

На каждом поколенииГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.Схема работы простого ГА выглядит следующим образом:НачальнаяпопуляцияотборскрещиваниемутацияПовторение цикла сновой популяциейоценкарезультатаЗадача решена.ВыходКритерии остановки алгоритма:нахождение глобального, либо субоптимального решения;исчерпание числа поколений, отпущенных на эволюцию;исчерпание времени, отпущенного на эволюцию.Генетические алгоритмы служат, главным образом, для поиска решений в очень больших,сложных пространствах поиска.

Примеры реальных областей применения:оптимизация запросов в базах данных;задачи на графах (задача коммивояжера, раскраска);задачи компоновки;составление расписаний.Замечание: Генетические алгоритмы и «метод проб и ошибок».4.Еще один пример обучаемой программы (М.Н. Вайнцвайг)Внешняя постановка задачи:Программа получает на вход цепочку символов в некотором алфавите А (вопрос),36Генерирует ответ (цепочка символов над этим алфавитом),Получает оценку Обучающего (+ - ответ верен, - - ответ неверен).В процессе обучения программа должна научиться всегда строить правильные ответы (всегда получатьоценку +).Базовые знания программы:Несколько универсальных эвристик, используемых человеком в случае столь же неопределенных (неимеющих смысловой интерпретации) задач.

В числе таких эвристик:Не выходить за пределы А.Давать на очередной вопрос ответ, совпадающий с ответом на предыдущий вопрос.Давать на очередной вопрос ответ, совпадающий с ответом на предыдущий вопрос, если этот ответ былоценен +.Правильность ответа на некоторый вопрос не зависит от контекста (хода диалога).День 9. Решение задач и искусственный интеллектДвумя составными элементами процесса решения задач в теории искусственного интеллектаявляются представление (формализация) задач и собственно решение – поиск. Мы рассмотрим дваподхода к решению задач и, соответственно, два способа представления – подход с использованиемпространства состояний и подход, основанный на редукции задач. Для обоих подходов описываютсяиспользуемые алгоритмы поиска решения.