![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovЯ тут пытаюсь расширить горизонты своего незнания и у меня есть чайниковый вопрос: вот, допустим, я взял наивный байесовский классификатор (или какие-то вариации на его тему) и начал им что-то там классифицировать.
Пока у меня с десяток классов - все, естественно, идет неплохо. А если я захочу, чтобы у меня было 100500 классов, то, естественно, классификатор у меня получится МЕЕЕЕДЛЕННЫЙ. А я хочу быстрый :)
Соотвественно, вопрос - куда бежать, если у меня 100500 классов, и 100-500 фич?
(Это я читаю про то, как работает akinator.com)
UPD: вот мой же вопрос на stats.stackoverflow.com со всем связанным матаном.
UPD: http://habrahabr.ru/blogs/artificial_intelligence/84364/ читал и использовал как один из основных источников информации
Пока у меня с десяток классов - все, естественно, идет неплохо. А если я захочу, чтобы у меня было 100500 классов, то, естественно, классификатор у меня получится МЕЕЕЕДЛЕННЫЙ. А я хочу быстрый :)
Соотвественно, вопрос - куда бежать, если у меня 100500 классов, и 100-500 фич?
(Это я читаю про то, как работает akinator.com)
UPD: вот мой же вопрос на stats.stackoverflow.com со всем связанным матаном.
UPD: http://habrahabr.ru/blogs/artificial_intelligence/84364/ читал и использовал как один из основных источников информации
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2011-01-07 09:47 pm (UTC)(no subject)
Date: 2011-01-07 10:21 pm (UTC)(no subject)
Date: 2011-01-07 09:51 pm (UTC)(no subject)
Date: 2011-01-07 10:25 pm (UTC)Можно (и нужно) еще читать http://habrahabr.ru/blogs/artificial_intelligence/84364 , где та же математика, но подробнее все расписано.
(no subject)
Date: 2011-01-07 09:58 pm (UTC)(можно ещё использовать сеть Кохонена, поиск главных компонент или ещё как уменьшить размерность пространства параметров - чтобы quadtree строить не по 100 фичам, а по 2-5)
Таким образом резко уменьшаем число проверяемых классов и радуемся.
(no subject)
Date: 2011-01-07 09:58 pm (UTC)(no subject)
Date: 2011-01-07 10:01 pm (UTC)Собственно, вариации на тему quadtree - по сути, тот же подход, просто кластеры тупо выбираем.
(no subject)
Date: 2011-01-09 04:56 pm (UTC)Я как-то не вижу подходящего решения. Подумаю еще.
(no subject)
Date: 2011-01-07 10:02 pm (UTC)(no subject)
Date: 2011-01-07 10:08 pm (UTC)2. 100500 не фич, а классов. Совершенно другой расклад (попроще, по ходу).
(no subject)
Date: 2011-01-07 10:14 pm (UTC)ну ок. тогда еще random projections в копилку dimension reduction methods.
(no subject)
Date: 2011-01-07 10:17 pm (UTC)(no subject)
Date: 2011-01-07 10:25 pm (UTC)И вообще, игра "животные" (см. http://en.wikipedia.org/wiki/Timeline_of_computer_viruses_and_worms ) - это 1975 год. Без всяких байесовских классификаторов. Примитивно, я сам такое в детстве на бейсике писал. И имеет смысл идти не от байесовского классификатора, а от дерева решений для такой игры - вводя в неё возможность неверных ответов и использования "лишних" вопросов для уточнения.
(no subject)
Date: 2011-01-07 10:41 pm (UTC)(no subject)
Date: 2011-01-07 11:20 pm (UTC)Вопрос не в обновлении, а в прощении ошибок - раз, в балансировке дерева (чтобы не вырастали мегадлинные цепочки вопросов) - два. Ну, наверное, ещё что-то.
И вообще, где дерево - там и лес ;-)
(no subject)
Date: 2011-01-09 04:57 pm (UTC)(no subject)
Date: 2011-01-09 08:00 pm (UTC)А вот сокращение длины цепочки - интересная задача.
Я тут подумал - нарисовались забавные намётки решения:
1. Держим не одно дерево, а целый лес.
2.
Вопросамответам присваиваем показатель ценности - грубо говоря, количество информации, полученной нами при движении вниз по дереву.Навскидку за основу берём энтропию: если для данного узла дерева с вероятностью p ответ "да" и q - ответ "нет", то веткам добавляем -log(p) и -log(q) к их ценности.
3. С определённой вероятностью (зависящей текущей набранной "ценности" и от сбалансированности остатка дерева) бросаем поиск по текущему дереву и перескакиваем на другое.
4. С определённой вероятностью бросаем поиск по текущему дереву, тупо добавляя в него вопрос из другого.
Только я не настоящий сварщик - в смысле, это ни разу не моя специализация, я всё больше по анализу изображений.
(no subject)
Date: 2011-01-09 08:06 pm (UTC)(no subject)
Date: 2011-01-07 10:22 pm (UTC)http://www.machinelearning.ru/wiki/images/7/78/BayesML-2010-Yangel-Akinator.pdf
(no subject)
Date: 2011-01-07 10:31 pm (UTC)Собственно, мне интересно, как развить вот этот результат, т.к. он таки действительно работает за O ( персон * вопросов * вариантов ответов ), что очень быстро превращается в О(дофига).
(no subject)
Date: 2011-01-08 10:51 am (UTC)Если Вы хотите использовать именно NBC, то Вам скорее всего потребуются отсечения. Если я верно все понял, Вы можете рассчитывать на однозначность ответов. Т.е. если персонаж Вася хороший, то P( хороший, да, Вася)=p, а P(хороший, нет, Вася) можно принять равным нулю.
Также можно выбрать для каждого персонажа набор релевантных вопросов, а все остальное занулить, соответственно распределение вероятностей нужно будет отнормировать. Получается что-то вроде сужения координат.
Правда это мои теоретические догадки :)
(no subject)
Date: 2011-01-09 04:58 pm (UTC)На самом деле ведь почти на любой вопрос кто-то отвечает "да", кто-то - "нет", а кто-то - "может быть"
(no subject)
Date: 2011-01-07 10:39 pm (UTC)(no subject)
Date: 2011-01-07 10:45 pm (UTC)(no subject)
Date: 2011-01-07 10:48 pm (UTC)(no subject)
Date: 2011-01-07 11:10 pm (UTC)(no subject)
Date: 2011-01-07 10:55 pm (UTC)(no subject)
Date: 2011-01-07 11:09 pm (UTC)Я вижу, что там просто забиты "Someone who click on No all the time" и т.п. в качестве вариантов ответов, и всё.
(no subject)
Date: 2011-01-07 11:35 pm (UTC)Хм, странно. Зигзагообразную оследовательность "да-возможно-не знаю-скорее, нет-нет-скорее, нет-..." поймал: Someone who clicked on all the options in order (I just wanted to see what would happen... I'm bored, okay?!)
а "да-нет-да-нет" - не поймал. Может быть, правда, я сам где-то сбился.
(no subject)
Date: 2011-01-08 08:00 am (UTC)(no subject)
Date: 2011-01-09 04:59 pm (UTC)(no subject)
Date: 2011-01-08 08:23 am (UTC)Машинное обучение тоже сейчас интенсивно копаю, т.к. надеюсь применить к одной своей задачке, но у меня там сначала data mining и потом exploiting, поэтому смотрю разные эволюционные методы, где это воедино слито. Жутко интересно это всё таки :)
Кстати, в качестве небольшого (офф?)топика - а вы не знаете ли хорошей поисковой системы по всяким (около-)научным публикациям и сайтам? Если гугель спрашивать в чистом виде, то очень утомляет продираться сквозь тыщи спамерских или барыжно-спрингеровских сайтов, когда нередко всё то же лежит в открытом доступе на сайте какого-нить нижне-оклахомского едушника и не отсвечивает за 101 страницей SERP'a... Пока остановился на своём варианте custom search, но вопрос его полноты, конечно, не простой. Может знаете более хорошие варианты?
(no subject)
Date: 2011-01-08 10:32 am (UTC)(no subject)
Date: 2011-01-08 10:44 am (UTC)(no subject)
Date: 2011-01-08 08:58 am (UTC)(no subject)
Date: 2011-01-08 09:01 am (UTC)(no subject)
Date: 2011-01-09 05:00 pm (UTC)(no subject)
Date: 2011-01-09 10:38 pm (UTC)(no subject)
Date: 2011-01-14 06:44 pm (UTC)Feature Selection
Date: 2013-01-15 10:39 am (UTC)