§ 4.7. Дискретные алгоритмы обучения

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

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

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

Таблица 4.1.

№	Функционал	Алгоритм	Примечания	Авторы
1				Айзерман М. А. Браверман Э. М. Розоноэр Л. И. Якубович В. А.
2				Айзерман М. А. Браверман Э. М. Розоноэр Л. И.
3			L-оптимальность по В. А. Якубовичу	Айзерман М. А. Браверман Э. М. Розоноэр Л. И. Якубович В. А.
				Блайднон Ч. Хо Ю.
4			- оператор случайного испытания с двумя исходами: 1 – с вероятностью , -1 – с вероятностью	Айзерман М. А. Браверман Э. М. Розоноэр Л. И.
5		;		Ванник В. Н. Лернер А. Я. Червоненкис Л. Я.

При отсутствии помех, как мы уже упоминали,  можно выбирать постоянной, не нарушая сходимости алгоритмов. Алгоритмы 1—3 соответствуют детерминированной задаче обучения, а алгоритм 4 — вероятностной задаче обучения.

Подчеркнем, что функционал, порождающий этот алгоритм, является случайной величиной, так как  — оператор случайного испытания с двумя исходами (несимметричная монета): 1 — с вероятностью  и (—1) — с вероятностью .

Когда принадлежность показанного образа какому-либо классу достоверно известна учителю, функционал 4 совпадает с функционалом 1, и вероятностная задача переходит в детерминированную. Если же эта принадлежность известна учителю только с некоторой степенью достоверности, то в качестве критерия можно взять средний квадрат отклонения

.                    (4.20)

В этом случае алгоритм обучения будет совпадать с алгоритмом

.   (4.21)

Знание функционалов дает возможность сравнивать алгоритмы между собой. Некоторые алгоритмы, например, не совсем удачны. Это относится к алгоритмам 1 и 4, для которых соответствующие функционалы не являются выпуклыми по  и для нулевого значения вектора  дают второй минимум, равный нулю.

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

Отметим в заключение, что в таблице приведены в основном дискретные алгоритмы, за исключением алгоритмов 5. Об этих непрерывных алгоритмах мы скажем подробнее в § 4.9.