Cтраница 3
Эти две особенности MYC1N тесно увязаны. Нет необходимости использовать обратное прослеживание, поскольку мы неотступно следуем за множеством независимых свидетельств и на заключительной стадии ранжируем гипотезы. Процесс обратного прослеживания требует больших затрат вычислительных ресурсов системы, так как приходится сохранять информацию о предыдущих этапах вычислений, к которым, возможно, придется еще возвращаться. Большой объем пространства состояний, в котором ведется поиск, требует значительных ресурсов памяти. На практике при этом используется механизм постраничного обмена между оперативной и дисковой памятью, что отрицательно сказывается на производительности системы в целом. Однако значительные вычислительные ресурсы отвлекаются на активизацию каждого потенциально подходящего правила, от чего приходится отказываться в некоторых системах. [31]
Пропускать вершины до тех пор, пока не встретится вершина в состоянии внутри, помеченная как противоречие. Если во время обратного прослеживания используется поддержание истинности ( шаги с первого по пятый), то вновь начать шаг 6; в противном случае вернуться. [32]
Если о данном значении не существует никакой дополнительной информации, то действительного подтверждения не будет ни у одной из альтернативных вершин кроме Аг, так что Аг будет внутри, а все остальные альтернативные вершины будут вне. Анализируя полученное из Аг противоречие, механизм обратного прослеживания по зависимостям распознает, что Аг является предположением, поскольку зависит от нахождения других альтернативных вершин в состоянии вне. Обратный прослеживатель может тогда подтвердить одну из других альтернативных вершин, например А /, вызывая переход Аг в состояние вне. [33]
На этой основе мы формулируем правила, направляющие пересмотр допущений, как планы для осуществления заданий выбора. Каждый план пересмотра рассматривается как специализация общей процедуры обратного прослеживания по зависимостям. Такие усовершенствованные варианты общей процедуры обратного прослеживания учитывают форму допущений ( и, следовательно, состояние решателя задач) при принятии решения о том, какие предположения должны быть отвергнуты. Детали этого исследования будут изложены в моей диссертации, которая скоро выйдет. [34]
Механизм сопоставления должен быть достаточно эффективным, поскольку исчерпывающий поиск можно применять только при работе с базами прецедентов сравнительно небольшого объема. При этом прецеденты, у которых какие-либо свойства совпадают, включаются в один кластер, в результате чего формируется таксономия типов прецедентов. Сопоставление в такой разделяемой сети свойств выполняется с помощью алгоритма поиска в ширину без обратного прослеживания. Поэтому время поиска связано с объемом пространства логарифмической зависимостью. Индивидуальное сопоставление, как правило, выполняется следующим образом. [35]
Здесь подтверждение для SR, означает, что R, была предложена как член класса эквивалентности и никакой другой член этого класса не был выбран представителем. Это подтверждение служит предположением по умолчанию о том, что R / является выбранным представителем. Таким образом, селектор для класса эквивалентности выбирает из него альтернативы в том порядке, в котором они добавлялись к множеству альтернатив, пряча этот выбор от системы обратного прослеживания. [36]
Тот факт, что пространство версий суммирует данные, означает, что его можно использовать в качестве базиса для формирования новых экземпляров для обучающей выборки, т.е. экземпляров, которые могли бы еще более сблизить границы. То, что программа анализирует каждый экземпляр только один раз, позволяет обойтись без сохранения ранее обработанных экземпляров. Следовательно, и время обучения пропорционально объему обучающей выборки, а не связано с количеством экземпляров в ней какой-либо показательной функцией. Поскольку отпадает необходимость в обратном прослеживании, эффективность процедуры должна быть довольно высокой. Наиболее серьезным подводным камнем в этой технологии является фактор ветвления в процессе частичного упорядочения образцов, который имеет тенденцию к комбинаторному росту по мере увеличения количества дизъюнктов в описаниях концептов. [37]
На этой основе мы формулируем правила, направляющие пересмотр допущений, как планы для осуществления заданий выбора. Каждый план пересмотра рассматривается как специализация общей процедуры обратного прослеживания по зависимостям. Такие усовершенствованные варианты общей процедуры обратного прослеживания учитывают форму допущений ( и, следовательно, состояние решателя задач) при принятии решения о том, какие предположения должны быть отвергнуты. Детали этого исследования будут изложены в моей диссертации, которая скоро выйдет. [38]
После того как таким образом будут исследованы все маркированные вершины, может оказаться, что для всех вершин будет найден солидный статус поддержки. Однако может случиться и так, что вследствие цикличностей некоторые из вершин останутся маркированными. Тогда TMS инициирует процесс сглаживания ограничений, который присваивает статус поддержки оставшимся вершинам. После всего этого TMS проверяет противоречивость и СР-подтверждения, выполняет, если это необходимо, обратное прослеживание по зависимостям и обработку СР-подтверждений и, наконец, сигнализирует программе пользователя об изменениях статуса поддержки тех вершин, которые были вовлечены в поддержание истинности. [39]
Для выбора своих действий рассуждающие программы должны быть в состоянии делать предположения и пересматривать эти предположения, если новые открытия противоречат им. Система поддержания истинности TMS ( Truth Maintenance System) является подсистемой решателя задач, выполняющей эти функции путем записи и поддержки причин для допущений, имеющихся в программе. Такие записанные причины полезны при конструировании объяснений действий программы и управления порядком действий решателя задач. В статье описываются: 1) представления и структура TMS; 2) методы пересмотра текущего множества допущений; 3) изменение множества текущих предположений при обратном прослеживании по зависимостям; 4) методы подытоживания объяснений допущений; 5) организация решателя задач на базе диалектически аргументирующих модулей; 6) способ пересмотра моделей систем допущений других; 7) методы встраивания управляющих структур в предположения. Мы подчеркиваем необходимость для решателей задач выбирать между альтернативными системами допущений и намечаем в общих чертах механизм, посредством которого решатель задач может использовать правила, управляющие выбором того; что допускать, чего хотеть и что делать. [40]
Хотя система R1 и формирует иногда несколько вариантов решения одной и той же задачи, в ней никогда не выполняется обратное прослеживание. Иными словами, в ней никогда не формируется промежуточный вариант решения, к которому затем можно вернуться и отменить. На любой стадии процесса решения задачи система располагает достаточными знаниями для того, чтобы сделать следующий шаг. К тому же при использовании обратного прослеживания пользователю очень сложно понять ход рассуждений, который привел к предлагаемому варианту решения. [41]
Выше уже отмечалось, что использование понятия контекста при решении задачи синтеза конфигурации в определенной мере соответствует тому способу мышления, который близок эксперту-человеку. Если же обратиться к методу Match, то ситуация становится в определенной мере обратной. Человек-эксперт при решении аналогичной задачи не использует ничего, подобного этому методу. Скорее он склонен к эвристическому поиску в той или иной форме, что само по себе часто приводит к использованию обратного прослеживания. Преимущество использования метода Match с точки зрения затрачиваемых вычислительных ресурсов несомненно, и в этом ему следует отдать предпочтение перед методом эвристического поиска при разработке программ решения тех задач, где метод Match можно применить. [42]
Это позволяет обойти невыполнимое требование теоретиков проектирования, согласно которому прежде, чем рассматривать детали, следует определить цели и критерии. Введение дополнительного этапа прогнозирования дает возможность начать решение с наиболее достоверно и детально определенного конца задачи вместо того, чтобы, как обычно, ограничивать поле поиска мелкими изменениями, не выходящими за пределы одного конструктивного решения. За это преимущество, однако, приходится весьма недешево платить. Поскольку исследования дают ответы на более широкий круг вопросов, чем требуется для решения данной задачи проектирования, и являются дополнением к последовательности строго необходимых операций проектирования, их можно отнести к статье сверхнормативных затрат. Однако затраты материальных средств и рабочего времени конструкторов в связи с проведением исследовательских работ компенсируются отчасти тем, что при этом ошибки исправляются с небольшими затратами на ранних стадиях, тогда как на более поздних стадиях их исправление было бы связано с большим материальным ущербом; частично они компенсируются также экономией времени, которое было бы затрачено на обратное прослеживание причинно-следственных связей; наконец, они отчасти компенсируются теми знаниями и навыками, которые при этом приобретаются и могут быть использованы не только при работе над данным проектом, но в значительной мере и при создании аналогичных конструкций в будущем. Когда при выполнении какого-то проекта недорогой ценой получают опережающую информацию, которую можно использовать в дальнейших разработках, это можно считать объективированным эквивалентом перенесения проектировщиком ( рассматриваемым как черный ящик) приобретенного опыта с одной задачи на другую. Исследовательская работа отличается от личного опыта более высокой точностью и меньшей зависимостью от общей формы прошлых конструкций. [43]
Пространство решений может оказаться и нефакторизуемым, в каком бы смысле мы не трактовали этот термин. Очень часто оказывается, что проблема проектирования допускает выработку частного решения какого-либо компонента только в контексте всего проекта. При сборке головоломки нельзя предсказать, найдено ли верное решение, пока последний элемент мозаики не станет на свое место. Общий подход к работе в большом пространстве поиска состоит в том, чтобы последовательно рассматривать его на разных уровнях абстракции, т.е. использовать варианты описания пространства с разным уровнем учета деталей. Применение метода нисходящего уточнения требует исключить, по возможности, обратное прослеживание между уровнями, реализация которого требует значительных вычислительных ресурсов. Но это срабатывает только в случае, если между уровнями нет тесного взаимодействия. Как было показано в главе 15, эффективной стратегией решения такого рода задач является стратегия наименьшего принуждения ( least commitment), подкрепленная адекватным механизмом разрешения конфликтов. [44]
Решатели задач, организованные так, чтобы поощрять модульность и дополнимость, часто включают несколько различных методов и правил, которые вычисляют значения одной и той же величины или дают описания одного и того же объекта. Следуя [9, 59], мы называем эти множественные результаты сопряженными. Если при помощи различных методов было получено несколько значений какой-либо величины, то, проверяя эти конкурирующие значения на совместность, часто можно получить ценную информацию. Если такими значениями, например, являются многочлены, то такая проверка на совместность иногда позволяет найти значения одной или нескольких переменных. После проверки сопряженных элементов на совместность и получения новой информации благоразумные программы в дальнейших вычислениях используют только одно из предложенных значений, сохраняя остальные для будущих ссылок. Эти различные значения образуют класс эквивалентности по использованию переданного значения в других вычислениях. Одно из значений в этом классе должно быть выбрано представителем класса, предназначенным для распространения в другие вычисления. Мы можем выбирать представителя, пользуясь предположениями по умолчанию, но это приводит к нежелательному поведению обратного прослеживания. Если, например, система обратного прослеживания находит представителя класса эквивалентности, который вовлечен в несовместность, то следует найти способ отвергнуть этого представителя, понимаемого как точное значение, а не оставлять это значение и одновременно выбирать другого представителя. [45]