Главная > Распознавание образов > Лекции по теории образов: Регулярные структуры
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Примечания

1.1.А. Теория статистического вывода для нетрадиционных выборочных пространств будет подробно развита в книге автора «Абстрактный статистический вывод». Эта теория возникла, главным образом, в связи с проблемами, встречающимися в выводе образов.

1.2.А. Рис. 1.2.1 заимствован из книги . Б. Некоторые математические результаты, полученные в этом

направлении, можно найти в См. также гл. 5 данного тома.

В. Соответствующий конкретный пример можно найти в томе I, разд. 3.7.

Г. Таксономия — наука, посвященная разделению объектов на «осмысленные» группы, — насчитывает длинную историю. В монографии приводится следующая старинная китайская таксономия:

Животные подразделяются на:

а) принадлежащих Императору,

б) бальзамированных,

в) прирученных,

г) молочных поросят,

д) сирен,

е) сказочных,

ж) бродячих собак,

з) включенных в настоящую классификацию,

и) буйствующих, как в безумии,

к) неисчислимых,

л)) нарисованных очень тонкой кисточкой из верблюжьей шерсти,

м) и прочих,

н) только что разбивших кувшин,

о) издалека кажущихся мухами.

Европейская биологическая таксономия восемнадцатого века не столь восхитительна, но, вероятно, более научна.

2.1.А. Нет необходимости в том, чтобы связи были ориентированными. Если они ориентированны, то мы говорим об ориентированной регулярности, в противном случае—о симметрической регулярности. Эта тема будет развита в гл. 3.

2.2.А. Если регулярность — симметрическая, то мы не говорим «от входных связей к выходным связям».

Б. Функцию А называют принимающей функцией.

В. Мы часто будем допускать, что деревья, вопреки общепринятой практике, имеют ориентированные дуги.

2.4.А. Дополнительные подробности можно найти в гл. 2.

Б. См. т. I, гл. 4.

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

Глава 3 основывается на ряде работ Гренандера (Grenander 1977 а, с, d, е, f]).

В данном томе мы всегда будем считать, что преобразования подобия образуют некоторую группу.

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

Б. Множество соединителей может задаваться косвенно, посредством 31, как это происходит в случае соединителей а, которые вводятся как или непосредственно — как явным образом определенные множества Какой именно, способ задания используется, будет ясно из контекста.

В. Этот соединитель отличается от предыдущих тем, что он зависит также и от показателей связи.

3.4.А. В старой алгебраической литературе часто предполагалось, что гомоморфизм является сюръективным, однако, в современном употреблении термин гомоморфизм сюръективности не предусматривает. Естественно, выбор того или иного варианта употребления — это лишь вопрос удобства. Мы придерживаемся второго варианта.

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

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

3.7. В этом разделе мы пользовались понятием алгебры подизображений алгебры изображений множество должно являться некоторым подмножеством для любого если

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

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

Утверждение о принадлежности или непринадлежности пустой конфигурации 0 к представляет собой свойство типа соединения. Роль пустой конфигурации аналогична роли пустой цепочки формального языка. В сущности, вопрос удобства —

допускать или не допускать вхождение 0 в Отметим, что

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

Б. Понятие отношения конгруэнтности, очевидное в случае универсальной алгебры, становится менее «устойчивым» в том случае, когда некоторые из основных операций алгебры являются лишь частично определенными, а именно этот случай представляет для нас наибольший интерес. Мы рекомендуем читателю познакомиться с монографией Гретцера (Gratzer 1968), с. 79—99, знание этого материала ниже предполагается. Если рассматривается некоторая базисная операция а, связывающая конфигурации с, и в некоторую регулярную конфигурацию с, а конфигурации — в некоторую регулярную конфигурацию с, то в этом случае мы требуем выполнения условия . Следовательно, наше понятие правила идентификации соответствует «конгруэнтности», а не «сильной конгруэнтности». Для базисной операции это различие не является необходимым, поскольку конфигурация с регулярна в том и только в том случае, если регулярна , когда преобразования подобия образуют некоторую группу, что в данном томе всегда предполагается.

В. В данном томе мы пользуемся ослабленным понятием гомоморфизма для того, чтобы допустить существование отображений между пространствами с различными глобальными регулярнос-тями. В этом же духе представляется естественным обобщить определение 3.1.1 из первого тома, опустив или, по меньшей мере, ослабив условие (II). Эта возможность нами не изучалась.

Г. Определение 3.7.1 расширяет соответствующее определение, введенное в первом томе, допуская изменение соединителей при применении к ним отображения.

3.8.А. Случай фиксированной глобальной регулярности являлся единственным допускавшимся определениями гомоморфизмов, которые использовались в первом томе и отчете автора (Grenander 1977а).

Б. В определении использовавшемся раньше, указывалось, что оно является изоморфизмом в том случае, когда оно гомоморфно и биективно. Мы теперь требуем также, чтобы гомоморфным, а это вынуждает нас пользоваться более сильными допущениями, для обеспечения справедливости теоремы 3.8.2.

В. Следует отметить, что здесь предусматривается использование сильного правила идентификации.

Часто возникает вопрос о допустимости рассмотрения 0 как некоторой регулярной конфигурации и, следовательно,

как изображения. Если тип соединения то дело будет обстоять именно таким образом, однако, в общем случае — выбор того или иного ответа — это вопрос удобства.

Б. Может оказаться целесообразным изменить определение 3.9.1 таким образом, чтобы запретить комбинации в которых одно из изображений является условной единицей. В настоящее время не ясно, к каким последствиям может привести такое изменение.

В. Определение (3.9.16) выглядит оправданным, однако, возникает вопрос, не содержит ли условных единиц См. также замечание, следующее за доказательством теоремы 3.9.2.

Если топологию, заданную на можно описать

с помощью некоторой метрики и если неполна, то можно продолжить в некоторое метрическое полное пространство и возникает задача определения свойств многочленов на по аналогии с приведенной выше теоремой. Мы этот вопрос еще не изучали.

Напомним читателю, что вероятностная мера на индуцирует другую меру Р, на через соотношение

где Е — борелевское множество в Г.

Б. Первое серьезное изучение управляемых вероятностей было проведено в работе (Grenander 1967 b).

В. Постоянная играет роль, аналогичную функции распределения в статистической механике.

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

Зафиксируем и состав пронумеруем пары связей как обычно двойным индексом Рассмотрим подмножество множества такое, что для каждого к существует не более одного для которого и аналогично для каждого Мы разрешаем замыкаться только парам из но они также могут оставаться открытыми.

5.2.А. Результаты, содержащиеся в теоремах 5.2.1 и 5.2.2, были получены в ходе совместных исследований, проведенных несколькими членами семинара по теории образов.

Б. Доказательство леммы 3 представляет собой упрощенную версию результата, принадлежащего Трифту (Thrift 1977). Это упрощение было проведено С. Джеманом. Теорему 5.2.3 можно

доказать также при помощи методов, представленных в работе (Suomela 1976).

5.4.А. Согласно теореме Шеффе, если почти наверное и если

то соответствующие меры сходятся в слабом смысле к Р, где

— см. книгу (Billingsley 1968).

Есть интересная идея — применить к бесконечным конфигурациям методы нестандартного анализа, однако эта возможность не была исследована.

Б. Результаты, имеющие отношение к этому вопросу, читатель может найти в работе (Kree, Tortrat 1973).

5.7.А. Подмножество множества Т называется конфинальным, если для любого элемента существует элемент у такой, что у

Б. Под копиями о мы понимаем объединение из , взятого раз.

В. Если Е — замкнутое подмножество при любых то отсюда следует, выпуклое. Покажем, что это так. Рассмотрим отрезок прямой от к у. Отобразим его линейно на [0, 1] на вещественной прямой. Тогда любая точка на исходном отрезке, которая соответствует конечному двоичному разбиению на [0, 1], принадлежит Е, в чем можно убедиться, проводя повторное деление пополам. Отсюда следует выпуклость, так как Е замкнуто.

Понятие маргинального множества в пространстве конфигураций было введено в работе с)

Теоремы были взяты из (Grenander 1977b и 1978а). Рассуждения принадлежат Хуангу (Hwang).

Б. Соотношение (5.15.112) по-видимому представляет собой известный факт, но нам не удалось найти его в литературе.

Имеется обширная литература о формировании гипотез в рамках искусственного интеллекта. В книге Нильсона (Nilsson 1971) можно найти ссылки на многие работы этого направления.

Оригинальный подход был применен в работе (Hajek, Havranik 1978).

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

6.3.А. Можно было бы также ввести образующие что означает непрерывные распределения на множестве в таком случае Р был бы показателем выходной связи.

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

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

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

К нашему пространству образующих можно добавить определенные изображения, выступающие в роли макрообразующих. Например, образующая с ее первой входной связью, ведущей к и второй — к означает все нормальные распределения и такая образующая конечно, полезна. Она обладает арностью единица, лишь единственная выходная связь соответствует

Изоморфизм, установленный в теореме, по-видимому связан с правилом идентификации, которое отождествляет конфигурации с одинаковыми выходными связями и одинаковыми моментами первого и второго порядков (при фиксированных входах). Эта мысль не получила развития. Эту ситуацию можно сравнить с той ситуацией, в которой работает теорема 3.8.1.

7.1.А. Результаты гл. 7 взяты из работы (Grenander 1978с).

7.3.А. Программа была написана П. Фланаганом.

8.1.А. Читатель, желающий познакомиться с современными тенденциями в количественной таксономии, может обратиться к работам и .

9.2.А. Описанная ниже интерпретация в значительной степени объясняется влиянием гл. 5 из книги и работы (von Wright 1957), с. 134—154.

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

9.3.А. Принять или не принять это очень строгое определение равенства равносильно решению вопроса о тем, какими должны быть координаты — абсолютными или относительными. В последнем случае мы идентифицируем конфигурации при помощи правила, которым мы пользовались в подразделе 9.3.8.

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

Б. Следует отметить, что утверждение, согласно которому конфигурация является неприводимой, не означает, что она неприводима по модулю см. том I, с. 82.

В. Правило идентификации в подразделе 3.8.1 имеет общее значение: оно делает абсолютные координаты относительными.

Г. В этой алгебре изображений образующие могут быть идентифицированы для конфигураций, составляющих любое заданное изображение.

9.7.А. Представляющее некоторый интерес ослабление определения 9.7.1 заключается в том, чтобы новые соединения, установленные любым связывали старые образующие. При этом мы не требуем, чтобы все новые выходные связи немедленно замыкались. В таком случае лемма 9.7.1 становится неприменимой.

9.8.А. Теорема справедлива только для биективных отображений, однако есть основания полагать, что метод доказательства можно применить также и в небиективном случае.

Б. Утверждение о том, что высокие уровни абстракции, по-видимому, приводят к отсутствию инъективности, основано лишь на исследовании некоторых частных случаев. Его не следует принимать на веру.

<< Предыдущий параграф Следующий параграф >>
Оглавление