ФОНЕТИЧЕСКИЙ звуко-буквенный разбор слов онлайн
 <<
>>

КОМБИНАТОРНЫЙ ВЗРЫВ

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

Пред­положим, что мы просто будем брать все возможные комби­нации предложений. Предположим также, что у нас есть 10 предложений и что для кратчайшего вывода нужно при­менить резолюцию 10 раз (то есть пустой дизъюнкт будет получен при десятом применении резолюции). На первом шаге имеется 10 вариантов выбора одной из резольвент (резольвентами будем называть предложения, подвергаю­щиеся резолюции) и 10 вариантов выбора второй, то есть всего 100 (=102) резольвент. Естественно, резольвировать А относительно В — это то же самое, что резольвировать В относительно А, поэтому нам понадобится около половины операций. (На самом деле, нам нужно ровно 55 операций. Однако для арифметических подсчетов 50 — более удобное число, а результат получится столь огромным, что наше ог­рубление не имеет существенного значения.) На втором

100 100 100 ( 104\ шаге —вариантов дадут -у- х -у- ( = возможных ком­бинаций для первой и второй резолюций, вместе взятых. (Мы снова округляем результат. На самом деле при второй резолюции возможны 11 вариантов: 10 исходных предложений плюс предложение, полученное в результате первого применения резолюции). Продолжая таким обра-

Ю20

зом, к десятому шагу мы получим ~1017 возможных спо­собов осуществления десяти резолюций. Естественно, не исключена возможность того, что пустой дизъюнкт полу­чится более одного раза, однако эта разница с лихвой ком­пенсируется произведенными округлениями. Чтобы дать представление о грандиозности полученного числа, напом­ним, что количество секунд в столетии меньше, чем 1010.

Специалисты в области ИППП обратили внимание на эту проблему; однако предложенные ими способы ее решения нельзя считать эффективными.

Например, была разработана так называемая стратегия опорного множества (set of sup­port), сущность которой сводится к следующему. Мы начи­наем с одного предложения, которое мы хотим доказать, и строим его отрицание. Теперь мы пытаемся опровергнуть это отрицание. Мы можем ограничиться сравнением отрица­ния исходного предложения со всеми имеющимися предло­жениями и с результатами предшествующих резолюций. Иначе говоря, если мы пытаемся показать, что предполо­жение об истинности НЕ (Р) ведет к противоречию, то мы не должны резольвировать пары предложений, не имеющих ничего общего с данным.

На количество вариантов перебора стратегия опорного множества существенно не влияет. Вместо 1017 мы получим около 1010 допустимых комбинаций. Это означает, что, если даже перебирать варианты со скоростью 10000 в секунду, то и тогда получение нужного вывода займет около 10 дней.

Ситуация, когда сравнительно небольшое количество исходных вариантов в результате комбинаторных преобра­зований приводит к огромному количеству конечных вари­антов, называется комбинаторным взрывом. Это очень труд­ная проблема, которая встает не только в ИППП. С ней сталкивается любая система, использующая выводы. Одна­ко сейчас большинство специалистов убеждены, что в ИППП названная проблема стоит особенно остро. Причина этого тесно связана с одним из важнейших преимуществ ИППП. В ИППП может быть выведено истинностное значе­ние каждого высказывания, записанного на его языке. Это свойство называется полнотой, и оно, естественно, является весьма желательным при прочих равных условиях. Тем не менее, хотя это и не доказано, многие считают, что всякая полная система необходимо подвержена комбинаторному взрыву. Только неполная система способна обойти это за­труднение.

КОГДА МЫ ВЫВОДИМ УМОЗАКЛЮЧЕНИЯ?

Существуют и другие затруднения, касающиеся ИППП. Чтобы понять их, нам придется обратить пристальное вни­мание на условия, при которых у нас возникает желание, чтобы наши системы вывода производили вывод умозаклю­чений.

Особенно важен для нас простой вопрос о том, когда мы делаем некоторое умозаключение.

Пусть перед нами диалоговая система, воспринимающая информацию на естественном языке и отвечающая на соот­ветствующие вопросы. Очевидно, что существуют две вре­менные точки, в которых можно начинать вывод умозаклю­чений: первая — после поступления вопроса, требующего вывода умозаключения, вторая — после поступления в сис­тему достаточной информации для вывода данного умоза­ключения. Две эти возможности мы назовем, соответствен­но, временем обработки запроса (question time) и временем обработки входного текста (read time).

Вывод умозаключений во время обработки запроса име­ет ряд очевидных преимуществ. Имея определенный набор фактов, мы сталкиваемся с огромным числом умозаключе­ний, которые можно было бы вывести (напомним о комбина­торном взрыве). Очевидно, что все допустимые выводы про­извести нельзя, тогда как поступление запроса гарантирует, что мы будем производить лишь те выводы, которые нужны для ответа пользователю. Однако и против такого решения имеются веские возражения.

<< | >>
Источник: В.А. ЗВЕГИНЦЕВ. НОВОЕ В ЗАРУБЕЖНОЙ ЛИНГВИСТИКЕ. ВЫПУСК XII. ПРИКЛАДНАЯ ЛИНГВИСТИКА. МОСКВА «РАДУГА» - 1983. 1983

Еще по теме КОМБИНАТОРНЫЙ ВЗРЫВ:

  1. 1.1. Научные исследования моды как социально! о явления: специфика социологических подходов
  2. Инновация
  3. Поэзия 1790-1810-х годов
  4. ЯЗЫК ХУДОЖЕСТВЕННОГО ПРОИЗВЕДЕНИ
  5. Прилагательные адъективного склонения
  6. § 2. Фонетические процессы
  7. ФОНЕТИЧЕСКИЕ ОСОБЕННОСТИ ЮЖНОРУССКИХ ГОВОРОВ ТВЕРСКОЙ ОБЛАСТИ (К ПРОБЛЕМЕ ДИНАМИКИ ДИАЛЕКТА)
  8. Лекция 2. Взаимодействие звуков в потоке речи
  9. в
  10. п
  11. ф
  12. Эйнар Хауген НАПРАВЛЕНИЯ В СОВРЕМЕННОМ ЯЗЫКОЗНАНИИ
  13. Б. Мальмберг ПРОБЛЕМА МЕТОДА В СИНХРОННОЙ ФОНЕТИКЕ[247]