- •1. Типы измерительных шкал. Теория измерений.
- •2. Меры близости между объектами в пространстве разнотипных шкал.
- •5. Статистическая постановка задачи распознавания. Байесово решающее правило.
- •6.Классификация алгоритмов распознавания
- •7. Параметрические и непараметрические алгоритмы восстановления плотностей.
- •8 Линейный дискриминант Фишера
- •10. Метод потенциальных функций
- •11. Метод опорных векторов
- •15.Оценка качества распознавания
- •18. Классификация методов таксономии
- •30. Алгоритм grad.
- •26. Задача частичного обучения. Основные подходы к ее обучению.
- •37 Функция конкурентного сходства. Измерение компактности на основание конкурентного сходства.
30. Алгоритм grad.
Его отличие от других состоит в том, что добавление 1n и исключение 2n признаковделается не по одному, а всеми возможными сочетаниями из имеющихся по 1n и 2n , соответственно. Полезность такого подхода понятна. Действительно, несколько признаков, каждый из которых не информативен, вследствие особого вида взаимной зависимости могут образовать информативную «гранулу». Мы убедились в этом на таком простом примере. На генетических данных с исходным числом признаков N=319 мы выбирали информативные подпространства, постепенно наращивая их размерность. При n=2 были использованы два метода – алгоритм AdDel и метод полного перебора. При этом выяснилось, что полный перебор выявил 6 пар, информативность которых была выше информативности лучшей пары, найденной методом AdDel. В состав всех этих более успешных пар входили признаки, индивидуальная информативность которых была ниже информативности самого информативного признака, выбранного алгоритмом AdDel на первом шаге.
Из приведенных фактов был сделан следующий вывод: в алгоритмах выбора информативных подсистем нужно применять элементы полного перебора настолько широко, насколько это позволяют машинные ресурсы. В разработанном нами алгоритме GRAD («гранулированный AdDel») метод AdDel работает на множестве G наиболее информативных «гранул», каждая из которых состоит из w признаков, w=1,2,3…W, предварительно отобранных методом полного перебора.
Выбор W нами делался исходя из двух соображений. Первое из них основано на учете ограничений на возможности решения реальных переборных задач на вычислительных машинах распространенного типа. Второе основано на гипотезе о преобладании простых закономерностей над сложными.
26. Задача частичного обучения. Основные подходы к ее обучению.
В зависимости от постановки может рассматриваться как задача таксономии с ограничениями
Основные подходы
Основанные на восстановлении смеси распределений
EM-алгоритм
Два взгляда на выборку
Co-training
Графовые методы с опорой на классифицированные объекты
TDR
Частично обученные SVM
Алгоритм СПА. Метод случайного поиска с адаптацией.
Разобьём отрезок (0-1) на одинаковых участков и сопоставим каждый участок своему признаку: 1-й участок соответствует первому признаку, 2-й — второму и т. д. Каждый участок имеет ширину . Запускается датчик случайных чисел с равномерным распределением в диапазоне (0-1). Если число попадает в -й участок, то -й признак включается в испытуемый набор признаков. После шагов работы датчика выбранными оказываются признаков. Качество этой случайно выбранной подсистемы оценивается по одному из критериев, например по числу получаемых ошибок распознавания .
Описанная процедура случайного выбора -мерных подсистем признаков и оценки их качества повторяется раз. Рассмотрение полученного списка оценок позволяет выбрать наилучшую и наихудшую из подсистем. На этом основании делается процедура «поощрения» и «наказания»: участки, соответствующие признакам, попавшим в наилучшую подсистему, поощряются путем расширения их границ на величину , а участки, соответствующие признакам из самой неинформативной подсистемы, наказываются тем, что их ширина уменьшается на величину . Суммарная длина всех участков по-прежнему равна единице.
После этого случайным образом выбираются и испытываются новых подсистем. Но теперь вероятность попадания признаков в эти подсистемы не одинакова: поощрённые признаки, представленные более широкими отрезками, имеют больше шансов войти в очередную подсистему, чем наказанные. По результатам испытания этой партии подсистем процедура адаптации (наказания и поощрения) повторяется. Если некоторый признак случайно попадает и в самую лучшую и самую худшую подсистемы, то длина его участка остаётся неизменной. Если же он регулярно оказывается в составе самой информативной подсистемы, то длина его участка растёт с каждым шагом адаптации. Точно так же признак, систематически попадающий в самую неинформативную подсистему, с каждым шагом сокращает длину своего участка и тем самым уменьшает вероятность включения в испытуемые подмножества признаков.
После некоторого количества циклов поиска и адаптации процесс стабилизируется: участки удачливых признаков занимают практически весь отрезок (0-1) и в испытуемую подсистему выбираются одни и те же признаки. Этот факт служит сигналом к окончанию процесса выбора -мерной подсистемы наиболее информативных признаков.
Скорость сходимости и качество получаемого решения зависят от величины . При больших значениях процесс останавливается раньше, но качество полученного решения обычно хуже, чем при малых . Малые значения соответствуют более мягкой стратегии поощрений и наказаний. Это иллюстрирует рис. 24. Если исходить из того, что признак, наказываемый на всех шагах адаптации, все еще сохраняет ненулевое значение длины своего участка, то величина должна выбираться из соотношения . Практически приемлемые результаты получаются при и .
В более сложных случаях, где полный перебор был невозможен, качество подсистемы признаков, выбранных методом СПА, сравнивались с качеством исходной системы из признаков. Как правило, за приемлемое время алгоритм СПА выбирал подсистему, которая по информативности мало уступала исходной системе, что позволяет считать выбранную подсистему близкой к оптимальной. На одних и тех же примерах алгоритм СПА показывает лучшие результаты, чем описанные алгоритмы Del и Add.
Алгоритмы семейства WANGA
WANGA-R – для шкалы отношений
blk/bik=blj/bij blk`=blj*bik/blk
дисперсии всех прогнозов по l-строке и k-столбцу используются в качестве меры компетентности
окончательный прогноз –средневзвешенные подсказки по компетентной подматрице
WANGA-I – для шкалы интервалов
(bij-blj)/(blj-btj)=(bik-blk)/(blk-btk)
bltk`=blj +(blj-btj)*(bik-blk)/(blk-btk)
Дисперсия в качестве меры компетентности
WANGA-0 – для шкалы порядка
bij`<blj если bik<blk
bij`>blj если bik>blk
bij`=blj если bik=blk
Устраивается голосование за все возможные значения признака
В качестве меры компетентности используется энтропия
WANGA-N – для шкалы порядка
bij`blj если bikblk
bij`=blj если bik=blk
В качестве меры компетентности используем энтропию
Алгоритмы семейства WANGА
Алгоритмы семейства WANGA [85], как и семейства ZET, основаны на гипотезе локальной компактности, но предназначены для заполнения пробелов в таблицах с разнотипными переменными. Начнем с описания алгоритмов для таблицы, все признаков в которой измерены в одной и той же шкале отношений.