Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

201

f(x

)=0

Рис. 2. Иллюстрация основной идеи SVM

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

которой ближайших точек обоих классов равны (рис. 2б). Ближайшие

точки-векторы называются опорными. Уравнение разделяющей

плоскости для d-мерного пространства выглядит следующим образом:

+ w

+ ... + w

+ w

= 0,

где d – размерность пространства признаков;

W=(w

, w

, ..., w

) – направляющий вектор разделяющей

плоскости;

– скалярное смещение.

Или в векторной форме:

(W, X) + w

= 0.

Обучением SVM называют процесс получения вектора W и

смещения w

Алгоритмы обучения SVM

Алгоритмы обучения SVM преобразуют задачу поиска

оптимальной разделяющей плоскости к следующей задаче

квадратичного программирования [1]:

()

[]

()

⎪

⎩

⎪

⎨

⎧

==+=

=≥

→−+−=

∑

N, 1,...,i ,1),( èëè ,0

N, 1,...,i ,0

maxmin1),(),(

),,(

wywL

iii

XWWWλW

где λ

– множители Лагранжа.

Поставленную задачу сложно решить, используя градиентные

методы, поскольку на практике размер пространства входных

векторов-признаков достигает нескольких сот тысяч признаков. Время

202

решения задачи такой размерности крайне велико, поскольку матрица

частных производных функции Лагранжа не может целиком

поместиться в памяти компьютера.

Поэтому для обучения SVM были разработаны специальные

методы. Одним из наиболее эффективных на сегодняшний день

является алгоритм последовательной минимальной оптимизации

(Sequential Minimal Optimization) [2], который решает поставленную

проблему, последовательно оптимизируя два случайно выбранных

вектора.

Распараллеливание процесса обучения SVM

Активное развитие многопроцессорных архитектур, методов и

систем параллельного программирования вносит коррективы во

многие сложные алгоритмы. Актуальной проблемой становится

распараллеливание алгоритмов обучения SVM для ускорения их

работы. Следствием такого ускорения является, например,

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

времени для классификации больших потоков информации (текста,

графики, звука).

Для параллельной реализации методов обучения

SVM

предлагается применить декомпозицию по данным.

Метод декомпозиции по данным предполагает выделение из

исходного обучающего множества примеров, принадлежащих первому

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

самое выполняется с примерами другого класса. Далее выбираются

пары групп из обоих подмножеств и для каждой пары строится

отдельный классификатор. Затем результаты

должны каким-то

образом объединяться.

В методе опорных векторов на этапе обучения из множества

исходных примеров выделяются опорные векторы и разделяющая

плоскость строится только на их основе, остальные примеры уже не

учитываются. Этот факт можно использовать следующим образом –

для каждой пары групп отбирать опорные векторы в общее множество

опорных векторов, а

итоговый классификатор строить только на

основе этого множества.

Такой алгоритм можно представить следующей блок-схемой:

203

Начало

Конец

Разбиение

примеров первого класса

на M групп

Параллельная

часть (М ветвей)

Выделение

опорных векторов

для 1-й пары групп

Выделение

опорных векторов

для 2-й пары групп

Выделение

опорных векторов

для М-й пары групп

Построение классификатора

на основе всех опорных

векторов

Разбиение

примеров второго класса

на M групп

Параллельная

часть (2 ветви)

Объединение групп

обоих классов в пары

Блок-схема параллельного алгоритма обучения SVM

Рассмотрим процессы разбиения исходного обучающего

множества на группы объектов и объединения групп в пары.

Разбиение и объединение произвольным образом не даст требуемого

результата, так как может оказаться, что векторы, которые не являются

опорными для пары, будут таковыми для задачи в целом. Пример

такого неудачного разбиения приведен на рис. 3. Векторы V1–V5

рассматриваются совместно

и оказывается, что для этих векторов

опорными будут векторы V3 и V4, таким образом, вектор V1 далее не

рассматривается, а он является опорным при рассмотрении множества

в целом.

Рис. 3. Пример неудачного разбиения на группы

Следовательно, необходима стратегия, которая позволила бы не

упускать на этапе выделения опорных векторов «настоящие» опорные

векторы.

В качестве такой стратегии предлагается использовать методы

кластеризации для выделения групп объектов, а также объединять

204

группы по принципу максимальной близости центров кластеров. В

качестве метода кластеризации можно выбрать метод k-means

(k-средних) [3].

Процесс обучения при данном подходе можно описать

следующим образом (рис. 4).

К1

К2

К3

К4

f(x

)=0

Рис. 4. Пример обучения с кластеризацией (число кластеров k=2)

Предварительно множество примеров каждого класса делится на

кластеры – на рис. 4 это кластеры К1–К2 для одного класса и К3–К4

для другого. Затем вычисляются центры кластеров и формируются

пары кластеров: в каждую пару входят кластеры, принадлежащие

разным классам, центры которых наиболее близки друг другу. На

следующем этапе осуществляется параллельное обучение всех

пар

кластеров (например, с использованием алгоритма последовательной

минимальной оптимизации), результатом которого является выделение

опорных векторов для каждой пары. После этого результаты

объединяются – происходит построение итогового классификатора на

основе полученных опорных векторов.

Итоговый классификатор является приближенным решением,

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

решения следует верифицировать классификатор на обучающем

множестве

и при обнаружении ошибочных примеров провести

повторное обучение на данных примерах и известных опорных

векторах.

Заключение

Таким образом, в докладе рассмотрены основы и алгоритмы

обучения машины опорных векторов SVM. В настоящее время

отсутствуют эффективные методы, позволяющие распараллеливать

205

процесс обучения SVM. В докладе предложено использовать для

параллельной реализации обучения метод декомпозиции по данным в

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

позволяет получить решение, близкое к оптимальному, которое при

необходимости может быть уточнено.

В дальнейшем планируется исследовать возможности применения

данного подхода для линейно неразделимых задач.

Литература

1. Burges C.A. Tutorial on Support Vector Machines for Pattern

Recognition. Kluwer Academic Publishers, Boston, 1998.

Platt J. Sequential Minimal Optimization: A Fast Algorithm for

Training Support Vector Machines // Advances in Kernel Methods

Support Vector Machine, MIT Press, Cambridge, 1999. P. 185–

208.

MacQueen J. Some methods for classification and analysis of

multivariate observations // Proc. 5th Berkeley Symposium on

Mathematical Statistics and Probability, Vol. 1, 1967. P. 281–297.

МЕТОДЫ ПАРАЛЛЕЛЬНОГО ЛОГИЧЕСКОГО ВЫВОДА ДЛЯ

ОБРАБОТКИ ЗНАНИЙ НА КЛАСТЕРНЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

О.В. Кошкин

Вятский государственный университет, Киров

Введение

Одним из основных направлений развития современных ЭВМ

является разработка архитектур, ориентированных на обработку

знаний. Обработка знаний – одна из сфер применения искусственного

интеллекта, предполагающая использование компьютером знаний,

которыми владеет человек, для решения проблем и принятия решений.

Важную роль в обработке знаний играет логический вывод [1].

Особый интерес представляет достоверный логический вывод

(дедуктивный)

в логике предикатов первого порядка, который в

отличие от правдоподобного (индуктивного, абдуктивного) вывода

позволяет получить истинные заключения.

Обработка баз знаний представляет собой трудоёмкий процесс,

ввиду необходимости специфичной обработки большого объёма

206

информации (переборный характер процедур вывода), а также

сложных нетрадиционных структур данных.

С учётом современных тенденций в вычислительной технике,

чёткой направленности на многопоточное программирование и

параллелизацию вычислительных процессов, имеет место развитие

параллельных методов логического вывода. В данном докладе

приводится приблизительная оценка эффективности подходов к

распараллеливанию логического вывода в системах обработки знаний.

В соответствии с [2] на современном этапе различают несколько

уровней параллелизма:

 параллелизм на уровне термов;

 параллелизм на уровне клозов (дизъюнктов);

 параллелизм поиска.

Параллелизм на уровне термов является параллелизмом низшего

уровня и применительно к исчислению предикатов первого порядка

реализуется параллельной унификацией литералов. В условиях

современных высокопроизводительных средств вычислительной

техники реализацию данного уровня параллелизма рационально

проводить в рамках одного многоядерного микропроцессора либо

многопроцессорного вычислительного модуля (в том числе

вычислительного модуля с многоядерными микропроцессорами

). Это

обусловлено высокой связностью между данными.

На уровне клозов (дизъюнктов) применяется параллельная

обработка формул. В Пролог-подобных системах имеет место OR-,

AND-, DCDP-резолюционый параллелизм. Также существуют методы,

отличные от резолюционных – метод деления дизъюнктов и его

модификации. Количество процедур вывода на текущем шаге в

зависимости от метода может быть различным (может достигать

огромного

количества при больших масштабах задачи). Реализация

данного уровня параллелизма возможна на нескольких

многопроцессорных мультиядерных вычислительных узлах

Параллелизмом самого высокого уровня является параллелизм

поиска. Здесь различают распределённый поиск и мультипоиск. В

первом случае пространство поиска разбивается на ряд

подпространств, в которых поиск происходит параллельно. В другом

случае к одному и тому

же пространству поиска применяются

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

количество вычислительных единиц, задействованных в процессе

207

поиска, будет зависеть от количества подпространств либо от

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

рационально комбинировать оба метода.

Параллелизм на уровне термов не требует особого анализа, так как

на текущий момент не имеет сложной алгоритмической структуры –

происходит параллельное выполнение операций унификации. Тем

более что на данном уровне нет такого

разнообразия методов, как на

уровне параллелизма клозов. Сама операция унификации проста,

поэтому затраты на её распараллеливание и выполнение могут не

стоить полученного выигрыша в быстродействии.

Самый высокий уровень (уровень поиска) может быть интересен с

точки зрения эффективности организации параллельных процессов.

Интересным для оценки эффективности методов

распараллеливания является средний уровень – уровень дизъюнктов

Этому есть несколько причин:

 разнообразие методов вывода и их модификаций;

 для масштабных задач возможен «комбинаторный взрыв»;

 методы, применяемые на данном уровне, более требовательны

к вычислительным ресурсам, поэтому от эффективности

алгоритма распараллеливания на данном уровне в большей

степени будет зависеть скорость вывода и эффективность

использования ресурсов кластера.

В качестве методов вывода предлагается рассмотреть наиболее

распространённый резолюционный метод и метод деления

дизъюнктов.

Среди перечисленных выше резолюционных методов, согласно

[2], достаточно рассмотреть только DCDP-резолюцию. AND-

резолюция эффективна в графах с большим количеством

однолитеральных дизъюнктов, что в реальных задачах практически не

встречается. OR-резолюция даёт хорошие результаты в задачах,

представляемых сильносвязными графами, однако при этом

генерируется самое большое среди аналогичных методов количество

резольвент, часть которых впоследствии не принесёт результатов в

выводе. На хранение

дополнительных резольвент требуется

дополнительный объём ОП, а это при решении масштабных задач

может играть существенную роль.

208

Сравнение методов достаточно провести на примере небольшой

задачи, по которой можно будет обнаружить преимущества и

недостатки. Предлагается задача, приведённая в [1]:

«Если я поеду автобусом, а автобус опоздает, то я опоздаю на

работу. Если я опоздаю на работу и стану огорчаться, то я не попадусь

на глаза моему начальнику. Если я

не сделаю в срок важную работу, то

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

Следовательно, если я поеду автобусом, а автобус опоздает, то я

сделаю в срок важную работу». Исходные данные и посылки

представлены в виде формул логического следования (секвенций),

определённых в исчислении высказываний I [1]:

A&B

C; 2) C&D E; 3) K D&E; 4) A&B K.

Рассмотрение метода DCDP-резолюции предлагается провести с

использованием графа связей Ковальского. Граф связей Ковальского

представляет собой структуру, построенную предварительно и

отображающую связь между потенциально резольвируемыми

дизъюнктами. Признаком выводимости того или иного утверждения

является получение пустой резольвенты в процессе вывода.

Ниже представлен логический вывод тремя параллельными

резолюционными методами.

Метод DCDP-параллельной резолюции.

Приведённые выше секвенции преобразуются к дизъюнктивной

форме по правилам, определённым в исчислении высказываний I:

1) А v B v C; 2) C v D v E; 3) K v D; 4) K v E; 5) A; 6) B; 7) K.

На рисунке 1 изображён граф связей Ковальского для данного

примера

209

K v E

K v D

AB K

C v D v E

A v B v C

Рис. 1. Граф связей Ковальского для поставленной задачи

Для пояснения процесса вывода следует дать несколько

определений, приведённых в [2].

Определение 1. Дизъюнкты называются смежными, если

существует одна или несколько связей, соединяющих литеры одного с

литерами другого.

Определение 2. Множеством DCDP-связей называется множество

связей, которые соединяют пары различных дизъюнктов, если

дизъюнкты каждой пары не являются смежными со всеми

дизъюнктами остальных пар.

Резольвирование в

данном методе осуществляется параллельно на

множестве DCDP-связей. Шаги вывода приведены ниже.

Шаг 1. Можно определить несколько DCDP-множеств: {1,5},

{2,5}, {1,6},{2,6}. Выбор конкретного множества в реальных задачах

определяется эвристиками. В данном примере можно выбрать любое

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

разницу в выборе того или иного множества.

После

проведения резольвирования по первому множеству

получается граф, приведённый на рисунке 2 а.

Шаг 2. Проведём резольвирование по DCDP-множеству {1,5}.

Полученный граф изображён на рисунке 2 б.

210

B v C

K v E

C v D v E

б)

а)

Рис. 2

На последующих трёх шагах DCDP-множеств нет, и будет

происходить последовательное резольвирование по связям 1, 2, 3. В

результате вывод будет успешен, так как будет получен пустой

дизъюнкт.

Метод деления дизъюнктов

В таблице 1 отражена последовательность действий при выводе

методом деления дизъюнктов. Решение приведено в [1]. Исходные

секвенции преобразованы в секвенции дизъюнкты по правилам

исчисления I.

Шаг 1 Шаг 2

1 A v B v C

_ _

C v D v E

1 K v D

1 K v E

÷d

1.1

_ _

=A v B v K

=CDE≠0

_ _

1.1

= C v D v E

Таблица 1. Вывод методом деления дизъюнктов

Как можно видеть, вывод завершился на втором шаге. В данном

случае параллельно осуществляются операции деления дизъюнктов.

Сравнение методов

По представленным выше выводам можно видеть, что метод

деления дизъюнктов существенно сокращает количество шагов

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