Часть 3.

Здесь грамматика, полученная во второй части, упрощается объединением эквивалентных правил подстановки.

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

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

В приведенном примере эквивалентны правила с левыми частями и . После слияния и получаем следующий набор правил:

,

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

,

,

,

.

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

70. Требование к вектору признаков

Общие требования:

1. Вектор не должен содержать компонент, которые для данного множества объектов не определены;

2. Вектор не должен содержать компонент, которые для объектов разных классов одинаковы;

3. Вектор не должен содержать компонент, которые не могут быть измерены или вычислены по измерениям;

4. Вектор не должен содержать функционально либо статистически зависимых компонент на рассмотренном множестве объектов;

5. Желательно, чтобы вводимые в описание признаки принимали близкие значения для объектов из одного класса, и сильно различались для разных классов;

6. Желательно, чтобы число компонент было как можно меньше – это способствует требованиям 1-4. Реализуется двумя путями:

   1. Ранжирование остальных признаков в порядке убывания полезности;

   2. Переход от признакового пространства большей размерности к признаковому пространству меньшей размерности.

71. Среднеквадратичное расстояние в евкл простр

Рассмотрим расстояния между различными объектами:

1 тип расстояний – расстояние между двумя точками:

Пусть заданы точка и множество точек .

Тогда средне квадратичное внутри множественное расстояние будет определяться через другие расстояния.

72. Преобр детерм вект призн, миним внутрикласс расст

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

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

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