На рис. 18.1, в показан второй набор данных. С этим набором данных нельзя совместить прямую линию; в действительности для обеспечения точного согласования с ним требуется полином шестой степени (с семью параметрами). Количество точек равно только семи, поэтому полином должен иметь столько же параметров, сколько имеется точек данных; таким образом, создается впечатление, что этот полином не позволяет найти в данных какие-либо повторяющиеся шаблоны, и поэтому не следует ожидать, что с его помощью будет получено хорошее обобщение. Может оказаться, что лучше согласовать этот набор данных с прямой линией, которая не будет точно совместимой, но позволит получать вполне обоснованные предсказания. Принятие данного решения равносильно признанию такой возможности, что истинная функция не является детерминированной (или, что примерно эквивалентно этому утверждению, истинные входные данные не являются полностью наблюдаемыми). При наличии недетерминированных функций неизбежно приходится искать компромисс между сложностью гипотезы и степенью ее согласования с данными. В главе 20 показано, как достичь этого компромисса с помощью теории вероятностей.

Следует всегда учитывать, что возможность или невозможность найти простую, согласованную гипотезу зависит главным образом от выбранного пространства гипотез. На рис. 18.1, г показано, что данные, приведенные на рис. 18.1, в, могут быть точно согласованы с простой функцией в форме ax+b+csinx. Этот пример подчеркивает важность выбора пространства гипотез. Пространство гипотез, состоящее из полиномов конечной степени, не позволяет точно представить синусоидальные функции, поэтому ученик, использующий такое пространство гипотез, не сможет осуществить обучение с использованием синусоидальных данных. Принято считать, что задача обучения является реализуемой, если пространство гипотез содержит подходящую функцию; в противном случае она является нереализуемой. К сожалению, в любой ситуации невозможно сразу же определить, относится ли данная конкретная задача обучения к категории реализуемых, поскольку не известна истинная функция. Один из способов, позволяющих преодолеть этот барьер, состоит в использовании априорных знаний для логического вывода пространства гипотез, в котором, как известно, должна находиться истинная функция. Эта тема рассматривается более подробно в главе 19.