Генетическое программирование («Yet Another Велосипед» Edition)

Применение Генетического Алгоритма для упаковки 2D обьектов: https://github.com/Jack000/SVGnest

Генетическое программирование («Yet Another Велосипед» Edition)

Заметил в Вашем примере родословной, что нектороые синтксически разные деревья, на самом деле семантически одинаковы:

(((x-0)**2)/1)
((((x-0)**2)-0)/1)
(((x-0)**2)-0)
(((x-0)**2)-0.000)

Некоторое время тому я тоже интересовался данной тематикой.

Чтобы уменьшить количество семантически одинаковых деревьев, я разбивал каждую итерацию Генетического Алгоритма на два этапа:
1) операции над синтаксическими деревьями (скрещивание и мутации)
2) оптимизация числовых коэффициентов каждого синтаксическогг дерева (опять же с использованием Генетического Алгоритма)
Дополнительная оптимизация: в случае, если поддерево не содержит переменных — оно заменяется на лист с единственным числовым значением.

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

Более подробоное описание можно найти в моём посте: https://habrahabr.ru/post/163195/ (правда у меня весь код реализован на Java, и в посте можно найти ссылку на GitHub)

Факторный анализ для чайников

Относительно привычки — хочу обратить внимание на немного другой факт: чаще всего мы привыкли брать чайник той рукой, которая у нас «главная» («правши» — правой, «левши» — левой). Отсюда могу предположить гипотезу: фотографируя чайник, мы будем поворачивать его в наиболее привычный для нас ракурс (носик влево — для правши, или носик вправо — для левши).

Используя Google картинки — можно посчитать процент различных ракурсов чайников: для примерно 100 первых картинок, можно насчитать 12 изображений чайников носиком вправо, и примерно 80 — носиком влево, что коррелирует с процентным соотношением «правшей» и «левшей».

Факторный анализ для чайников

Спасибо за интересную статью.

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

фото 1

фото 2

В большинстве случаев, фото 1 воспринимается людьми как более информативное (в качестве подтверждения: в поиске картинок Google, по запросу «чайник», довольно редко встречаются фотографии чайников со стороны дна).

Таким образом, выбирая наиболее информативную фотографию (проекцию 3х мерного объекта на 2х мерную плоскость) — наш мозг, фактически, выполняет метод главных компонент (в данном случае — поиск ортогональной проекции с наибольшим рассеянием)

Модель Random Forest для классификации, реализация на c#

Спасибо за статью, особенно за обоснование bagging'а и декорреляции.

Также, пользуясь случаем немного попиарюсь :-) Раньше писал небольшую либу на JS и демку того, как работают деревья и лес принятия решений: habrahabr.ru/post/208952/

Деревья принятия решений на JavaScript

Опять проблема с подключением либы из гитхаба на jsfiddle (
Вот эта ссылка на демку, которая должна работать во всех браузерах: jsfiddle.net/ug4Hs/

Деревья принятия решений на JavaScript

А, если не секрет, почему Вы выбрали именно javascript в диссертации? Вы рассматривали какую-то задачу, которая должна решаться на стороне клиента, или просто симпатия к языку?

Деревья принятия решений на JavaScript

Построил дерево решений для Вашего примера.
Судя по структуре дерева, значимыми являются только три параметра из пяти: x1, x4 и x5

Ссылка на демку: jsfiddle.net/H4jpA/



Таким образом, чтобы понять что объект принадлежит к классу «1» — достаточно всего двух параметров x1 и x4.

Деревья принятия решений на JavaScript

Пофиксил.
Теперь демки должны работать и в Яндекс Браузере и в Хроме (надеюсь, что и в IE тоже).

Причина была в том, что к jsfiddle подключал JS код, который хостится на гитхабе (более подробное описание здесь: stackoverflow.com/questions/17341122/link-and-execute-external-javascript-file-hosted-on-github)

Ссылки на демки обновил.

Деревья принятия решений на JavaScript

Проверял в Safari 6.0 и 7.0, Firefox 8.0 и 26.0, Google Chrome 31.0
А что именно не пашет?

Если честно, то в хроме и FF наблюдал проблемы с отображением очень больших деревьев.

CSS для рисования дерева на основе вложенных списков — взят отсюда: thecodeplayer.com/walkthrough/css3-family-tree
Но, поскольку с вёрсткой я фактически не работал раньше — то пофиксить стили для определённых браузеров у меня не получилось (

Деревья принятия решений на JavaScript

В качестве довольно грубого приближения — можно разбить ряд непрерывных значений на несколько классов (например, «очень маленькие значения», «маленькие значения», «большие значения» и т.д.). Затем, имея ограниченное число классов — можно использовать ID3 дерево. Правда, такую технику получится использовать лишь для прогнозирования трендов.

А вообще, для регрессии, лучше посмотреть в сторону CART. На Хабре была статья, в которой упоминался данный метод: habrahabr.ru/post/116385/

Деревья принятия решений на JavaScript

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

В конце статьи я описал идею, о поисковике, который мог бы ранжировать результаты поиска на стороне клиента, с использованием локально построенного классификатора принятия решений (заинтересует пользователя сниппет или нет?). Хотя, думаю, что несмотря на то, что идея звучит довольно просто — при её реализации могут возникнуть различные подводные камни (например, какие именно статические/динамические атрибуты использовать?).

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

С днём 3D и прочей графики!

Присоединяюсь к поздравлениям )

Raytracing render на C

Спасибо за идеи. Реализовал антиаласинг :)

Для поиска границ, в качестве чернового варианта, используется Оператор Собеля
Для каждой точки, которая находится на границе — запускаю 4 луча.

Стало красивее:

Коммит: github.com/lagodiuk/raytracing-render/commit/b6f2d3d49bc13488c7c560c4b54ccbe9cb6d5c0d

Raytracing render на C

Теперь понял что имеется ввиду :-) Попробую реализовать.

У меня, кстати, ещё была идея — содеражть дополнительный массив объектов, которые не эффективно хранить в kd-дереве (например скайбокс, или объект, который передвигается по сцене).

Raytracing render на C

В природе «гладкие не-резкие тени» наблюдаются по двум причинам:
1) существование не точечных источников света
2) в результате освещения диффузно рассеянным светом — областей геометрической тени

А ещё в природе есть:
1) всяческие каустики
2) свет может рассеиваться в результате проникновения в материал на небольшую глубину с последующим излучением (subsurface scattering)
3) есть частички тумана (или дыма), проходя сквозь которые возникает причудливая игра света (в данном случае используется алгоритм — Ray Marching)

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

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

Нужна колориметрия? — используйте Path tracing (его можно можно реализовать поверх Ray tracing рендера, т.к. оперирует он теми же абстракциями).

И, кстати, а почему именно Path tracing? Ведь для каждого нового положения камеры — приходится заново рендерить всё изображение.

Как по мне — более интересным вариантом является Ray tracing + Photon mapping. В данном случае, фотоны можно сохранять в kd-дереве — и их не нужно заново трасировать при изменении положения камеры.

Raytracing render на C

Тоже сначала подумал об этом. Но в качестве контраргумента придумалось вот такое изображение:



В кадре только зеркальная сфера, но в ней отражается вся сцена.

Raytracing render на C

Только что получилось ускорить построение дерева :-)
Подробности описал в этом комментарии: habrahabr.ru/post/187720/#comment_6580780

Raytracing render на C

Подумал над вашим комментарием, а вы правы!

Я пытался найти очень хорошее разбиение сцены, и поэтому анализировал возможность разбиения сцены в 100 различных точках (разбивал сцену, считал SAH и т.д.) — на каждом шаге построения дерева.

Теперь я пытаюсь отыскать оптимальное разбиение только в 5 точках: для сцены с автомобилем (107364 полигонов) — дерево строится за несколько секунд.

Вот этот коммит: github.com/lagodiuk/raytracing-render/commit/3a373e3bbaba25e3d777260e326768b2a4d0ec62

Спасибо :-)

UPD: Упс, комментарий должен быть на уровень выше

Raytracing render на C

К сожалению да. У меня не очень оптимально реализована процедура построения дерева. Более подробно описал в этом комментарии: habrahabr.ru/post/187720/#comment_6580078