Решение задачи о двух спиралях с помощью пакета 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) и уменьшить время обучения.