![[info]](../../../img/userinfo.gif){kind=small}
tiphareth) wrote,@ 2001-06-07 21:24:00
| Misha Verbitsky (tiphareth) wrote, @ 2001-06-07 21:24:00 |
| Current mood: | mean |
| Current music: | Mayhem - Deathcrush |
Яндекс и лохотрон - второй раунд
В комментах воюют граждане, интересующиеся Яндексом
http://www.livejournal.com/talkread.b
Позиция Яндекса, как я понял, сводится к следующему:
персонал Яндекса - люди идейные, неприемлющие спам и
скрытую рекламу, и поэтому не торгуют результатами.
Ну что ж, в России еще есть люди, которым начхать на
условия рынка. И это очень хорошо.
Я готов вполне поверить, если мне объяснят две вещи:
1. Почему алгоритм вычисления релевантности держится в
секрете
2. И ежели этот алгоритм похож на тот, что у Гугля,
то каким образом определяется, от каких сайтов
ведется отсчет (по формуле, которую цитировал
Лихачев, релевантность определяется рекурсивно; значит,
каким-то сайтам она задана от балды; разумеется,
манипулируя этими сайтами, можно получить более-менее
любой результат).
Вопрос на самом деле математический.
Пусть у нас есть граф, вершины
документы, ссылки ребра. Есть ли способ вычислить
релевантность таким образом, чтобы формула, приведенная
Лихачевым, была точна? И если есть, то сколько
таких способов?
Формула вот
http://www.livejournal.com/talkread.b
У меня есть два предположения:
(а) Пусть вычисление релевантности ведется
последовательными приближениями
(т.е. задаем PR всем сайтам по единичке, потом вычисляем
PR по формуле
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) (*)
нормализуем, повторяем).
Тогда оно не сойдется, т.е. для большинства графов у
этого аффинного оператора будет настолько большой
разброс собственных значений, что рекурсия приведет
к хаотическим флуктуациям
(б) Пространство распределений релевантности, примерно
удовлетворяющих формуле (*), плотно в достаточно большой
области параметров, для достаточно сложного графа.
То есть релевантность "по гуглю" можно писать более-менее
от балды. Разумеется, именно так она и пишется: гугль
берет за точку отсчета какие-то родственные ему сайты,
затем инкрементально меняет релевантность при
добавлении новых документов.
То есть вопрос о алгоритме подсчета релевантности это вопрос
о власти. Как и все вопросы.
А где власть - там и секретность.
Так я понимаю политику Яндекса.
Такие дела
Миша.
 | dm_lihachev
2001-06-07 17:26 (link) |
| ""значит, каким-то сайтам она задана от балды"" в кач. балды запросто можно брать посещаемость, хотя это и несколько противоречит ""значимость непопулярных, но качественных сайтов"", но таки кол-во показов ссылки - существенно -- тот же баннер на сам деле ""рекурсия приведет к хаотическим флуктуациям"" пошто вдруг? тут не физика - ежли формулу колбасит, то просто берется оная формула и меняется - чтоб не колбасило... Т.е. ежли обывательски - есть впечатление, что можно добьиться штоб сходилось решение, то значит и формулу такую можно нарисовать, штоб оно сходилось но конешно эту "эмпирику" стоит держать в публичном месте, я и по форуму порылся, но что-то там ничего такого нету, можно спросить, ежли Илья обещает, что типа не РЖ и не ливер, там мы подробно отвечать горазды что до манипулирования этими ранками, то вот пошто я в это дело не верю -- таки джинса (а это именно джинса, так?) - реклама второй свежести, на нее и в тв смотреть тошно, оно бъет и по рекламодателю (типа не настолько крут, чтоб настоящюю рекламу купить, экономит) и по носителю (ворует)... А ежли на интернете и настоящую рекламу продать проблема, заглушки сплошные везде смотрю -- то кто ж будет покупать джинсу?? но конешно *возможность* манипулирования есть, и правильный ход мыслей - что процедуры расчетов д.б. публичны и воспроизводимы - типа аудита, не нра - сам пересчитай (Reply to this) (Thread) |
| tiphareth
2001-06-07 17:53 (link) |
>тут не физика - ежли формулу колбасит, то просто берется оная формула > и меняется - чтоб не колбасило... (а) я не уверен, что это возможно - граф огромный, и даже если бы формула была линейная (а она аффинная), найти собственные вектора соответствующего линейного оператора - задача теоретически нерешаемая. И инкрементальный метод решения не дает именно потому, что траектория решений соотв. дифференциального уравнения довольно хаотическая. и (б) проще сначала задать от балды правдоподобный рейтинг, а затем его инкрементально (косметически) править; это, видимо, единственный способ приближенно решать (неразреженные) линейные уравнения с миллионами переменных. Про более сложные уравнения я не говорю (гуголевское в общем более сложное, хотя сводится к линейному). Умной вещью было бы добавить в формулу квадратичный член, который создавал бы затухание, и после этого искать приближенное решение последовательными приближениями, что будет (тогда) возможно. Но гуголь до этого не додумался, и Яндекс, я подозреваю, тоже. То есть выход один - гнать туфту, чего они и делают, с удовольствием. По поводу же джинсы - Яндекс это холдинг, у всякого холдинга есть корпоративная политика поддерживать союзников и мочить тех, с кем отношения натянутые. Естественно при выборе модели, от которой начинать рекурсию, ставить свои ресурсы на первое место. А скажем фашистов каких-нибудь, коммунистов и педофилов ставить на последнее, даже если у них цитируемость как у рамблер.ру. Вот это я и имею в виду под подтасовками - нигде не декларируемый произвол в выборе начальных значений приведет к любому заданному наперед распределению релевантности основных игроков. Такие дела Миша. (Reply to this) (Parent) (Thread) |
| dm_lihachev
2001-06-08 06:33 (link) |
| ""граф огромный, и даже если бы формула была линейная (а она аффинная), найти собственные вектора соответствующего линейного оператора - задача теоретически нерешаемая. я ежли честно из выч.мат помню только что там все нерешаемое, что из жизни и без отрывания всего, что можно и нельзя отрывать.. Но напр мой УниКальк - сожрал бы это дело и не подавился бы. Т.е. порядка 100К сайтов? семечки. Мы вот когда у Кургиняна трудались на Вспольном -- заливали в него - типа моделирования макроэкономики - там дес. тыс. уравнений, и нелинейные и ступеньками, типа ставок налогов - и все это сходилось на там чуть ли не 286-386.. Кст, каж и до сих пор в думе эту поделуху крутят - хотя точно не знаю Т.е. теории эти выч.матовские - эт студентов мучить, штоб водки меньше пили:) кст. не будь Нариньяни такой крез, все эти поискалки - наше все, мы б могли и делать, да у него какие-то приоритеты с интернетом не вяжутся абс... :( Почему и ушел - грустно все это дело.. """видимо, единственный способ приближенно решать (неразреженные) линейные уравнения с миллионами переменных ни, с 80-х - не единственный, Тыугу, Нариньяни, недоопределенные модели, уникальк, раздаем все диапазоны рейтинга там от 0 до беск. - и начинаем крутить - все сходится, ежли не сходится - значит формула кривая, оно *должно* сходиться, и должно сходиться, а не играть в зависимости от начальных условий.. Это таки проще всех этих наших сапровских и/или экономических задачек - т.к. формулу можно и нужно рихтовать, штоб она была хшая но вообще, они все конешно умных машинок типа уникалька пока еще не пользуют, эт они зря - надо-надо им уникальк впарить:) я когда-то про это дело пытался и с Крюковым и с разными людьми из яндеха говорить, но как-то они ищо не созрели.. Вообще интернет как-то - как эмбрион, осваивает все програмерские кнов-хавы последовательно, вот щас где-то с 60х на 70е перебирается, а что до манипулирования - как минимум, есть 3-4 холдинга, и ежли будут хоть какие-то расхождения -- то всем мало не покажется, так ведь? Т.е. возможно только одна технологическая отмазка, которую счетчики вот активно использовали -- что де связь с машинами из *нашей-сети* - гораздо лучше, так что и у них есть такое технологическое типа преимущщество. на сам деле получа, что вы с Ильей одно и тож говорите - нет? т.е. он - что типа оно все так сложно-запутано, что рассказать/расписать ничего не можно-сложно, но мы честны-пушисты, вы - никто не честен-не пушист, но все действительно так сложно-нерешаемо,.. а на сам деле - все просто, общий объем рунету счас такой, что его проще рассчитать, чем там ремонт какой-нить подлодки в Славянке - сотни тыс. деталек и тр.пр. - а ниче, брали ЕС ЭВМ, колоду перфокарт - и все от зубов отлетало:) (Reply to this) (Parent) |
| iseg
2001-06-09 09:17 (link) |
| Для гарантированной сходимости стоит коэффициент. "d". Он меньше 1. Приведенное преобазование - сжимающее. На эту тему есть теорема Фробениуса-Перрона. Еще ребята рекомендуют книжку Гантмахера. :) Про родственные сайты - это фантазия редкостного вдохновения. Если уж портить выдачу - то зачем так сложно? :) Формула искалки отсутвует в открытом доступе по одной простой причине - ее не существует. Ни у кого. Их (формул) у каждой искалки два десятка в самых разных местах. Факторы все (по крайней мере, яндекс) честно перечисляют. Конкретные коэффициенты и виды функций ничего никому не скажут. Конечно же функции из классического IR (или их близкие подобия) используются в той или иной степени всеми. (Reply to this) (Thread) |
| tiphareth
2001-06-09 13:00 (link) |
Это хуйня, извините. Идет речь о системе линейных уравнений X_i = 1-d + d \sum (T_{ij} X_j) с произвольными значениями коэффициeнтов T_{ij}. Что изменится, если изменить коэффициент d, я не вижу - это эквивалентно изменению T_{ij} в соответствующее количество раз и все. Сжимающим это отображение было бы, если бы все собственные значения оператора X_i -> d \sum (T_{ij} X_j) были бы меньше 1 (это если оператор полупрост). То есть Ваше выступление не только выглядит нечистоплотно, оно еще и предельно непрофессионально. Фе. Яндексу два балла, что не может найти себе сколько-нибудь профессиональных пиарщиков. Причем в Яндексе первая же ссылка на слова "сжимающее отображение" дает вполне вразумительную статью о предмете нашего обсуждения http://www.issep.rssi.ru/pdf/9705_118.P Сходите типа юноша, просветитесь. Школьный курс типа. Такие дела Миша. (Reply to this) (Parent) (Thread) |
| tejblum
2001-06-09 16:52 (link) |
| Да-а-а-а. Демонстрируемый Вами уровень мышления не дотягивает не толкько до PhD математики, но и до первокласника: если бы T_{ij} были произвольными, так бы, наверно, и было сказано в определении PageRank'а. Там, однако, сказано, что
T_{ij} = | 1/C(j), если есть ребро из j в i
| 0, если такого ребра нет,
где C(j) - число ребер, выходящих из j. Это, как ни странно, довольно сильное ограничение. Например, довольно очевидно, что матрица T_{ij} стохастическая.
(Reply to this) (Parent) |
| tiphareth
2001-06-10 04:21 (link) |
Вы чего-то не понимаете. Контрпример строится элементарно. Берем граф с N вершиной и N ребрами, которые все идут в одну вершину (т.е. все документы ссылаются на один). Это соответствует матрице, у которой одна строка состоит из чисел d, остальные нули. Такая матрица ну никак не задает сжимающее отображение. Например, вектор (1,1,1...,1) (длины равной корню из N = размерности пространства) переводится в (Nd, 0, 0, 0, ...), длины Nd; для d=0.85, это не сжимающее отображение уже при N=2. Действительно, из стохастичности можно получить оценку на собственные значения; в случае матрицы, которая не полупроста, сжимающего отображения все равно не получится. Такие дела Миша. (Reply to this) (Thread) |
| tejblum
2001-06-10 06:44 (link) |
| Вы чего-то не понимаете. Я в математике действительно очень много чего не понимаю (и, к сожалению, забыл практически все, что знал). Да, в общем-то, не очень-то и обязан - я в отличие от некоторых не PhD. Это, однако, не имеет отношения к предмету дискуссии: мы обсуждали, сходится PR или нет. Вы же, однако, опять ни доказали его сходимость, ни даже не привели контрпример (граф с расходящимся PageRank'ом). Так что вам двойка. ...Такая матрица ну никак не задает сжимающее отображение... А давайте в качестве нормы возьмем не ваш дурацкий квадратный корень, а сумму абсолютных величин координат. Ничем ведь не хуже, правда? А это отображение становится сжимающим. Остаток доказательства сходимости PageRank'а опять оставляю в качестве упражнения. Кстати, высказанные мною или Ильей идеи использовать не обязательно. Также разрешается пользоваться литературой, например, статьями, найденными по запросу PageRank. Дима (Reply to this) (Parent) |
| snyders
2001-06-10 08:32 (link) |
| 1. I think both sides may benefit from reading original google page-ranking paper , some other related papers I've put here . One of the convenient models is that of a Markov chain: webpages -- nodes, hyperlinks -- transitions. Corresponding transition matrix M is the matrix that you discuss. If Markov chain is irreducible (there is a path from each vertex to each vertex) then it has a limit probability distribution L (Frobenius-Perron theorem). One can pick arbitrary prob. vector V [for ex.(1/N, 1/N,...,1/N)] as initial "rank"-distribution and after sufficiently many iterations: M^k*V will be close to L. This L is the "fair" rank distribution that we are looking for. However web-graph does not lead to irreducible Markov chain, since there are sites that have no outgoing links. If one takes a random walk in the web one will be finally stuck in one of those. Solution: "Let's jump to a random site if we are stuck" (corresponds to connecting each terminal node to all the other nodes in the graph). This explains the factor d in the formula. However the graph is still not strongly connected since there can be "sinks". In a simplest case consider two nodes that point to each other and suppose that there is a link to one of these nodes from the outside. At each iteration these two nodes will be accumulating the probability mass.. Google paper suggests a solution of adding vector E which will balance the deficiency of the prob. mass due to sinks. The choice of vector E allows to play with the ranks as you like, see the paper... 2. Google was started as an academic project (Stanford), papers and even source code was on the net. Now it is a commercial enterprise it's know-how is not published. The fact that the issue of ranking is not resolved by a single formula is obvious: if it were so simple all search engines on the net would be as good as Google, but they are not (my opinion). 3. Google is great at ranking [and IMHO he who rules the ranking -- rules the net], it has also a great feature of "cached pages". Also, it can show you all citations made to your cite (can it be done in yandex?) 4. Annoying in Google is its poor query language. It also searches for the words literally (looking for "apple" will not find "apples"). What is cool in yandex is that it has morph-engine and a rich query syntax. (Reply to this) (Thread) |
| tiphareth
2001-06-11 08:08 (link) |
Yes! Thank you for an extremely informative and coherent reply! It answers all points I raised. Кроме следующего философического наблюдения: невероятно трудно построить математическую модель гуманитарного дискурса, поскольку при попытке ее построить мы немедленно натыкаемся на вопросы математической невычислимости (так, лотмановские работы по применению колмогоровской энтропии к стиховедению немедленно опровергаются тем, что невозможно вычислить энтропию естественного языка) либо на хаотические структуры в динамических системах (к чему, мне думалось, сводятся проблемы корректного page ranking-а). У разных людей имелись мысли о том, что эти два предмета связаны; никаких работ в этом направлении, кажется, не делалось. То, что невычислимость есть ключ к человеческому мышлению - доказывает Пенроуз. http://imperium.lenin.ru/EOWN/eown4/pen Очень убедительно, мне кажется. Буду читать статью и думать. Такие дела Миша. P. S. By the way, the "cached pages" feature and the search of all links to your page were all introduced in Altavista, about 4 years ago I think. I distinctly remember Nossik writing in VI about this stuff. (Reply to this) (Parent) |
| snyders
2001-06-10 09:16 (link) |
| I see that yandex also has the citation feature: #link="www...." it was even used in the 1st discussion. |
| janetg
2002-01-18 02:58 (link) |
| В своем принципиальном устройстве он известен и описан, и регулярно подвергается обсуждению в местах типа searchengines.ru. Что же касается деталей, тут есть одна очень большая тонкость: больше всего в знании точных деталей алгоритма релевантности заинтересованы... кто? Правильно, поисковые спаммеры. Т.е. те, кто хочет раскрутиться за счет поисковой системы, подняв свой сайт повыше в выдаче. А их интересы в общем случае противоположны интересам пользователей поисковой системы, которые хотят видеть наверху выдачи самые интересные сайты, а не сайты самых ушлых вебмастеров. |
[ Home | Update Journal | Login/Logout | Browse Options | Site Map ]