Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 182
Скачиваний: 4
§ 13. ПРИЛОЖЕНИЕ К ГЛАВЕ ХІѴ |
341 |
Теорема П.5. Пустъ функция F (х) дифференцируема и вы пукла. Если в точке х0, удовлетворяющей неравенствам
(щ, fi) > 4 (£ = 1 , 2 , . . |
п), |
выполняются условия (П.12), т. е. существуют такие Xit что
VF (х0) = 2 Ѵ і,
((»о. U) — ci) = 0,
то точка хп доставляет условный минимум функции F (х) при ог раничениях
(*, ft) > et . |
(П.15) |
Д о к а з а т е л ь с т в о . Пусть х0 — точка, о которой гово рится в условии теоремы. Если теорема неверна, то найдется точка Xi, удовлетворяющая (П. 15), такая, что
*■(*!)< f(*o). |
(П.16) |
Рассмотрим отрезок
X = х0 + X (хі — х0) при 0 ^ X ^ 1.
Всилу выпуклости допустимой области этот отрезок целиком лежит
впределах ограничений. Кроме того, из выпуклости F(x) следует
(см. § 2 главы IX), что
F (хі) — F (х0) > (хі — х0) V F (*„) |
|
||
и, следовательно, |
|
|
|
(-Ѵ Е (*„),. (и - |
*„)) > |
0. |
(П.17) |
Как и раньше, будем считать, |
что от |
1 до р |
занумерованы |
те ограничения, которые достигаются в точке х0, т. е.
(*о, fi) = Ч (1 < і < р),
(*о. /) > Ч (Р + 1 < £ < п).
Тогда, поскольку отрезок хі -*■ х0 целиком лежит в пределах ог раничений, имеем
(хі — х0, fi) ^ 0 (1 ^ і < р). |
(П.18) |
Из (П.17) и (П.18), учитывая замечание к теореме П.З, получаем, что вектор — ѴЕ (х0) не является базовым в системе
F (#о), /і> • • ■» /р
р
и, следовательно, не существует представления VF (хи) = ^
І=1
(Xt 0) в противоречии с условием теоремы. Теорема доказана.
3.Пусть точка х0 удовлетворяет системе ограничений Г:
(fi, х о) = Ч (1 < £ < р),
(Іі, хо) > сі (Р 4- 1 < £ < п),
т. е. первые р ограничений достигаются в точке х 0•
342 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ
Назовем единичный вектор <р допустимым направлением в
точке х, |
если существует t > 0 такое, что (х0 -|- срт) С Г при |
О < X ^ |
t. Нетрудно убедиться, что допустимыми в х0 являются те |
и только те направления ср, для которых выполняются неравенства
(Ф,/і) > 0 (1
Условный градиент в точке хп определяется так. Прежде всего, находится направление ф0 наибольшего возрастания функции среди допустимых, т. о.
(Ѵ/,’-фо)= max (VF, <p),
IФ|=i
где максимум берется по допустимым направлениям. При этом мо жет оказаться, что
(V F-фо) ^ 0.
Это означает, что по всякому допустимому направлению функция
не возрастает. В этом случае условный градиент считается равным
нулю.
Если же
(V F, ф0) > 0,
то в качестве условного градиента берется вектор, по направлению совпадающий с ф0, а по модулю равный (VF, ф0).
Таким образом,
|
ѴАусл |
Я>о)Фо» есл и |
( Ѵ Л Фо) |
> 0, |
|
||||
|
jo, если (VF, ф0) < |
0. |
|
|
|
||||
|
Справедлива |
теорема. |
градиент |
в точке х0 |
представим в виде |
||||
|
Теорема П.6 |
Условный |
|||||||
|
|
|
|
|
г=1 |
|
|
|
(П.19) |
причем |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
h (ѴуслЛ fi) |
= |
О |
(1 < |
i < |
p), |
(П.20) |
||
|
(VyCJIf , / i ) > 0 , |
h > o , |
|||||||
и обратно, всякий вектор, |
удовлетворяющий (П.19), (П.20), яв |
||||||||
ляется условным |
градиентом. |
Допустим, |
что |
Ѵусл F = 0; |
тогда |
||||
|
Д о к а з а т е л ь с т в о . |
||||||||
по |
теореме Куна — Таккера |
существует |
представление |
|
|||||
|
|
|
|
р |
|
|
|
|
|
и, |
следовательно, |
|
|
і=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
° = ѵу<а/ |
= ѵ^ 4-2 Vi’ |
|
(П.21) |
||||
что |
и требуется. |
|
|
|
i=l |
|
|
|
|
|
|
|
|
|
|
|
|
||
§ 13. ПРИЛОЖ ЕНИЕ К ГЛАВЕ ХІѴ |
343 |
Обратно, пусть справедливо (П. 21); в этом случае раз ложение (П.19) может задавать только нулевой вектор. Дей ствительно, пусть
ф = v f - 1] %іа,
і 1
h (Ф, /і) = О,
h > o (1 <<</»),
(ф. /і) > 0.
Тогда
(Ф, Ф) = (Vf, Ф) -4- SXj (ф, /,) = (Vf, ф).
Если при этом
(Ф, Ф) = (Vf, -Ф) > о,
то ф/|ф I есть допустимое направление, по которому функция f возрастает в противоречии с допущением. Таким образом, (ф, ф) = 0 Допустим теперь, что | VyCJIf | > 0. Тогда, как нетрудно убе
диться, направление ср0 совпадает с направлением обобщенного портрета класса X, состоящего из одного вектора V f, относитель
но класса X, состоящего из векторов —Д, . . ., |
—/р для к = 0. |
|||||
Действительно, при этом ф есть единичный вектор, на котором |
||||||
достигается максимум |
|
(V f, Ф) |
|
|
|
|
при ограничениях |
|
|
|
|
|
|
|
(fl, Ф) > о, |
|
|
|
||
|
|
|
|
|
||
причем заведомо известно, что сі (ф) > 0. |
|
вектор фо однознач |
||||
Поэтому в силу теорем, |
доказанных |
выше, |
||||
но задается разложением |
|
|
|
|
|
|
|
|
р |
|
|
|
|
|
фо= |
ctVf + 2 |
ßj/j, |
|
(П.22) |
|
|
|
j= i |
|
|
|
|
а > 0 , ß j > |
0, ß j (f j , Фо) = |
0, |
(/,-, |
фо) |
> 0. |
|
Умножим равенство скалярно на ф0: |
|
|
|
|
||
1 = (Фо, Фо) = « |
(Vf, |
Фо) + 2ßj (fj, |
фо) = |
а (V f, фо), |
||
откуда |
|
|
|
|
|
|
Поэтому |
а== |
(V f ,фо) > а |
|
|
|
|
|
|
|
|
|
|
|
VyCa f = Фо (Фо, V f) = V f + 2ß; (фо, V f)/f.
Полагая Я,г = (ф0, V f), получим разложение (П.19). Теорема доказана.
§ 1. СПОСОБЫ ПРВДСТАВЛЕНИН ИНФОРМАЦИИ |
345 |
ния числовой оси. При дискретном способе каждая коор дината вектора х может принимать лишь фиксированное число значений.
Оба способа представления информации имеют как свои сильные, так и слабые стороны.
Сильной стороной непрерывного способа является точ ность задания значений координат. Каждая координата вектора здесь равна тому значению параметра, которое было замерено. Однако при таком способе представления информации для хранения значения каждого параметра требуется одна ячейка памяти вычислительной машины. А так как в задачах распознавания ситуация описывает ся большим числом параметров (вектор х имеет размер ность порядка десятков и сотен), то хранение одной ситу ации в памяти машины требует слишком большого объема памяти. Кроме того, часто, например в задачах медицин ской диагностики, ситуации описываются признаками, которые не имеют точного количественного выражения (например, надо отразить, что у данного больного повы шена «бледность кожных покровов»). В этом случае при нят следующий способ записи такой информации. Дого вариваются, что единица означает наличие данного приз нака, нуль — его отсутствие.
Возможен способ записи информации, при котором кодируется не только наличие или отсутствие некоторого признака, но и степень проявления признака. Например, следующие характеристики: «бледность кожного покрова не выражена», «бледность кожного покрова выражена слабо», «бледность кожного покрова сильно выражена» — могут иметь соответствующие коды 100, 010, 001.
Таким образом, наличие качественных признаков опи сания объекта предопределяет дискретный способ пред ставления информации.
В задачах обучения распознаванию образов принято дискретно кодировать не только признаки, отражающие качественную характеристику объекта, но и параметры, которые принимают непрерывные значения. При этом пользуются следующим способом представления дискрет ной информации.
Весь диапазон значений параметра разбивается на ряд градаций. Единицей кодируется /-й разряд кода приз рака, если значение параметра принадлежит j-жградации;
346 г л . XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА
если же значение параметра не принадлежит /-й градации, то в /-м разряде проставляется нуль.
П р и м е р . Пусть значение параметра хі принадлежит отрез ку [—5, -4-8] и этот отрезок разбивается на пять градаций:
|
ж <[ 0; |
0 ж < 2; 2 |
ж < 4; |
4 <1 ж < |
6; х ^ 6. |
Кодом |
10000 |
обозначаются |
величины |
х < 0, |
01000 — величины |
0 < х < |
2, 00100 — величины |
2 ^ х < |
4, 00010 — величины 4 ^ |
||
< г < |
6, 00001 — величины х ;> 6. |
|
|
||
Рассмотренный дискретный способ представления ин формации замечателен не только тем, что позволяет ком пактно записывать информацию. Дискретизация вели чины X есть нелинейная операция, с помощью которой век тор X переводится в бинарный вектор х'.
Поэтому увеличение числа градаций при кодировке значения параметра эквивалентно использованию более разнообразного класса разделяющих поверхностей в про странстве X. Однако, как было установлено в первой ча сти книги, чрезмерная емкость класса решающих правил при ограниченном объеме обучающей последовательности недопустима и поэтому возникает проблема экстремальной разбивки на градации непрерывных признаков.
В этом параграфе будет приведен алгоритм опреде ления экстремальной разбивки значения признаков на градации. Принцип, который реализует алгоритм, заклю чается в следующем: необходимо так разбить значения па раметра, чтобы оценка неопределенности (энтропии) при классификации с помощью этого признака была мини мальной или близка к минимальной (оценка энтропии производится с помощью элементов обучающей последо вательности) .
Итак, пусть признак х может принимать значения из интервала [а ^ х 61 и пусть вектор, обладающий этим признаком, принадлежит одному’ из к классов. Будем считать, что существуют условные вероятности принадлеж ности к каждому классу
Р (1 I Я), . . Р ( к I X).
Для каждого фиксированного значения признака х = я может быть определена мера неопределенности (энтропия)
