Die Metapher und Das Gestalt -- 1/2001 -

Асимметрия познавательных механизмов и ее следствия

§ 2. ИТЕРАТИВНЫЕ МЕТОДЫ РАСПОЗНАВАНИЯ ПРОПОЗИЦИОНАЛЬНОЙ ВЫПОЛНИМОСТИ

1. Универсальная переборная задача

В качестве таковой рассмотрим задачу нахождения пути через целочисленную матрицу размера 3`m; этот путь не содержит нулей и чисел, равных по величине, но противоположных по знаку (путь - это набор чисел по одному из каждого столбца). Если n - максимум модуля встречающихся в матрице А чисел, то составленный из нулей и единиц n-вектор

является решением задачи (или - выполняющим булевым вектором), коль скоро существует путь через A, содержащий лишь такие i, что

sign (i) = sign(X |i| - 1/2)

(т.е. при Xi = 1 мы включаем в путь i, а при Xi = 0 включаем -i). Получена тривиальная переформулировка задачи распознавания пропозициональной выполнимости (выбор числа строк A основан на известном результате о линейном сведении произвольной формулы к конъюнктивно-нормальной форме с трехчленными дизъюнкциями).

Для вектора (1) легко проверяется (за линейное от длины A число шагов), является ли он решением для A. Вместе с тем, чтобы найти такое решение или убедиться в его отсутствии, следует теоретически перебрать 2n векторов. Мы сталкиваемся с так называемой переборной задачей, т. е. задачей, перебор решений в которой требует экспоненциального числа шагов, а проверка каждого решения — полиномиального. Более того, можно доказать, что рассматриваемая задача является универсальной переборной, т.е. такой, что к ней сводятся (с полиномиальной оценкой сложности сведения) все другие переборные задачи; см., например, [16]).

Эффективный механизм предъявления ответов для универсальной переборной задачи моделировал бы самые существенные стороны механизма интуитивного выбора. Реальное наличие такого механизма в мозгу объясняло бы многие факты, представляющиеся загадочными в рамках современной психологии творчества (а отчасти — и в рамках современной научной парадигмы). Не случаен поэтому поиск самых неожиданных возможностей физической реализации такого механизма. Для предлагаемой ниже модели важное значение имели устные сообщения, сделанные Ю.В. Матиясевичем и В.Я. Крейновичем на семинаре в Ленинградском отделении математического института АН СССР (первый предложил «электротехническую» схему на элементах со сверхпроводимостью, которая проводит ток лишь при наличии пути через соответствующую матрицу, а второй связал проблему интуитивного выбора с акаузальными эффектами в физике).

При этом рассматриваемая модель носит вполне «приземленный» и «левополушарный» характер, легко реализуется на современных ЭВМ без привлечения каких бы то ни было новых технических средств и не гарантирует практическую эффективность метода (точнее, имеется ряд подтверждений эффективности метода, но они еще далеки от построения оценок сложности для общего случая). В контексте данной статьи модель интересна прежде всего тем, что, сохраняя возможность осмысления левым полушарием, она обладает почти всеми особенностями познавательного механизма правого полушария. В частности, она отражает глобальный принцип обработки информации и фактически реализует распараллеленный перебор экспоненциального числа путей на процессорах, число которых линейно зависит от длины исходных данных.

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

2. Формулировка итеративных методов

Пусть А, m и n такие, как в предыдущем пункте. Сопоставим каждому числу i из 2n ненулей матрицы А неотрицательное число, обозначаемое e(i) и называемое «заторможенностью» i. Вектор

(2) (e(-n),e(-n+1),...,e(-1),e(1),...,e(n))

назовем тормозом для А. Будем говорить, что тормоз определяет вектор (1), если

(Xi=0 => e(-i)=0) & (Xi=1 => e(i)=0), i=1,...,n

Тормоз назовем правильным, если он определяет ровно один вектор (правильный тормоз содержит ровно n нулей).

Рассмотрим оператор K R,L, пересчитывающий значения заторможенностей по следующей формуле (R и L — неотрицательные числа, e` — новые значения заторможенностей):

e`(i) = R•e(i) + L•( min{ek (a1,k)} + min{ek (a2,k)} + ...
+ min{ek (aj,k)}),

где j пробегает по номерам всех столбцов, содержащих -i, а минимум берется по всем элементам j-го столбца, кроме -i (т.е. по двум элементам); при этом считаем, что нули матрицы А формально заторможены бесконечно большим числом. K R,L - однородный, непрерывный, кусочно-линейный оператор.

В неформальных терминах: новое значение заторможенности i складывается из старого и того, насколько трудно «пробиться» сигналу, учитывая прежние заторможенности всех других чисел и считая, что сигналу полностью запрещено проходить через -i. Понятно, что иногда вместо min, естественно использовать другие функции (хотя бы среднее арифметическое).

Лемма. При любых R и L пространство тормозов, определяющих решение задачи А, является инвариантным пространством оператора K R,L (при R1O итерации K R,L сохраняют правильность тормозов, определяющих решения).

Эта простая лемма является симптомом того, что во многих случаях последовательность приближения Xn сходится по направлению к решению (т. е. речь идет о сходимости Xn / ||Xn|| ). Правда, непосредственное применение метода последовательных приближений часто затруднено тем, что решение определяется отнюдь не главным собственным направлением оператора K R,L. Это обстоятельство может учитываться разными способами. В качестве основного приема (способствующего, кроме того, ускорению сходимости) используется следующий: шаги применения оператора K R,L перемежаются шагами выбора окончательно заторможенного числа (т. е. в соответствии с теми или иными критериями из чисел i и -i выбирается более заторможенное и превращается в 0; это соответствует превращению соответствующей заторможенности в бесконечность и рассмотрению впредь лишь путей, проходящих через менее заторможенное число). Шаги выбора могут проводиться периодически (например, один раз на k итераций) или зависеть от возникающего тормоза (например, при переходе max ue(i)-e(-i)u через какой-то порог). Окончательно заторможенное число может выбираться по максимальному перепаду между e(i) и e(-i), или по максимальной заторможенности, или еще каким-нибудь способом. Во всяком случае, задание данного итеративного метода состоит в указании R, L, начального приближения, критерия применения шага выбора и критерия выбора заторможенного числа. Описание некоторого конкретного итеративного метода, подвергавшегося экспериментальной проверке, содержится в § 3.

Теоретическое исследование сходимости итеративных методов носит пока фрагментарный характер, касаясь отдельных классов матриц. Достаточно полно изучены матрицы размерности 2`m (этот случай, как известно, составляет класс полиноминального разрешения по выполнимости). Для этого класса оператор K R,L оказывается линейным.

Теорема. Пусть А — имеющая решение задача размерности 2`m для любых ненулевых R, L и начального приближения последовательность итераций оператора K R,L сходится по направлению к такому тормозу, что любое максимально заторможенное им число может быть заменено в А нулем, а задача не потеряет решения.

3. Эксперимент

Содержательный смысл оператора K R,L подсказывает, что регулирование шагов выбора на основе k-кратного применения K R,L представляет собой определенную аппроксимацию стратегии увеличения свободы выбора (УС - стратегии), предложенной в [17]. Эта аппроксимация тем точнее, чем больше k. Уже самая простая из этих аппроксимаций (при k=1) показала свою высокую эффективность в машинном эксперименте по распознаванию выполнимости [7]. Эксперимент посвящен следующей конкретизации итеративного метода: шаг выбора используется каждый раз после однократного применения оператора K0,1 к тормозу, состоящему из единиц. В качестве окончательно заторможенного числа выбирается любое из таких чисел i, что e(i) максимально превышает e(-i) (при равном перепаде выбирается более заторможенное) .

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

Эксперимент состоял из двух этапов. На первом этапе рассматривались случайно порожденные матрицы с параметрами 3`30 и n=7 (параметры были подобраны в предварительном эксперименте для получения матриц с малым числом путей). Было порождено 64 матрицы, из них 59 оказались имеющими решение. Во всех 59 случаях основной вариант нашел решение. Во вспомогательном варианте было только два случая, когда один из последних выборов был совершен неправильно (и в этих случаях «запас надежности», предусматриваемый перестраховочным вариантом, не позволил бы потерять решение). Перехода к перебору путей не произошло ни разу.

На втором этапе рассматривались матрицы, соответствующие задаче раскрашиваемости в три цвета графов Петерсена [18] и результатов случайного выбрасывания из этих графов (ребер) (18). Рассмотрены все графы от Р (5,2) до Р (8,5), для каждого из них выбрасывалось от 0 до b ребер (b второй из параметров графа P(a,b). Проверялся перестраховочный вариант, который во всех случаях довел исходную матрицу до двухстрочечной (т. е. до полиномиально разрешимого класса) и ни разу не потерял выполнимости. Отдельно исследован граф Р (43, 13), раскрашиваемость которого не смогла установить рекордная по своим возможностям программа Г.Е. Минца [18]. И в этом случае перестраховочный вариант привел к нахождению раскраски (он остановился на выполнимой формуле, имеющей лишь два трехчленных столбца и 174 двучленных).

4. Обсуждение

Шаг выбора представляет собой на самом деле однократное применение расщепления [20, 21] с переходом на одну из ветвей. В этом смысле беспереборный алгоритм итеративного метода является вырожденным случаем перебора в методе расщеплений с назначенными предпочтениями путей. Учитывая все сказанное, понятно, какова возникающая модель взаимодействия полушарий.

Собственно правополушарный механизм итеративного «углубления в смысл» целостного объекта моделируется итерациями оператора K R,L. В более благоприятных случаях непосредственной сходимости к тормозу, определяющему решение, возникает эффект «интуитивного прокола»—неограниченное возбуждение проходит по пути, отмеченному минимальными заторможенностями, не встречая препятствий (эффект «короткого замыкания»). В менее благоприятных случаях узнавание откладывается в связи с необходимостью некоторых переборных шагов (т.е. некоторых действий механизма левого полушария). При этом перебор регулируется предпочтениями, накопленными в очередном тормозе (т. е. возникшими в ходе работы правополушарного механизма). Это разделение труда полностью соответствует модели взаимодействия полушарий в организации переборов, как она изложена в [6, с. 40].

Единственная особенность правополушарного механизма из числа упомянутых, не отраженная пока что в модели, — это возможность возникновения «промежуточных смыслов». Для моделирования этой особенности, видимо, лучше всего подходит не задача распознавания выполнимости, а двойственная—распознавание тавтологичности. Однако такая постановка задачи связана со значительными математическими трудностями, известными под названием проблемы равенства классов NP- и NP -задач.

§ 3. ОППОЗИЦИЯ «ЛЕВОГО» И «ПРАВОГО» В ПОЗНАВАНИИ

Сказанное в предыдущих параграфах может быть просуммировано в виде таблицы:

Таблица 1. Особенности познавательных механизмов

Следует еще отметить, что для левого полушарного механизма характерно рациональное осмысление своей деятельности, для правого—эмоциональная мотивация. Оппозиция пополняется противостоянием разум — чувство. B связи с этим важный материал может быть получен при изучении познавательных возможностей эмоций—эти возможности определенно смыкаются с правополушарными по показателям субъективности, неосознанности, нерасчлененности реакций и др., а также по тяготению к подкорковым и вообще более древним механизмам. С этим хорошо согласуются, в частности, интересные эксперименты, описанные в [29]. В этих экспериментах фиксируется, например, большая роль эмоций при попытках реорганизации наличных ситуаций [22, с. 87], опережения эмоциональной активацией процесса вербализации, особенно при формировании гипотез (с полным отсутствием такого опережения при оценивании уже сформированных гипотез [22, с 100 — 104]) и др.

1. Гносеологические предпочтения

Приблизительное ощущение областей плодотворности и границ возможностей каждого из механизмов, пройдя через эмоциональную составляющую личности, приводит к формированию достаточно заметных гносеологических предпочтений, соответствующих той же оппозиции. Важнейшие из этих предпочтений сведены в табл. 2, из которой, в частности, вытекает, что «левый» механизм предпочитает догматизировать законы дедуктивной системы, рассматриваемой в данный момент. «Правый» механизм, напротив, склонен догматизировать «данность» рассматриваемого явления, что вполне согласуется со «своевольным» отношением к моделирующей эту данность системе.

Таблица 2. Система гносеологических предпочтений

Собственно, с этим и связана сама возможность переходить к новым, все более адекватным исчислениям. Поэтому достоинством левополушарного механизм является возникновение новой содержательной реальности на каждом «этаже» башни дедуктивных систем, а недостатком — некоторый догматизм и прекращение дальнейшего подъема. Достоинством правополушарного механизма является осознание подчиненного значения каждой конкретной модели («не сотвори себе кумира»); характерным недостатком — склонность к построению все более утонченных толкований одного единственного замкнутого в себе текста.

Замечание 4. Логика формирования этой системы предпочтений может быть уточнена в терминах фундаментальных эвристик ([23, 24]; некоторые математические аспекты освещены также в [25]). Комплексы таких эвристик определяют методологию и гносеологию мировоззренческих систем; многие из пар противостоящих друг другу эвристик находятся в той же оппозиции «левого» и «правого» механизмов (в этом легко убедиться сравнивая табл. 2 со списками пар из [23] и [24]). В рамках этой же оппозиции лежит известное противопоставление рационализма и интуитивизма правополушарного и левополушарного механизмов, а внутри науки — рационализма и эмпиризма.

2. Общесистемные параллели асимметрии

Хотя функциональное различие «левого» и «правого» механизмов декларировалось выше как фундаментальное свойство процессов познания и вообще развития, почти весь материал относился лишь к организации познания человеческим мозгом. Поэтому сказанное поддерживает пока лишь психологический и, в меньшей степени, — социопсихологический аспекты дальнейшего рассмотрения. Эта поддержка кажется более или менее убедительной, однако не повредит дополнить ее некоторыми аргументами общей теории систем.

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

Основную роль при этом играет известное противопоставление корпускулярных (популяционных) и жестких систем [26]. Легко видеть, что развитие корпускулярных систем соответствует движению «по горизонтали», а возникновение жесткой системы следующего уровня на базе корпускулярной — функции «подъема». Чередование обоих принципов построения систем (например, в рамках одного биологического организма [26, с. 16—17]) вполне соответствует возникновению «башни» исчислений. Эволюционный аспект этого чередования является выражением упоминавшейся и важной для дальнейшего попеременности деятельности левополушарного и правополушарного механизма. Ряд рассматривавшихся параметров оппозиции «левого» и «правого» механизмов — и таких очевидных, как разделенность — целостность, анализ — синтез, и таких существенных, как локальность — глобальность обработки информации (вспомним, что информация — мера упорядоченности системы) — подтверждает ту же аналогию.

Противопоставление добровольно-договорных единств в обществе и их жестких исторических наследников оказывает большое влияние на ход исторического процесса; соответствие этого противостояния нашей оппозиции используется в дальнейшем.

Для рассмотрения этих вопросов представляют интерес модификации понятий m- v-связи [27, с. 100—103], изучение механических и других модельных примеров систем с различными типами связей, теоретико-алгоритмические результаты о «сколь угодно сильном» замедлении функционирования систем при жесткой фиксации связей (см. нарушения условия монотонности в [17]).