§ 2. Геометрическая интерпретация задачи

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

Поставим в соответствие каждому изображению, которое может быть «показано» машине в ходе обучения или экзамена, точку некоторого пространства. Это соответствие может быть установлено различным образом. Можно, например, ввести в рассмотрение -мерное пространство, если считать, что фотополе машины состоит из фотоэлементов и что состояние фотополя полностью определяется числами — состояниями каждого из фотоэлементов. Проецирование какого-либо изображения на фотополе приводит все его элементы (а значит, и фотополе в целом) в некоторое состояние, т. е. определяет точку в так введенном пространстве.

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

Пространство, точкам которого соответствуют различные объекты, подлежащие классификации, назовем рецепторным пространством и обозначим через X. Образ — множество таких объектов (изображений). Поэтому образу в пространстве X соответствует множество точек (область). Если утверждается, что при показе изображений человек может однозначно отнести их к одному из двух (или нескольких) образов, то тем самым утверждается, что в пространстве X существуют две (или несколько) области, не имеющие общих точек, и что показываемые изображения — точки из этих областей. Каждой такой области можно приписать наименование, которое придано соответствующему образу. Так, например, всему бесконечному разнообразию начертаний буквы «а» соответствует в пространстве X область «рукописная буква а», а каждому конкретному начертанию этой буквы — точка из этой области. Аналогично обстоит дело с точками, соответствующими различным буквам «о» и областью «рукописная буква о». Области «рукописная буква а» и «рукописная буква о» не имеют общих точек друг с другом так же, как и нет у них общих точек с областями «мужской портрет», «пейзаж» или «цифра 5», но область «рукописная буква а» является частью области «рукописные буквы». В этом смысле области, соответствующие образам, не обязательно «связные», так, например, область «рукописные буквы» состоит из совокупности ряда областей, не имеющих между собой общих точек.

Проинтерпретируем теперь в терминах этой геометрической картины процесс обучения распознаванию образов с учителем, ограничившись пока, как это делалось и в § 1, случаем распознавания двух образов, например, образов «буква а» и «буква о».

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

областей, и сообщается информация о том, к какой области предъявленные точки принадлежат. Никакой дополнительной информации об этих областях, т. е. о расположении их границ, в ходе обучения не сообщается. Цель обучения — построить поверхность, которая разделяет не только показанные точки, но и все остальные точки, принадлежащие этим областям. Иначе говоря, цель обучения — построить функцию над точками х пространства X такую, которая, например, положительна не только на показанных, но и на всех точках из области «буква а» и отрицательна на всех точках из области «буква о». В связи с тем, что эти области не имеют общих точек, всегда существует множество таких разделяющих функций. В результате обучения должна быть построена какая-либо одна из них. В ходе экзамена машина относит предъявляемые точки к областям «буква а» или «буква о», в зависимости от того, по какую сторону от разделяющей поверхности они лежат, т. е. в зависимости от знака функции в этой точке.

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

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

пересекает эту поверхность и вместе с тем содержит все показанные точки. Напомним, однако, что задача о приближении функции по информации о ней в ограниченном множестве точек, существенно более узком, чем все множество, на котором функция задана, является обычной математической задачей об аппроксимации функций. Разумеется, решение таких задач требует введения известных ограничений на класс рассматриваемых функций; выбор этих ограничений зависит от характера информации, которая может быть использована при аппроксимации. Так, например, если заранее известно, что подлежащая аппроксимации функция представима разложением в ряд по какой-либо системе функций то задача сводится к определению коэффициентов этого ряда, т. е. для аппроксимации функции, заданной на континуальном множестве, надо определить лишь счетное множество чисел, а, значит, для этого достаточно информации о функции в счетном множестве точек. Если можно заранее предположить, что искомая функция представима конечным рядом, то для ее аппроксимации надо определить конечное число коэффициентов разложения, и принципиально достаточно информации, касающейся конечного числа точек. Эти простые примеры показывают, что задача аппроксимации разделяющей поверхности по информации об ограниченном числе точек из подлежащих разделению областей может быть решена, если ввести разумные ограничения на класс функций, которому принадлежит подлежащая аппроксимации разделяющая функция.

Интуитивно ясно, что аппроксимация разделяющей функции будет задачей тем более легкой, чем более «компактны» и чем более «разнесены» в пространстве области, подлежащие разделению. Так, например, в случае, показанном на рис. 3, разделение заведомо более просто, чем в случае рис. 4. Действительно, в случае рис. 3 области могут быть разделены плоскостью, и даже при значительных отклонениях в определении коэффициентов ее уравнения эта плоскость продолжает разделять области; в случае же рис. 4 разделение осуществляется «вычурной» поверхностью, и даже незначительные отклонения в ее форме приводят к ошибкам разделения. Имея

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

Рис. 3.

Рис. 4.

Этим интуитивным представлениям в следующих главах будет придан точный смысл.

Ограничиваясь пока указанным выше интуитивным пониманием компактности, можно перейти к Геометрической трактовке не только детерминистской, но также и вероятностной задачи обучения. В этом случае уже не утверждается наличие в пространстве областей, подлежащих разделению. С каждой точкой пространства связывают два числа: вероятность (степень достоверности) того, что эта точка есть «а», и того, что она есть «о». Предполагается, что две функции — указанные степени достоверности — существуют во всех точках пространства X, но что они не известны заранее. Далее в процессе обучения появляются случайно точки и учитель относит их к «а» или «о» именно с этой вероятностью. Задача состоит в восстановлении функций во всем X, т. е. вновь ставится аппроксимационная задача.

Компактность в этом случае означает, что функции в интуитивном смысле достаточно просты, не «вычурны», «грубы».

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

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

Вернемся опять к задачам распознавания образов. Интуитивные представления о компактности позволяют дать геометрическую интерпретацию и процессу обучения без учителя. В этом случае мы предполагаем лишь, что в пространстве X объективно существуют несколько компактных областей. Число областей либо известно, либо заранее не известно, и при появлении случайных точек из этих областей нет информации о том, к какой области показываемые точки принадлежат. В силу того, что точки принадлежат компактным областям, они будут «ложиться» в пространстве X «кучно», и процесс обучения без учителя может быть понят так: в пространстве X расположено несколько «кучных» множеств точек; требуется, наблюдая лишь расположение точек в пространстве, установить этот факт, определить число таких «скоплений» (если оно заранее не известно) и построить поверхность, которая разделяет их таким образом, чтобы

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