четверг, 2 декабря 2010 г.

Замечания по отладке в SBCL и Slime

Оригнальный текст: https://gist.github.com/659495#file_sbcl_debugging_notes.txt, Nikodemus Siivola

0 Умение сокращать размеры тестового набора - это важный навык, не зависящий от языка или инструментария. Это целое искусство - сокращать до премлемых размеров количество примеров, приводящих к появлению ошибок, неверных результатов (например, моменты, связанные с указанием полного пути или текущей директории, выполнением кода в Slime или вне него). С одной стороны, чем меньше тестовых примеров, тем лучше, но здесь надо соблюдать осторожность. Если вы в состоянии распознать баг за пару минут каким-либо другим методом, очевидно, глупо тратить несколько часов на сжатие тестового набора. Однако, если другими методами вы не в состоянии этого сделать, придется смириться с временными затратами.

1 Осторожное программирование. Речь не только о том, как избегать ошибок в коде, но и о том, как делать его легкоотлаживаемым. Избегайте IGNORE-ERRORS, не позволяйте компилятору безмолвно проглатывать ошибки. Иногда это может быть полезным, но чем больше таких мест в коде, тем сложнее использовать *BREAK-ON-SIGNALS*. Избегайте SAFETY 0 как чумы - он скроет множество огрехов. Не используйте DEBUG 0 - от этого вы не получите выгоды. Определяйте PRINT-OBJECT методы для собственных объектов, давайте им имена. Никогда не употребляйте INTERRUPT-THREAD или WITH-TIMEOUT, пока вы не будете точно уверены в том, что делаете, и пока не поймете, почему их лучше не использовать.

2 Не задумывайтесь там, где не следует. Просто внимательно вчитывайтесь в сообщения об ошибках. Иногда они бесполезны, но иногда вы рискуете упустить много полезной информации.

3 Изучайте возможности инструментария. Здесь стоит остановиться подробнее.

   3.0 M-. - это отличная вещь. Нажимая 'v' в отладочном окне Slime, вы также попадаете в участки кода, предоставляющего достаточно много информации для отладки, но M-. можно использовать везде.

   3.1 Slime Inspector - один из главных отладочных инструментов. Пригодится он вам или нет - зависит от задачи, но будет полезно познакомьться с его возможностями, они того стоят.

   3.2 Обратная трассировка (backtrace) в SBCL на настоящий момент реализована не лучшим образом, но ее использование может принести определенные плоды. Просто загляните (вызовите любую ошибку) в REPL и выясните, что происходит. Поразвлекайтесь с штатным отладчиком SBCL и модным Slime Debugger, прежде чем будете пользоваться ими на практике, и тогда они перестанут казаться вам враждебными. О том, как пользоваться обратной трассировкой, я напишу в другой раз.

   3.3 Разберитесь с *BREAK-ON-SIGNALS* и TRACE. Не забывайте, что SBCL предоставляет некоторые расширения возможностей TRACE.

   3.4 Пошаговое выполнение по сути не является отладочным инструментом. Я считаю, что это всего лишь средство наблюдения за ходом исполнения. Иногда это может быть полезным в отладке, но только при компиляции кода с DEBUG 3, когда (STEP (FOO)) доставит вас в нужное место.

   3.5 Пользуйтесь M-RET (macroexpand) в Slime. Попробуйте (SETF *PRINT-GENSYM* NIL) и посмотрите, что будет происходить. Это несет с собой потенциальные опасности, но зато может позволить легко копировать и вставлять код, в который раскрывается ваш тестовый пример. (Замена раскрытий макросов в пакете COMMON-LISP, как правило, нецелесообразна, но в пользовательских пакетах может быть очень полезным.)

   3.6 Если ничего не помогло, попробуйте (sb-ext:restrict-compiler-policy 'safety 3) и (sb-ext:restrict-compiler-policy 'debug 3), после чего перекомпилируйте весь код. Теперь отладка станет легче. Если ошибка исчезла,  либо (а) вы ошиблись с типами (или допустили похожую ошибку) в коде, собранном с SAFETY 0, и она не терялась благодаря IGNORE-ERRORS или HANDLER-CASE, либо (б) вы обнаружили баг в SBCL: вообще говоря, политика компилятора не должна изменять поведение кода, за исключением нескольких допускаемых ANSI случаев при использовании SAFETY 3, или же когда высокий уровень отладки препятствует оптимизации хвостовой рекурсии. Знающие Scheme объяснят вам, что это может иметь значение.

   3.7 DISASSEMBLE не есть штатное средство отладки, но иногда может быть полезным. Это зависит от сути имеющейся проблемы.

4 Расширения отладочной печати. Часто это простейшее средство, которым можно воспользоваться. Не стыдитесь этого.

   4.1 Пользуйтесь специальными переменными:

  (LET ((*DEBUG* :MAGIC)) ...) и, где-либо в коде,

  (WHEN (EQ :MAGIC *DEBUG*) (PRINT (LIST :FOO FOO)))

Будучи ленивым, я обычно использую глобальные переменные для управления отладочной печатью, как в примере выше. Это позволяет использовать ее только при необходимости, определять, на каком участве кода происходит вызов и т.д.

   4.2 Не бойтесь вставлять в отлаживаемый код (break "foo=~S" foo) или подобные вызовы.

   4.3 SB-DEBUG:BACKTRACE все же можно использовать.

пятница, 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). Сеть успешно справилась с задачами и показала даже большую эффективность, чем авторская реализация.

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

воскресенье, 12 сентября 2010 г.

Математика в SBCL: бенчмарк

После проведения некоторых оптимизаций кода sb-math решил провести тест производительности функций умножения матрицы на матрицу и матрицы на вектор. Для сравнения взял GSLL и простым сишным кодом. Таким образом, сравнивался чистый вызов функций cblas_sgemv и cblas_sgemm из библиотеки GSL CBLAS и два интерфейса к ним.

Код бенчмарков тут:
* bench.lisp - код для gsll и sb-math, а также вызова скомпилированного сишного кода, обработки результатов и отрисовки графиков.
* gemm_bench.c, gemv_bench.c - сам сишный код
* там же графики зависимостей (png)

Итак, умножение матрицы на вектор. Для упрощения умножалась квадратная матрица NxN на вектор длиной N.





На графике показана зависимость времени единичного вычисления от размености N. на больших размерностях GSLL дает существенное отставание. Причина этого неожиданного факта не совсем понятна. Более того, полгода назад на похожем тесте для больших размерностей GSLL шла рядом с сишным кодом, а вот для малых давала из рук вон плохие результаты. Вероятно, это связано с тем, что автор GSLL (Liam Healy) недавно перекроил все матричное api для нее.

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






Тут не очень интересно, поэтому чуть увеличим размерность:







Так все более-менее ясно.

Теперь умножение матрицы на матрицу. Простоты ради все матрицы квадратные, с одинаковой размерностью.






Начиная с N=200 GSLL резко уходит уходит в отрыв, sb-math продолжает преследовать gcc :)

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


Подводя итог, можно сказать, что sb-math смотрится достаточно неплохо даже на  фоне gcc, хотя на матрицах малых размерностей относительное отставание от сишного кода велико. Но там еще есть возможности для оптимизации, и это вселяет надежду :)

GSLL ведет себя достаточно странно, причем это поведение стабильно воспроизводится. Тем не менее, с новым foreign array api там все стало существенно лучше.

Ну а сишный код - что с него взять? Накладных расходов на подготовку параметров там нет, но нет и гибкости и удобства, которые дает lisp.

Ну и это самое. В отличие от GSLL sb-math не привязана к какой-то одной библиотеке CBLAS. Подключение ее к функциям из ATLAS дает существенный рост производительности по сравнению с GSLL. Тем не менее, я не стал включать в бенчмарк тесты на атласе, потому что целью было посмотреть оверхед на вызов функций. Да и не совсем честно это, что sb-math будет обгонять сишный код.

Ну вы поняли :)

UPD: В связи с глобальной переписью кода этот бенчмарк стал неактуальным. Оверхед на малых размерностях стал еще меньше.

суббота, 11 сентября 2010 г.

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

Присоединился к недавнему флешмобу и заменил свой оконный менеджер для X11 на StumpWM. Настроил управление в духе fluxbox, конфиг на github, если кому вдруг интересно.
StumpWM запускается в виде образа sbcl, поэтому для работы в sbcl нет смысла запускать новый процесс, если можно приконнектиться к старому.

В моем случае окончание файла xinitrc выглядит так:

stumpwm &
exec emacs

В конфиге stumpwm запускается swank, а в емаксе, в свою очередь, выполняется
(slime-connect "127.0.0.1" 4005 'utf-8-unix)

В итоге, сразу после загрузки иксов открывается емакс с уже запущенным slime. Удобно.


Но пост не об этом, на самом деле, а об одном забавном моменте.

StumpWM имеет тенденцию иногда падать, особенно, когда sbcl, в котором он работает, кто-то загрузил на 100%. И вот, значит, он упал, окошки не переключаются, хоткеи не работают и т.д., но X-сервер исправно пашет, и последнее активное окно по-прежнему доступно. Перезапускать иксы не хочется, особенно, когда открыто много окон.


Решение найдено!
Alt-Ctrl-F2     # переключаемся в консоль
killall stumpwm # убиваем повисший процесс
stumpwm         # запускаем новый
Alt-Ctrl-F7     # возвращаемся в иксы

Все окна целы, несохраненные данные не потеряны. Не знаю, может быть, это вполне естественно, но меня порадовало :)

понедельник, 30 августа 2010 г.

интерфейс к gnuplot

Решил написать лисповый интерфейс к отличной рисовалке графиков gnuplot. Отчасти потому что существующие интерфейсы в печальном состоянии, отчасти из-за своей страсти к велосипедостроению.

Выложил одну из версий на github. Приведу небольшой обзор возможностей.

;; запускаем gnuplot
(gplt-start)
;; далее передаем ему команды
#G(plot (/ (sin x)))
;; смотрим, что получилось
(gplt-display)
;; убиваем процесс
(gplt-stop)

После вызова gplt-display появилось обычное окошко gnuplot:

#G() - это макрос чтения, соответствующий вызову (gplt-exec '(plot (/ (sin x)))). здесь могут быть любые команды, которые поймет сам gnuplot. s-выражение преобразуется в строку по следующим правилам.

  • Если выражение начинается с plot или splot, то следующий элемент выражения считается функцией либо файлом с данными. Функция задается обычным s-выражением и преобразуется в инфиксную форму, понятную gnuplot.
  • Интервалы задаются словом range. (range 0 1) преобразуется в [0:1]
  • Перечисления задаются словом enum. (enum 10 10) преобразуется в 10,10
  • Остальные ключевые слова передаются без изменений
Таким образом, мы можем написать следующее:

(gplt-restart)
(map nil #'gplt-exec
  '((unset key)
    (set xrange (range 0 2))
    (set yrange (range 2 5))
    (set isosamples (enum 30 30))
    (splot (sin (* x y)) with pm3d)))
(gplt-display)

Это будет соответствовать следующим командам, набранным в самом интерпретаторе gnuplot:

unset key
set xrange [0:2]
set yrange [2:5]
set isosamples 30,30
splot sin(x*y) with pm3d

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

воскресенье, 15 августа 2010 г.

Бредогенератор запущен

Тут буду помещать разные вещи, связанные с языком Common Lisp, которые могут быть интересны сообществу.

Бредогенератор, от винта!