Описанный здесь первый подход к индуктивному логическому программированию начинается с получения очень общего правила и его постепенного уточнения для достижения соответствия с данными. По сути такой же процесс происходит при обучении деревьев решений, когда дерево решений постепенно наращивается до тех пор, пока не становится совместимым с результатами наблюдений. Но для осуществления индуктивного логического программирования вместо атрибутов используются литералы первого порядка, а вместо дерева решений рассматриваются гипотезы, представляющие собой множества выражений. В этом разделе рассматривается программа Foil [1258], одна из первых программ ILP.

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

а отрицательными — такие примеры:

Обратите внимание на то, что каждый пример представляет собой пару объектов, поскольку Grandfather— это бинарный предикат. В целом в данном генеалогическом дереве имеется 12 положительных примеров и 388 отрицательных (все прочие пары людей).

Программа Foil строит множества выражений, в каждом из которых Grandfather (x, у) является головой предиката. Эти выражения должны классифицировать 12 положительных примеров как экземпляры отношения Grandfather{х,у) и вместе с тем исключать 388 отрицательных примеров. Рассматриваемые выражения являются хорновскими выражениями, расширенными с помощью отрицаемых литералов, в которых используется отрицание как недостижение цели, по аналогии с языком Prolog. Первоначальное выражение имеет такое пустое тело: