§ 8.6. Выпуклые множества

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

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

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

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

Точка х выпуклого множества называется его крайней точкой, если х не лежит внутри никакого отрезка прямой, соединяющей две точки из Каждая крайняя точка лежит на границе но если граница содержит линейные куски, то не всякая ее точка является крайней.

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

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

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

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

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

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

Рис. 8.4. Выпуклое множество G..

Эта прямая вертикальна в каждой точке между она горизонтальна во всех точках между у нее отрицательный наклон, на участках между и между Уравнение опорной прямой во всех этих случаях имеет вид , где и