Аннотация:Разумность и осмысленность решения задачи распознавания образов неявно основана на истинности некоторых эмпирических предположений относительно обучающей выборки. Одно из основных – гипотеза представительности, которая гласит, что обучающая выборка отражает закономерность, заключённую в генеральной совокупности. Эта гипотеза гарантирует принципиальную возможность построения решения задачи распознавания, но ничего не говорит о том, насколько оно может оказаться сложным в конкретном пространстве признаков. Гипотеза компактности (ГК), о которой пойдёт речь в данной работе, предполагает, что объекты разных классов некоторым образом сгруппированы в признаковом пространстве, что облегчает выявление разделяющей их закономерности. Возможность проверить, выполняется ли это предположение (сформулированное пока на интуитивном уровне), позволит оценить пригодность выбранного пространства признаков для распознавания без привлечения громоздких процедур оценки качества решения вроде скользящего контроля, например.
В работе предлагается формальный способ оценки компактности, придающий математическую интерпретацию естественным представлениям о «скученности», «сгруппированности», и позволяющий получить оценку качества текущего признакового пространства. Рассмотрен также способ построения нового пространства признаков, гарантирующего более высокую компактность, основанный на методе М. М. Бонгарда [1] решения задач с невыполненной гипотезой компактности. По этому способу решена задача прогнозирования результатов логического синтеза и проведено сравнение построенного решения с результатом, полученным для этой задачи в [2].
В разделе 1 кратко излагается суть рассматриваемой в работе проблемы и ставится основная цель, достижению которой посвящены все последующие рассуждения.
В разделе 2 проведён обзор уже существующих результатов в данной области. Освещены некоторые формулировки ГК для частных случаев и указано, почему они не могут претендовать на решение проблемы в целом.