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 если bikblk

bij`=blj если bik=blk

В качестве меры компетентности используем энтропию

Алгоритмы семейства WANGА

Алгоритмы семейства WANGA [85], как и семейства ZET, основаны на гипотезе локальной компактности, но предназначены для заполнения пробелов в таблицах с разнотипными переменными. Начнем с описания алгоритмов для таблицы, все признаков в которой измерены в одной и той же шкале отношений.