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

Если некоторый пример является ложно положительным или ложно отрицательным применительно к некоторой гипотезе, то данный пример и данная гипотеза являются логически несовместимыми друг с другом. При условии, что рассматриваемый пример представляет собой правильное наблюдение факта, такая ситуация позволяет исключить данную гипотезу. С точки зрения логики соответствующая операция исключения гипотезы полностью аналогична операции применения правила резолюции в логическом выводе (см. главу 9); в этой аналогии дизъюнкция гипотез соответствует выражению, а пример соответствует литералу, который взаимно уничтожается с одним из литералов выражения. Поэтому в принципе может быть обеспечено обучение на примерах обычной системы логического вывода путем удаления одной или нескольких гипотез. В частности, предположим, что пример оформлен в виде высказывания, а пространство гипотез представляет собой высказывание. В таком случае, если высказываниенесовместимо с выражениями, то система логического вывода может сформировать новое высказывание, соответствующее уточненному пространству гипотез.

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