ИНДУКТИВНОЕ ОБУЧЕНИЕ

Любой алгоритм детерминированного контролируемого обучения получает в качестве исходной информации правильные значения неизвестной функции, соответствующие конкретным входным данным, и должен предпринять попытку восстановить эту неизвестную функцию или сформировать какую-то другую функцию, близкую к ней. Более формально можно определить, что пример представляет собой пару {х, f{x) ), где х— входное, a f (х) — выходное значение функции, применяемой к х. Основная задача чисто индуктивного логического вывода (или просто индукции) указана ниже.
На основании совокупности примеров входных и выходных данных функции f получить функцию Л, которая аппроксимирует f.
Функция h называется гипотезой. С концептуальной точки зрения та причина, по которой задача обучения является трудной, состоит в том, что обычно нелегко определить, действительно ли какая-то конкретная функция h является хорошей аппроксимацией для f. Качественная гипотеза должна обеспечивать приемлемое обобщение, т.е. должна правильно предсказывать появление еще не полученных примеров. В этом состоит фундаментальная проблема индукции. Эта проблема изучалась в течение многих столетий; в разделе 18.5 приведено ее частичное решение.
На рис. 18.1 приведен известный пример: подгонка функции от одной переменной к некоторым точкам из набора данных. Примеры представляют собой
На рис. 18.1, в показан второй набор данных. С этим набором данных нельзя совместить прямую линию; в действительности для обеспечения точного согласования с ним требуется полином шестой степени (с семью параметрами). Количество точек равно только семи, поэтому полином должен иметь столько же параметров, сколько имеется точек данных; таким образом, создается впечатление, что этот полином не позволяет найти в данных какие-либо повторяющиеся шаблоны, и поэтому не следует ожидать, что с его помощью будет получено хорошее обобщение. Может оказаться, что лучше согласовать этот набор данных с прямой линией, которая не будет точно совместимой, но позволит получать вполне обоснованные предсказания. Принятие данного решения равносильно признанию такой возможности, что истинная функция не является детерминированной (или, что примерно эквивалентно
пары (х, f (х) ), где и х и f (х) — действительные числа. Выберем в качестве пространства гипотез н (множества гипотез, которые мы будем рассматривать в качестве потенциально приемлемых) множество полиномов, имеющих степень не больше к, таких как Зх2 + 2, х17-4х3 и т.д. На рис. 18.1, а показаны данные, которые соответствуют некоторой прямой (полиному первой степени). Эта прямая называется совместимой с гипотезой, поскольку она согласуется со всеми данными. На рис. 18.1,6" показан полином более высокой степени, который также согласуется с этими данными. Данный случай может служить иллюстрацией к наиболее важной проблеме в индуктивном обучении: как осуществлять выбор среди многочисленных согласованных гипотез? Ответ состоит в использовании принципа бритвы Оккама2, согласно которому предпочтение следует отдавать наиболее простой гипотезе, согласующейся с данными. Интуитивно ясно, что такой подход имеет смысл, поскольку гипотезы не позволяют извлекать из данных какую-либо информацию, если они не проще самих данных. Определить, какая гипотеза проще, а какая сложнее, обычно нелегко, но, по-видимому, вполне резонным является утверждение, что полином первой степени проще по сравнению с полиномом двенадцатой степени.
этому утверждению, истинные входные данные не являются полностью наблюдаемыми). При наличии недетерминированных функций неизбежно приходится искать компромисс между сложностью гипотезы и степенью ее согласования с данными. В главе 20 показано, как достичь этого компромисса с помощью теории вероятностей.
Следует всегда учитывать, что возможность или невозможность найти простую, согласованную гипотезу зависит главным образом от выбранного пространства гипотез. На рис. 18.1, г показано, что данные, приведенные на рис. 18.1, в, могут быть точно согласованы с простой функцией в форме ax+b+csinx. Этот пример подчеркивает важность выбора пространства гипотез. Пространство гипотез, состоящее из полиномов конечной степени, не позволяет точно представить синусоидальные функции, поэтому ученик, использующий такое пространство гипотез, не сможет осуществить обучение с использованием синусоидальных данных. Принято считать, что задача обучения является реализуемой, если пространство гипотез содержит подходящую функцию; в противном случае она является нереализуемой. К сожалению, в любой ситуации невозможно сразу же определить, относится ли данная конкретная задача обучения к категории реализуемых, поскольку не известна истинная функция. Один из способов, позволяющих преодолеть этот барьер, состоит в использовании априорных знаний для логического вывода пространства гипотез, в котором, как известно, должна находиться истинная функция. Эта тема рассматривается более подробно в главе 19.
Еще один подход состоит в применении наибольшего возможного пространства гипотез. Например, почему бы не использовать в качестве Н класс всех машин Тьюринга? В конечном итоге любая вычислимая функция может быть представлена с помощью некоторой машины Тьюринга, и это — наилучший способ представления, который только может применяться. Но при реализации этой идеи возникает проблема, связанная с тем, что в ней не учитывается вычислительная сложность обучения. Необходимо найти компромисс между выразительностью пространства гипотез и сложностью поиска простой, совместимой гипотезы в этом пространстве. Например, подгонка к данным прямых линий осуществляется очень просто; подбор полиномов высокой степени становится сложнее, а создание соответствующих машин Тьюринга действительно представляет собой очень сложную задачу, поскольку неразрешима в общем виде даже проблема определения того, является ли конкретная машина Тьюринга совместимой с данными. Второй причиной, по которой следует предпочесть простые пространства гипотез, является то, что результирующие гипотезы могут оказаться более простыми в использовании, т.е. вычисление п(х), если h — линейная функция, будет осуществляться быстрее, чем при использовании программы, моделирующей произвольную машину Тьюринга.
По этим причинам основной объем исследований в области обучения был сосредоточен на относительно простых способах представления. В данной главе в основном рассматриваются пропозициональная логика и связанные с ней языки. В главе 19 рассматриваются теории обучения в логике первого порядка. Ниже будет показано, что компромисс между выразительностью и сложностью найти не так просто, как кажется на первый взгляд, поскольку, как было описано в главе 8, выразительный язык позволяет создать простую теорию, согласующуюся с данными, а ограничение выразительности языка приводит к тому, что любая согласованная теория должна стать очень сложной. Например, правила шахмат могут быть записаны в логике первого порядка на одной или двух страницах, но потребуют тысячи страниц при их формулировке в пропозициональной логике. Кроме того, в подобных случаях при использовании более выразительного языка намного ускоряется обучение.







Материалы

Яндекс.Метрика