пятница, 19 ноября 2010 г.

Решение задачи о двух спиралях с помощью пакета ANNIL

Задача о двух спиралях известна как трудная, с высокой степенью нелинейности, задача для тестирования алгоритмов классификации.


Две спирали, "одна в другой", симметричные относительно центра и поворота на 180 градусов.


Обучающее множество генерируется так ("annil/tests/two-spirals.lisp")

(defun 2spiral-radius (i) (/ (* 6.5 (- 104 i)) 104))
(defun 2spiral-angle (i) (* i (/ (coerce pi 'single-float) 16)))


(defun genpat-2spirals (&optional (output-ranges '(-1.0 1.0)))
  
(let ((patterns nil))
    
(dotimes (i 97)
      
(let ((r (2spiral-radius i))
        
(a (2spiral-angle i))
)

    
(let ((x (* r (sin a)))
          
(y (* r (cos a)))
)

      
(push (list (make-matrix 2 :initial-contents `(,x ,y))
                  
(make-matrix 1 :initial-element (first output-ranges))
)

        patterns
)

      
(push (list (make-matrix 2 :initial-contents `(,(- x) ,(- y)))
                  
(make-matrix 1 :initial-element (second output-ranges))
)

        patterns
)
)
)
)

    
(nreverse patterns)
)
)

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

(defparameter *classifier*
  
(make-cascor-classifier *patterns* nil 'tanh-fn 0.8 20
   `
((:iter . 100) (:verbosity . 2) (:cc-iter . 100) (:cc-candidates . 5))
)
)

Процедура обучения сети состоит из последовательного добавления нового узла (и настройки его входных весов) и настройки выходных весов


Аргументы обучающей процедуры:


*patterns* - обучающий набор (пары вход -- желаемый выход)
nil - тестовый набор для проведения перекрестной проверки (cross-validation, метод предупреждения переобучения сети)
'tanh-fn - функция активации узлов.
0.8 - порог уверенной классификации. (выход в промежутке [-1.0;-0.2] - отрицательная классификация, [0.2;1.0] - положительная, [-0.2;0.2] - неуверенная, рассматривается как неверная)
20 - количество добавляемых скрытых узлов.


Ассоциативный список содержит параметры самого алгоритма (довольно удобный способ хранения и передачи аргументов, не надо париться с порядком последовательности). В примере приведены обязательные аргументы (количество итераций настройки выходов (:iter), входов (:cc-iter), кандидатов на добавление в сеть (:cc-candidates, выбирается лучший из заданного количества узлов, обученных обученных).
Параметр verbosity не обязательный, по умолчанию 0. Определяет "многословность", количество выдаваемой информации (0 - ничего не говорит, 4 - выдает максимум информации)


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


Дополнительная опция test-fn (последний аргумент) позволяет выводить состояние системы после обучения каждого нового узла, например, рисовать картинки с помощью gnuplot.


Вернемся к процессу обучения. С параметром verbosity=2 вывод процедуры выглядит следующим образом:

(defparameter *classifier*
  
(make-cascor-classifier *patterns* nil 'tanh-fn 0.8 20
    `
((:iter . 100) (:verbosity . 2) (:cc-iter . 100) (:cc-candidates . 5))
    #'
(lambda (net iter)
        
(visual-classify-2spirals net *pat* 0.8
          
(format nil "'/tmp/test-known~A.png'" iter)
)

        
(visual-test-2d net 10000 6.5 '(-1.0 1.0) 0.8
          
(format nil "'/tmp/test-unknown~A.png'" iter)
)
)
)
)

Сделать нормальный cut с первой попытки не получилось, на то он и blogger, поэтому привожу только начало и конец вывода.

В начале ...


 ;; Final error: 0.9869251
 ;;
 ;; Training 0 node
 ;; Training candidates: .....
 ;; Best corr: 27.80652
 ;; Connecting to outputs
 ;; Final error: 0.97089535
 ;; Epochs passed: 200
 ;;
 ;; Training 1 node
 ;; Training candidates: .....
 ;; Best corr: 24.884932
 ;; Connecting to outputs
 ;; Final error: 0.95397794
 ;; Epochs passed: 300
 ;;
 ;; Training 2 node
 ;; Training candidates: .....
 ;; Best corr: 17.344604
 ;; Connecting to outputs
 ;; Final error: 0.94608283
 ;; Epochs passed: 400

И в конце ... 


 ;; Training 17 node
 ;; Training candidates: .....
 ;; Best corr: 16.05864
 ;; Connecting to outputs
 ;; Final error: 0.062364805
 ;; Epochs passed: 1900
 ;;
 ;; Training 18 node
 ;; Training candidates: .....
 ;; Best corr: 10.090686
 ;; Connecting to outputs
 ;; Final error: 0.052389637
 ;; Epochs passed: 2000
 ;;
 ;; Training 19 node
 ;; Training candidates: .....
 ;; Best corr: 8.781674
 ;; Connecting to outputs
 ;; Final error: 0.043491814
 ;; Epochs passed: 2100



После обучения каждого нового узла рисуются две картинки - результат работы сети на обучающем наборе (проверка качества запоминания) и на наборе случайных точек, которые он должен отнести к одной или другой спирали (проверка качества обобщения).


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


Картинки лежат на гитхубе. Приведу две соответствующие картинки после окончания обучения.




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




Неплохо, однако. У Фальмана аналогичные картинки (в статье) более ломаные и меньше похожи на спираль.


Надо сказать, что после добавления 20 узлов среднекваратическая ошибка все еще довольно высока (0.04). Настройкой параметров алгоритма можно значительно ее уменьшить (мне удавалось получить меньше 0.001) и уменьшить время обучения.

среда, 17 ноября 2010 г.

Нейросетевое решение задачи классификации

Наконец-то удалось сделать нормальный классификатор для пакета нейросетевого анализа. (http://github.com/allchemist/annil).

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

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

Алгоритм quickprop решает задачу нелинейной регрессии с квадратичной сходимостью за время, линейно зависящее от количества весов сети, чем выгодно отличается от обратного распространения (линейная сходимость, линейное время) и от многомерной квазиньютоновской оптимизации (квадратичная сходимость, квадратичное время).

Алгоритм каскадной корреляции настраивает архитектуру сети самостоятельно, добавляя по одному узлу, который обучается извлекать следующий наиболее важный признак (процедура исчерпания, аналогичная ортогонализации Грама-Шмидта).

В результате, архитектура обладает отличной способностью к решению задач классификации, не обладая при этом многими неприятными особенностями обратного распространения.

Как quickprop, так и каскадная корреляция, разработаны Скотом Фальманом, одним из разработчиков CMU CL, также известным как изобретатель смайликов. :)
Авторские статьи по этим алгоритмам лежат тут: http://www-2.cs.cmu.edu/~sef/sefPubs.htm

Реализация тестировалась на нескольких задачах, которые считаются довольно сложными (two spirals, ocr, некоторые задачи проекта elena). Сеть успешно справилась с задачами и показала даже большую эффективность, чем авторская реализация.

В ближайшее время подготовлю примеры использования с красявыми картинками :)