КОМБИНАТОРНЫЙ ВЗРЫВ
Как было отмечено, ИППП не содержит рекомендаций относительно нахождения фактов, нужных для вывода. Применительно к принципу резолюции это означает, что ИППП не дает информации о том, какие именно предложения следует резольвировать относительно друг друга.
Предположим, что мы просто будем брать все возможные комбинации предложений. Предположим также, что у нас есть 10 предложений и что для кратчайшего вывода нужно применить резолюцию 10 раз (то есть пустой дизъюнкт будет получен при десятом применении резолюции). На первом шаге имеется 10 вариантов выбора одной из резольвент (резольвентами будем называть предложения, подвергающиеся резолюции) и 10 вариантов выбора второй, то есть всего 100 (=102) резольвент. Естественно, резольвировать А относительно В — это то же самое, что резольвировать В относительно А, поэтому нам понадобится около половины операций. (На самом деле, нам нужно ровно 55 операций. Однако для арифметических подсчетов 50 — более удобное число, а результат получится столь огромным, что наше огрубление не имеет существенного значения.) На втором100 100 100 ( 104\ шаге —вариантов дадут -у- х -у- ( = возможных комбинаций для первой и второй резолюций, вместе взятых. (Мы снова округляем результат. На самом деле при второй резолюции возможны 11 вариантов: 10 исходных предложений плюс предложение, полученное в результате первого применения резолюции). Продолжая таким обра-
Ю20
зом, к десятому шагу мы получим ~1017 возможных способов осуществления десяти резолюций. Естественно, не исключена возможность того, что пустой дизъюнкт получится более одного раза, однако эта разница с лихвой компенсируется произведенными округлениями. Чтобы дать представление о грандиозности полученного числа, напомним, что количество секунд в столетии меньше, чем 1010.
Специалисты в области ИППП обратили внимание на эту проблему; однако предложенные ими способы ее решения нельзя считать эффективными.
Например, была разработана так называемая стратегия опорного множества (set of support), сущность которой сводится к следующему. Мы начинаем с одного предложения, которое мы хотим доказать, и строим его отрицание. Теперь мы пытаемся опровергнуть это отрицание. Мы можем ограничиться сравнением отрицания исходного предложения со всеми имеющимися предложениями и с результатами предшествующих резолюций. Иначе говоря, если мы пытаемся показать, что предположение об истинности НЕ (Р) ведет к противоречию, то мы не должны резольвировать пары предложений, не имеющих ничего общего с данным.На количество вариантов перебора стратегия опорного множества существенно не влияет. Вместо 1017 мы получим около 1010 допустимых комбинаций. Это означает, что, если даже перебирать варианты со скоростью 10000 в секунду, то и тогда получение нужного вывода займет около 10 дней.
Ситуация, когда сравнительно небольшое количество исходных вариантов в результате комбинаторных преобразований приводит к огромному количеству конечных вариантов, называется комбинаторным взрывом. Это очень трудная проблема, которая встает не только в ИППП. С ней сталкивается любая система, использующая выводы. Однако сейчас большинство специалистов убеждены, что в ИППП названная проблема стоит особенно остро. Причина этого тесно связана с одним из важнейших преимуществ ИППП. В ИППП может быть выведено истинностное значение каждого высказывания, записанного на его языке. Это свойство называется полнотой, и оно, естественно, является весьма желательным при прочих равных условиях. Тем не менее, хотя это и не доказано, многие считают, что всякая полная система необходимо подвержена комбинаторному взрыву. Только неполная система способна обойти это затруднение.
КОГДА МЫ ВЫВОДИМ УМОЗАКЛЮЧЕНИЯ?
Существуют и другие затруднения, касающиеся ИППП. Чтобы понять их, нам придется обратить пристальное внимание на условия, при которых у нас возникает желание, чтобы наши системы вывода производили вывод умозаключений.
Особенно важен для нас простой вопрос о том, когда мы делаем некоторое умозаключение.Пусть перед нами диалоговая система, воспринимающая информацию на естественном языке и отвечающая на соответствующие вопросы. Очевидно, что существуют две временные точки, в которых можно начинать вывод умозаключений: первая — после поступления вопроса, требующего вывода умозаключения, вторая — после поступления в систему достаточной информации для вывода данного умозаключения. Две эти возможности мы назовем, соответственно, временем обработки запроса (question time) и временем обработки входного текста (read time).
Вывод умозаключений во время обработки запроса имеет ряд очевидных преимуществ. Имея определенный набор фактов, мы сталкиваемся с огромным числом умозаключений, которые можно было бы вывести (напомним о комбинаторном взрыве). Очевидно, что все допустимые выводы произвести нельзя, тогда как поступление запроса гарантирует, что мы будем производить лишь те выводы, которые нужны для ответа пользователю. Однако и против такого решения имеются веские возражения.