Обсуждение полученных результатов
В рамках теории вычислительного обучения был создан новый способ трактовки проблемы обучения. В начале 1960-х годов разработки в области теории обучения
сосредоточивались в основном на проблеме успешной идентификации в пределе. В соответствии с этим понятием любой алгоритм идентификации должен возвращать гипотезу, которая точно совпадает с истинной функцией. Один из способов решения этой задачи состоит в следующем: вначале упорядочить все гипотезы в множестве н в соответствии с некоторым критерием простоты, затем выбрать простейшую гипотезу, совместимую со всеми полученными до сих пор примерами. По мере получения новых примеров в этом методе предусмотрен отказ от более простой гипотезы, которая стала недействительной, и принятие вместо нее более сложной гипотезы. Но после того как достигается истинная функция, от нее никогда не происходит отказ. К сожалению, в больших пространствах гипотез количество примеров и продолжительность вычислений, необходимая для достижения истинной функции, становятся колоссальными. Поэтому теория вычислительного обучения не определяет безусловного требования, чтобы обучающийся агент определил "единственный истинный закон", руководящий его средой, а вместо этого допускает, чтобы он нашел гипотезу с определенной степенью прогностической точности. Кроме того, в теории вычислительного обучения большое внимание уделяется выявлению компромисса между выразительностью языка гипотез и сложностью обучения, поэтому развитие этой теории непосредственно привело к созданию важного класса обучающих алгоритмов, получившего название машин поддерживающих векторов (support vector machine).
Приведенные в данном разделе результаты РАС-обучения представляют собой результаты определения сложности для наихудшего случая и не обязательно отражают выборочную сложность для среднего случая, которая измеряется с помощью приведенных здесь кривых обучения. При анализе среднего случая необходимо также принять предположения о распределении вероятностей примеров и распределении вероятностей истинных функций, которые должны быть изучены с помощью данного алгоритма. По мере того как достигается все лучшее понимание этих проблем, теория вычислительного обучения предоставляет все более ценную помощь исследователям в области машинного обучения, для которых важно предсказать или модифицировать обучающую способность создаваемых ими алгоритмов. Кроме списков решений, важные результаты были получены почти для всех известных подклассов булевых функций, для множеств высказываний первого порядка (глава 19) и для нейронных сетей (глава 20). Эти результаты показывают, что чистые задачи индуктивного обучения, в которых агент приступает к работе без априорных знаний о целевой функции, обычно являются очень трудными. Как будет показано в главе 19, использование априорных знаний для управления индуктивным обучением дает возможность изучать весьма крупные множества высказываний на основе приемлемого количества примеров, даже если используется столь выразительный язык, как логика первого порядка.
РЕЗЮМЕ
Настоящая глава главным образом посвящена изложению темы индуктивного обучения детерминированных функций на основе примеров. Основные вопросы, рассматриваемые в этой главе, перечислены ниже.
• Обучение принимает много разных форм в зависимости от характера производительного элемента, компонента, подлежащего усовершенствованию, и доступной обратной связи.
• Если доступна обратная связь либо от учителя, либо от среды, позволяющая получать правильные значения, относящиеся к примерам, то задача обучения относится к типу контролируемого обучения. Такая задача, называемая также индуктивным обучением, сводится к изучению некоторой функции на примерах ее входных и выходных данных. Изучение функции с дискретными значениями называется классификацией; изучение непрерывной функции называется регрессией.
• Индуктивное обучение сводится к поиску совместимой гипотезы, которая согласуется с примерами. При этом должен соблюдаться принцип бритвы Окка-ма, согласно которому следует всегда выбирать наиболее простую совместимую гипотезу. Сложность решения этой задачи зависит от выбранного способа представления.
• Деревья решений позволяют представить любые булевы функции. Эвристика, определяющая приращение информации, может стать основой эффективного метода поиска простого, совместимого дерева решений.
• Производительность обучающего алгоритма измеряется кривой обучения, которая показывает прогностическую точность применения алгоритма к проверочному множеству как функцию от размера обучающего множества.
• Методы обучения ансамбля деревьев решений, такие как усиление, часто показывают более высокую производительность по сравнению с методами обучения отдельных деревьев решений.
• Для анализа выборочной и вычислительной сложности индуктивного обучения применяется теория вычислительного обучения. Эта теория позволяет найти компромисс между выразительностью языка гипотез и легкостью обучения.