8137

Обучение с использованием знаний. Логическая формулировка задачи обучения

Лекция

Информатика, кибернетика и программирование

Обучение с использованием знаний. Логическая формулировка задачи обучения Обучение с использованием знаний Рассмотрим логические связи между гипотезами, описаниями примеров и классификациями. Пусть Descriptions обозначает коньюнкцию всех описаний пр...

Русский

2013-02-04

78.5 KB

3 чел.

Обучение с использованием знаний.

Логическая формулировка задачи обучения

Обучение с использованием знаний

Рассмотрим логические связи между гипотезами, описаниями примеров и классификациями. Пусть Descriptions обозначает коньюнкцию всех описаний примеров в обучающем множестве, а Classifications – коньюнкцию всех классификаций примеров. В таком случае гипотеза, которая позволяет “объяснить результаты наблюдений”, должна удовлетворять следующему свойству:

Hypothesis & Descriptions |= Classifications

Связь такого рода называется ограничением логического следствия, в котором Hypothesis представляет собой “неизвестное”. Например, если дерево решений рассматривается как логическая формула, то дерево решений, совместимое со всеми примерами, удовлетворяет данному уравнению.

Современный подход состоит в том, что должны проектироваться агенты, которые уже что-то знают и пытаются освоить в процессе обучения некоторую дополнительную информацию. Схема, которая показывает, как в процессе обучения с накоплением знаний используется и со временем обогащается запас фоновых знаний, изображена на рис. 4.

Рис. 4

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

Рассмотрим общеизвестные примеры обучения на основе фоновых знаний.

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

2. Во втором примере путешественник, прибывший в Бразилию, встречает первого в своей жизни бразильца. Услышав от него речь на португальском языке, путешественник делает вывод, что бразильцы говорят на португальском, но узнав, что его собеседника зовут Фернандо, он не делает вывод, что все бразильцы носят это же имя. Аналогичный пример из научной области: когда студент-физик измеряет плотность и проводимость медного образца при определенной температуре, он обобщает эти данные на все предметы из меди. Но измерив массу этого образца, студент не рассматривает гипотезу, что все предметы из меди имеют такую же массу, хотя он может сделать такое обобщение относительно всех монет одинакового достоинства.

3. Следующий пример: студент-медик присутствует на консультации, которую дает пациенту опытный терапевт. После ряда вопросов и ответов специалист сообщает пациенту, чтобы он прошел курс лечения конкретным антибиотиком. Студент-медик делает вывод, что данный антибиотик является эффективным средством лечения при данном конкретном типе инфекции.

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

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

В первом примере используется обобщение, получившее название обучения на основе объяснения (EBLExplanation-Based Learning). Здесь общее правило следует логически из фоновых знаний, которыми обладают пещерные люди:

Hypothesis & Descriptions |= Classifications

Backgraund |= Hypothesis

Во втором примере априорные знания Backgraund касаются релевантности множества характеристик по отношению к целевому предикату. Эти знания, наряду с результатами наблюдений, позволяют агенту вывести новое, общее правило, которое объясняет результаты наблюдений, следующим образом:

Hypothesis & Descriptions |= Classifications

Backgraund &Descriptions & Classifications |= Hypothesis

Обобщение такого рода называется обучением с учетом релевантности (RBLRelevance-Based Learning).

В третьем примере для объяснения примеров объединяются фоновые знания и новая гипотеза:

Backgraund & Hypothesis & Descriptions |= Classifications

Как и при чисто индуктивном обучении, алгоритм обучения должен выдвигать гипотезы, которые являются как можно более простыми и совместимыми с данным ограничением. Такие алгоритмы называются алгоритмами индуктивного обучения на основе знаний (KBILKnowledge-Based Inductive Learning).

Логическая формулировка задачи обучения

Для создания логической формулировки задачи обучения гипотеза представляется в виде множества логических высказываний. Описания примеров и определения классов также заданы в виде логических высказываний, а классификация нового примера может быть выполнена путем логического вывода классификационного высказывания из гипотезы и описания примера. Такой подход обеспечивает инкрементное формирование гипотез и дает возможность использовать априорные знания, так как уже известные высказывания могут помочь при классификации новых примеров.

Рассмотрим логическую формулировку задачи обучения на примере задачи обучения с рестораном, в которой требуется изучить правило принятия решения о том, при каких условиях следует ждать освобождения столика. В логической формулировке задачи атрибуты становятся унарными предикатами. Пусть Xi – обозначение i-го примера. Каждый пример может быть описан с помощью примерно таких высказываний:

Alternate(Xi)&¬Bar(Xi)&¬Fri/Sat(Xi)&Hungry(Xi)& …

Полное обучающее множество представляет собой коньюнкцию всех описательных и классификационных высказываний.

Целью индуктивного обучения в логической постановке задачи является поиск эквивалентного логического выражения для целевого предиката Q, который может использоваться для правильной классификации примеров. Подобное выражение – потенциальное определение целевого предиката – предлагается в каждой гипотезе. Используя Ci для обозначения потенциального определения, можно утверждать, что каждая гипотеза Hi представляет собой высказывание в форме  x Q(x)  Ci(x). В частности, дерево решений представляет собой утверждение, что целевой предикат принимает истинное значение по отношению к какому-то объекту тогда и только тогда, когда выполняются условия в одной из ветвей, ведущих к листовому узлу со значением true. Таким образом, на рис. 4 в графической форме выражено следующее логическое определение Hr:

r WillWait(r) Patrons(r,Some)

 or Patrons(r,Full)&WaitEstimate(r,0-10)

 or Patrons(r,Full)&WaitEstimate(r,30-60)&

   ¬Alternate(r)&Reservation(r)

 or Patrons(r,Full)&WaitEstimate(r,30-60)&

   ¬Alternate(r)&¬Reservation(r)&Bar(r)

 or Patrons(r,Full)&WaitEstimate(r,30-60)&

   Alternate(r)&Fri/Sat(r)

 or Patrons(r,Full)&WaitEstimate(r,10-30)&¬Hungry(r)

 or Patrons(r,Full)&WaitEstimate(r,10-30)&Hungry(r)&

   ¬Alternate(r)

 or Patrons(r,Full)&WaitEstimate(r,10-30)&Hungry(r)&

   Alternate(r)&Raining(r)

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

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

H1 or H2 or H3 or … or Hn

По мере поступления новых примеров появляется возможность исключать гипотезы, не совместимые с этими примерами. Примеры могут быть двух видов по отношению к гипотезе. Пример ложно отрицателен, если гипотеза утверждает, что он должен быть отрицательным, а он фактически положителен. Пример ложно положителен для данной гипотезы, если в гипотезе утверждается, что он должен быть положительным, но фактически он является отрицательным. Если некоторый пример является ложно положительным или ложно отрицательным применительно к некоторой гипотезе, то данный пример и данная гипотеза являются логически несовместимыми друг с другом, что и позволяет исключить данную гипотезу. Операция исключения гипотезы полностью аналогична операции применения правила резолюции в логическом выводе. Дизьюнкция гипотез соответствует выражению, а пример соответствует литералу, который взаимно уничтожается с одним из литералов выражения. Например, если пример I1 несовместим с выражениями H2 и H3, а пространство гипотез представляет собой высказывание H1 or H2 or H3 or H4, то система логического вывода сформирует новое высказывание H1 or H4, соответствующее уточненному пространству гипотез.

Таким образом, индуктивное обучение в логической постановке задачи есть процесс постепенного устранения гипотез, несовместимых с примерами. Но поскольку пространство гипотез велико (бесконечно для логики первого порядка), то обычно система обучения не создается с использованием доказательства на основе резолюции и полного перебора пространства гипотез.


Апр
иорные знания

Гипотезы

Индуктивное

обучение на основе знаний

Наблюдения

Предсказания


 

А также другие работы, которые могут Вас заинтересовать

73826. Операции над матрицами 1.17 MB
  Элементами матрицы могут являться числа алгебраические символы или математические функции. Например матрицы используется для решения систем алгебраических и дифференциальных уравнений нахождения значений физических величин в квантовой теории шифрования сообщений в Интернете. Строки матрицы нумеруются сверху вниз а столбцы слева направо.
73827. Системы уравнений в линейной алгебре 467.5 KB
  Если это определение озвучить в терминах определителей то оно будет выглядеть примерно так: Матрица размера m×n имеет ранг r если существует хотя бы один отличный от нуля определитель rго порядка тогда как определитель любой подматрицы более высокого порядка равен нулю. Для вычисления ранга матрицы можно использовать метод элементарных преобразований строк и столбцов в точности тот самый метод который применяется для вычисления определителей. Целью элементарных преобразований является приведение матрицы к...
73828. Модель затраты- выпуск (модель В. Леонтьева) 121 KB
  Либо не весь объём производства расходуется на потребление и его достаточно для расширения производства тех видов продукции на которые имеется растущий спрос либо объём производства недостаточен для воспроизводства трудового ресурса на постоянном уровне. Свойство наличия баланса состоит как раз в том что полные объёмы всей продукции складываются только из объёмов её конечного потребления и объёмов потребления продукции в производственных процессах межотраслевых потоков. Примером такой взаимосвязи может служить например потребление с х...
73829. Комплексные числа 388 KB
  Определение комплексного числа. Первая компонента комплексного числа действительное число называется действительной частью числа это обозначается так; вторая компонента действительное число называется мнимой частью числа. Два комплексных числа и равны тогда и только тогда когда равны их действительные и мнимые части.
73830. Многочлены -ой степени 536.5 KB
  Многочленом ой степени называется функция где постоянные комплексные числа коэффициенты многочлена комплексная переменная. Число в котором многочлен принимает нулевое значение называется корнем многочлена. Представим в виде многочлена по степеням. Очевидно отсюда следует утверждение: для того чтобы число было корнем многочлена необходимо и достаточно чтобы коэффициент при нулевой степени в разложении по степеням был равен нулю: .
73831. Линейные пространства 451.5 KB
  Обозначим множества векторов направленных отрезков на прямой на плоскости в пространстве соответственно с обычными операциями сложения векторов и умножения векторов на число. Вместо свободных векторов можно рассмотреть соответствующие множества радиус-векторов. Например множество векторов на плоскости имеющих общее начало т. Множество радиус-векторов единичной длины не образует линейное пространство так как для любого из этих векторов сумма не принадлежит рассматриваемому множеству.
73832. Проектирование операционных технологических процессов обработки заготовок 67.5 KB
  обработки позволяет правильно выбрать станок из имеющегося парка или по каталогу. По типу обработки устанавливают группу станков: токарный сверлильный В соответствии с назначением станка его компоновкой степенью автоматизации определяют тип станка: токарный одношпиндельный многошпиндельный револьверный полуавтомат и т. Если эти требования выполнимы на различных станках то при выборе учитывают следующие факторы: 1 соответствие основных размеров станка габаритным размерам обрабатываемой заготовки или нескольких одновременно...
73833. Анализ технологичности конструкции деталей 43 KB
  Ее следует отрабатывать на технологичность комплексно учитывая зависимость технологичности от следующих факторов: исходной заготовки вида обработки технологичности СЕ в которую эта деталь входит. Конструкция должна быть такой чтобы для ее изготовления можно было применять высокопроизводительные методы обработки. Повышение технологичности конструкции изделия предусматривает проведение следующих мероприятий: Создание конфигурации деталей и подбор их материалов позволяющих применение наиболее совершенных исходных заготовок сокращающих объем...
73834. Выбор вариантов схем базирования 40.5 KB
  Для создания возможности повышения уровня концентрации обработки в операции и снижения разнообразия технологической оснастки лучше принять в качестве базы для обработки всех поверхностей детали одну и туже базу Е. Синтез маршрута обработки заготовки Первый шаг синтеза маршрута обработки заготовки распределение отобранных переходов обработки типовых поверхностей заготовки по этапам типовой схемы изготовления деталей соответствующего класса или подкласса. Типовая схема обработки является вариантом полного типового решения. Причиной...