Алгоритм НСКО (алгоритм Хо-Кашьяпа)

Зачастую, во время работы с нейронными сетями, перед нами встает задача в построении линейных решающих функций (ЛРФ) для разделения классов, содержащих наши образы.


Рисунок 1. двумерный случай

Один из методов, позволяющих решить нашу проблему, это алгоритм наименьшей среднеквадратичной ошибки (НСКО алгоритм).

Интерес данный алгоритм представляет не только в том, что он помогает построить необходимые нам ЛРФ, а в том, что при возникновении ситуации, когда классы линейно неразделимы, мы можем построить ЛРФ, где ошибка неправильной классификации стремится к минимуму.


Рисунок 2. линейно неразделимые классы

Далее перечислим исходные данные:

— обозначение класса (i — номер класса)

— обучающая выборка

— метки( номер класса к которому относится образ )

— скорость обучения (произвольная величина)

Этой информации нам более чем достаточно для построения ЛРФ.
Перейдем непосредственно к самому алгоритму.

Алгоритм


1 шаг


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

Например:

Пусть задан образ .

Тогда

, если из 1 класса

, если из 2 класса

б) строим матрицу размерностью Nx3 которая состоит из наших векторов

в) строим

г) считаем где произвольный вектор(по умолчанию единичный)

д) (номер итерации)

2 шаг


Проверяем условие останова:

Если то «СТОП»

иначе — переходим к шагу 3

3 шаг


а) (где + это функция Хэвисайда)

Например(функция Хэвисайда):


(если )

(если или )

После подсчетов меняем номер итерации:



б) переходим на шаг 2

Пример работы алгоритма НСКО







принадлежат 1 классу
принадлежат 2 классу

а)






б)


в)


г)




д)

, т.к. все элементы «СТОП»

Завершили работу алгоритма, и теперь можно подсчитать нашу ЛРФ.


Спасибо parpalak за онлайн редактор.

Спасибо за внимание.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 8

    +2
    Этот подход чем-то лучше обычных SVM?
      –1
      Метод SVM имеет кардинально иной подход к классификации данных. На практике я не сравнивал, но с точки зрения теории могу сказать, что в случае линейно неразделимых классов в алгоритме SVM предусмотрен переход к пространству большей размерности, дабы получить разделимость, а в НСКО мы, не меняя исходных данных, стараемся разделить классы, сводя ошибку к минимуму.
        0
        Ну не обязательно же, достаточно просто перейти от жестких ограничений к мягким. Скажем при помощи Hinge loss.
      +1

      Какова общая идея метода? Как вычисляется ошибка, которая минимизируется? Почему алгоритм вообще работает? Чем он лучше или хуже других методов классификации? Какова скорость сходимости?


      Я правильно понимаю, что первый шаг — это просто решение задачи методом нормального уравнения для подвыборки?

        +3
        Как-то это больше похоже на методичку к лабе, честно говоря. Хотелось бы всё-таки увидеть описание работы алгормитма. Хоть какое-то обоснование, почему он сходится и как быстро сходится. Как выбирается скорость обучения… А то сейчас выглядит так, будто если поставить h_k = 100500, то алгоритм всегда будет сходится за одну итерацию.

        Короче, хотелось бы видеть полноценную статью, а не короткую заметку.
          0
          Спасибо за замечание. Данную тематику можно было бы довести до научного исследования, но в данной статье я постарался изложить теорию кратко, в помощь для тех, кто начинает изучение теории классификации.
            +2

            При всём уважении, эта статья начинающим вряд ли будет полезна, так как не объясняет область применимости и характер поведения алгоритма.

              0
              Извините, но теории то как раз нету. Сплошная практика.
              Вот вам шаги алгоритма, вот вам пример шагания.

          Only users with full accounts can post comments. Log in, please.