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

8.2. Логика образов таксономической близости

Пусть на плоскости даны две точки Соединим их кривой Г класса не содержащей двойных точек, длина дуги которой (здесь не обозначающая преобразования подобия) измеряется от 2, при s = 0 до , где «длина Г».

Рис. 8.2.1

Разделим Г на равновеликих дуг точками так что Введем локальную систему координат, как показано на рис. 8.2.1, где локальная ось у направлена по нормали к кривой, и образуем множества

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

При заданной непрерывной плотности (это будет подразумеваться в настоящей главе) неоднородного пуассоновского

случайного процесса нужно вычислить вероятность того, что каждое пробное множество содержит по крайней мере один объект:

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

Чтобы изучить поведение (8.2.2) в пределе, когда параметры стремятся к бесконечности, нужно подходящим образом нормировать это выражение для получения осмысленного и невырожденного предела. Чтобы понять асимптотическое поведение (8.2.2), заметим, что асимптотически ведет себя как умноженное на интеграл от вдоль дуги между и Эта дуга будет обозначаться если в качестве меры выбрать длину дуги, то По форме (8.2.2) напоминает интегралы-произведения, так что естественно взять логарифмы и нормировать их. Соответствующее выражение есть

где 9 обозначает разбиение Г на дуги и символ используется теперь в ином смысле:

Величина по построению неотрицательна. Если окажется, что некоторое то естественно приписать значение Пусть причем при т. е.

Заметим, что наш функционал можно записать в виде

Докажем теперь основной предельный результат.

Теорема 8.2.1. Поведение функционала где есть разбиение описывается следующей альтернативой:

Замечание. В важном частном случае, когда не принимает малых значений, можно аппроксимировать функционал в (8.2.6) выражением

для некоторых целей такое приближение достаточно.

Доказательство. Чтобы изложить существенные идеи доказательства с максимально возможной ясностью, мы разобьем его на ряд лемм. Заметим, что (8.2.5) имеет смысл не только для разбиений более общего вида, не обязательно состоящих из интервалов, задаваемых длиной дуги но также и для произвольных борелевских множеств Е, - с положительной мерой Лебега при той же естественной интерпретации случая, когда какая-либо функция множества оказывается нулем. Пока что мы исключим этот тривиальный случай.

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

Лемма 1. Если Е есть объединение двух непересекающихся борелевских множеств то

Доказательство. Рассмотрим функцию

Поскольку выпукла, то для

Полагая

получаем

что доказывает (8.2.8).

Из этой леммы следует, что если есть измельчение разбиения то

а это и есть свойство монотонности, отмеченное выше.

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

Лемма 8.2.2. Если то для выполняется

Доказательство. Поскольку среднее геометрическое не превосходит среднего арифметического, то

Для малых положительных и справедливо неравенство так что

Из (2.15) и (2.16) получаем

но поскольку интегрируема, то

что доказывает лемму.

Отсюда ясно, что не нужно беспокоиться о поведении вблизи нуля, пока есть интегрируемая функция. Если же она неинтегрируема, то ситуация становится совершенно иной, но мы отложим обсуждение этого вопроса до леммы 8.2.4. Сначала рассмотрим то, что можно назвать случаем, когда плотность ведет себя хорошо, а именно вторую возможность из указанных в теореме 8.2.1.

Лемма 8.2.3. Если отграничена от нуля, т. е. для всех то выполняется предельное соотношение

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

Доказательство. Введем функцию для данного разбиения

так что наш критерий можно записать в виде

Но неотрицательные функции равномерно ограничены константой:

поскольку в силу теоремы о среднем значении

При измельчении разбиения получаем предел

так что

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

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

Лемма 8.2.4. Если что возможно лишь при расходимости интеграла от т. е. если

то

Доказательство. Рассмотрим функции введенные при доказательстве леммы 8.2.3. Мы по-прежнему получаем (8.2.24), но теперь не можем продолжать те же рассуждения. Вместо этого воспользуемся леммой Фату, из которой следует,

что выполняется (2.2.25). Действительно,

это неравенство следует истолковывать как обычно, если интеграл расходится. Он и в самом деле расходится, поскольку

что доказывает утверждение леммы.

Неравенство (8.2.29) было использовано для доказательства тою, что если то его можно обобщить и показать, что последнее утверждение справедливо и в обратную сторону

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

Если есть разбиение на множества осуществляемое точками то пусть будет разбиением на множества Тогда, согласно (8.2.13),

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

где

Значение равное можно рассматривать с помощью

небольшой модификации доказательства леммы 8.2.3. Итак,

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

что вместе с (8.2.34) завершает доказательство теоремы.

Теперь можно продвинуться дальше и задать такой вопрос: что произойдет, если принять более «осторожную» индуктивную логику образования таксона? Если потребовать не только того, чтобы ни одно не было пустым, но чтобы каждое из них содержало по крайней мере наблюдаемых объектов, то в (8.2.5) вместо простого экспоненциального выражения вида нужно будет использовать пуассоновскую вероятность

Это приводит к следующей предельной теореме.

Теорема 8.2.2. Поведение величины при условии, что в каждом пробном множестве содержится по крайней мере объектов, подчиняется следующей альтернативе:

где есть неполная гамма-функция.

Доказательство практически то же, что и в теореме 8.2.1, за исключением вида подынтегрального выражения, которое теперь заменяет и может быть выражено через неполную гамма-функцию:

Заметим, что особое условие (условие сингулярности) в альтернативе теоремы остается прежним: независимо от

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

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

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

Тогда получаем совершенно иной результат.

Теорема 8.2.3. При данных условиях функционал

где означает событие, описываемое неравенством (8.2.39), ведет себя асимптотически в соответствии со следующей альтернативой:

Доказательство. Теперь функционал принимает вид

где означает вероятность обнаружить по крайней мере объектов в пробном множестве принадлежащем разбиению Как н ранее, мы начали полосы шириной требуя, чтобы каждая пробная площадь содержала по крайней мере объектов, и затем устремили к нулю при стремлении к бесконечности (см. соотношение (8.2.40)).

Изучим асимптотическое поведение в окрестности точки на пути Г, для которой Оценим пуассоновскую вероятность

Заметим, что в процессе стягивания к точке выполнается соотношение Теперь воспользуемся хорошо известной границей:

где последняя величина (8.2.45) стремится к при стягивании к Следовательно, с помощью формулы Стирлинга получаем следующую асимптотическую оценку для

Итак, можно асимптотически ограничить снизу выражением

которое стремится к при Отсюда следует первая часть доказываемой альтернативы: если на части пути Г существует такая точка для которой то

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

где есть наибольшее целое число . Следовательно, опять применяя формулу Стирлинга, получаем верхнюю границу для с иной константой, но в других отношениях такую же, как и в (8.2.45) -(8.2.46):

Следовательно,

где Но правая часть неравенства (8.2.50) стремится к нулю при что доказывает вторую часть альтернативы.

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