Поисковик-затейник ([info]itman) wrote in [info]ru_ir,
@ 2008-05-02 17:00:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Entry tags:google, pagerank, qbic

Пейджранк на ненаправленном графе
Мой недавний квест получил интересное "продолжение" в виде статьи гугловских ресерчеров. Jing и Baluja описали эксперименты по частичному ранжированию множества изображений с помощью PageRank. PageRank они рассчитывают на графе похожести изображений. Авторы отмечают, что полученный граф является симметричным, но не пытаются дать глубокое метафизическое обоснование.


(Post a new comment)


[info]dp_maxime
2008-05-02 09:30 pm UTC (link)
Хм, а этого обоснования разве не достаточно ?

... symmetrical adjacency matrix S where Su,v measures the visual similarity between image u and v. Since we assume similarities are commutative, the adjancy matrix is undirected.

(Reply to this) (Thread)

[info]itman
2008-05-02 09:36 pm UTC (link)
Это не обоснование, это "отмечают, что полученный граф является симметричным". И что? В прошлый раз я задавался вопросом в духе: сила пейджранк в том, что "подправляет" голосование ссылками по принципу: "более влиятельный имеет больший вес при голосовании". Если процесс взаимный, то есть реципиент всегда что-то возвращает донору, идея перестает работать, а я перестаю понимать, что же именно считает PR? Некий центры кластеров, или что-то еще?

(Reply to this) (Parent)(Thread)

[info]dp_maxime
2008-05-02 10:29 pm UTC (link)
Это как раз-таки обоснование, он симметричный потому, что они по определению считают операцию похожести картинок коммутативной.

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

(Reply to this) (Parent)(Thread)

(Anonymous)
2008-05-07 10:24 am UTC (link)
Voobsche, PageRank uzla na undirected graph eto degree uzla. Chto tut schitat'-to?

(Reply to this) (Parent)(Thread)

[info]itman
2008-05-07 01:48 pm UTC (link)
Это только в случае, когда нет затухания.

(Reply to this) (Parent)

[info]dp_maxime
2008-05-07 07:39 pm UTC (link)
Не является он степенью узла, т.к. все страницы имееют в общем разное число исходящих ссылок.

(Reply to this) (Parent)(Thread)

(Anonymous)
2008-05-21 11:17 am UTC (link)
PageRank это вектор, на i-ом месте стоит степень i-ого узла когда параметр затухания = 1 (спасибо за ответ выше). А входящих и исходящих ссылок в ненаправленном графе нет.

(Reply to this) (Parent)(Thread)

[info]dp_maxime
2008-05-21 12:48 pm UTC (link)
PageRank страницы - это число, равное сумме PageRankов всех страниц, ссылающихся на данную, поделенных на число ссылок с этих страниц.
http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=6285999

(Reply to this) (Parent)(Thread)

[info]itman
2008-05-21 01:56 pm UTC (link)
помноженное на коэффициент затухания плюс скобка открывается единица минус коэффициент затухания скобка закрывается деленное на число документов

(Reply to this) (Parent)

[info]itman
2008-05-21 01:57 pm UTC (link)
Да, но мы говорим не про вырожденный случай :-)

(Reply to this) (Parent)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…