MatrixNet без формул
Теорию графов я изучал в институте. Не очень нужной оказалась. Напомнил о ней лишь в 2007 создатель живого журнала Бред наш Фицпатрик, когда на Google Developer Day рассказал про социальный граф. У теории графов такой набор терминов, что их и в институтах не изучают.
А в SEO из теории графов имеет значение вот что.
В основе поисковых алгоритмов обычно лежит функция релевантности, которая, по сути, оценивает соответствие того или иного документа запросу: чем выше ее значение, тем сильнее это соответствие. Функция релевантности - это функция двух аргументов: запроса (q) и документа (d).
А MatrixNet - это метод получения поисковой машиной Яндекса функций (в их обозначениях hk(q,d)), которые заданы деревом решений.
Что такое функция, заданная деревом решений? Рассмотрим в качестве простого примера конструкцию, представленную на рисунке.
Рисунок 1. Функция одного аргумента, заданная деревом решений.
Каждый узел дерева (жирная черная точка) содержит условие ветвления. Например, самый верхний узел (именуемый корнем дерева), содержит условие x<4. Если значение х, для которого мы хотим определить значение функции действительно меньше 4, то мы спускаемся вниз по левой ветви, т.е. в узел с условием x<2. Из этого узла мы также продолжаем движение вниз, пока не достигнем узла, в котором нет разветвления и вместо условия в нем записано искомое значение функции. Определим по дереву значение функции для х=1:
Начинаем из корня дерева, условие x<4 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1)=1.
Повторим операцию для х=2. x<4, да. Идем по левой ветке. х<2, нет. Идем по правой ветке. Значение функции f(2)=2.
Аналогично получаем f(3)=2, f(4)=3, f(5)=3, f(6)=4, f(7)=4, ..., f(10000)=4.
А теперь обратим внимание на следующие важные особенности функции, заданной деревом решений:
Для наглядности построим график этой функции:
Рисунок 2. График функции, заданной деревом решений.
Теперь усложним пример и рассмотрим функцию от двух переменных f(x1,x2) (рисунок 3.):
Рисунок 3. Функция двух аргументов, заданная деревом решений.
Вычислим значение функции для х1=1 х2=1.
Начинаем из корня дерева, условие x1<3 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x2<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1,1)=1.
Повторим операцию для х1=2, х2=2. x1<3, да. Идем по левой ветке. х2<2, нет. Идем по правой ветке. Значение функции f(2,2)=2.
Аналогично получаем f(3,1)=3, f(3,2)=4, f(3,3)=4 и т.д.
Теперь рассмотрим пример с hk(q,d). Главное отличие дерева для этой функции от рассмотренных выше в том, что условиями ветвления выступают не аргументы функции (q-запрос, d-документ), а некоторые функции от них f1(q,d), f2(q,d), именуемые признаками документа. В качестве признаков могут выступать: количество точных вхождений запроса в документ, количество точных вхождений в заголовок документа, количество вхождений лемм слов запроса в документ, длина документа и т.д. В общем все то, что Яндекс считает свойствами документа, а также комбинации этих свойств (например произведения). Рассмотрим простенькое дерево для функции h(q,d). (рисунок 4):
Рисунок 4. Пример простейшего дерева для функции h(q,d).
В нашем примере f1(q,d) - TF - число вхождений лемм слов запроса в документ, f2(q,d) - отношение числа вхождений леммы в заголовок документа к длине заголовка, f3(q,d) - отношение числа вхождений леммы в теги H1-H6 к длине текста включенного в эти теги.
Пусть некоторый документ d при запросе q имеет следующие свойства: f1(q,d)=5, f2(q,d)=1 f3(q,d)=0,2. Найдем значение функции h(q,d) для этого документа:
f1(q,d)<10, да. Спускаемся по левой ветви.
f2(q,d)<0,5, нет. Спускаемся по правой ветви.
f3(q,d)<0,2, да. Спускаемся по левой ветви.
Результат h(q,d)=3.
Реальные деревья решений, полученные при помощи алгоритма MatrixNet, обладают следующими свойствами:
Глубина (т.е. число горизонтальных уровней или число ветвлений) дерева - число ограниченное. По некоторым данным это ограничение равно 10, т.е. на нижнем (10-м) уровне имеется 210 - узлов соответствующих значениям фунции h(q,d). По другим данным - глубина деревьев равна 6.
На каждом уровне ветвление происходит по одному и тому же условию (собственно, только такие примеры мы и рассматривали). Т.е. всего в каждой функции может использоваться не более 10-ти (или 6-ти) признаков документа.
Эти два условия и являются особенностью метода MatrixNet.
Ну и в заключении еще раз отметим основные особенности функций hk(q,d) заданных деревом. Во-первых, кусочно-постоянный характер функций дает следующий эффект. Документы с незначительно отличающимися значениями свойств могут восприниматься алгоритмом как равнозначные. При этом один документ может быть «чуть более» релевантным относительно другого, однако значение функции hk(q,d) у них будет одинаковым.
Для пояснения этого эффекта рассмотрим два документа d1 и d2, запрос один и тот же q. Каждый из документов имеет следующие признаки первый: f1(q,d1)=2, f2(q,d1)=0,1 f3(q,d1)=0,1, второй: f1(q,d2)=9, f2(q,d2)=0,4 f3(q,d2)=0,2. Определим значения h(q,d), дерево решений которой представлено на рисунке 4, для этих двух документов: h(q,d1)=1, h(q,d2)=1. Как видно, значения признаков отличаются довольно сильно, а значения функции h(q,d) у документов одинаковое.
Обратная сторона этой медали, документы с незначительно отличающимися свойствами могут иметь сильно отличающиеся значения функций hk. Опять рассмотрим два документа с признаками: f1(q,d1)=9, f2(q,d1)=0,4 f3(q,d1)=0,2, второй: f1(q,d2)=10, f2(q,d2)=0,5 f3(q,d2)=0,3. Значения функции h для документов равны h(q,d1)=1, h(q,d2)=8. Разница между значениями признаков у документов незначительна (существенно меньше, чем в предыдущем примере), при этом значения функции h(q,d) отличаются очень сильно.
Во-вторых, это непрямая зависимость функций от свойств документа, которая делает поведение функций hk и в конечном итоге фунции релевантности в зависимости от fi(q,d) более непредсказуемым с точки зрения внешнего анализа.
В чем была настоятельная необходимость вводить Matrixnet? Хотелось научить машину хотя бы частично выполнять функции асессоров. В результате был разработан алгоритм обучения поисковой машины и уменьшилось количество ошибочных оценок важности тех или иных факторов. Говоря проще, поисковая машина, обученная с помощью MatrixNet, перестала выдавать желаемое за действительное, придавая несущественным поисковым критериям большой вес.
Возможность точной настройки процедуры ранжирования позволяет отсеивать, так сказать, нетематические страницы, содержащие тематические запросы.
А в SEO из теории графов имеет значение вот что.
В основе поисковых алгоритмов обычно лежит функция релевантности, которая, по сути, оценивает соответствие того или иного документа запросу: чем выше ее значение, тем сильнее это соответствие. Функция релевантности - это функция двух аргументов: запроса (q) и документа (d).
А MatrixNet - это метод получения поисковой машиной Яндекса функций (в их обозначениях hk(q,d)), которые заданы деревом решений.
Что такое функция, заданная деревом решений? Рассмотрим в качестве простого примера конструкцию, представленную на рисунке.
Рисунок 1. Функция одного аргумента, заданная деревом решений.
Каждый узел дерева (жирная черная точка) содержит условие ветвления. Например, самый верхний узел (именуемый корнем дерева), содержит условие x<4. Если значение х, для которого мы хотим определить значение функции действительно меньше 4, то мы спускаемся вниз по левой ветви, т.е. в узел с условием x<2. Из этого узла мы также продолжаем движение вниз, пока не достигнем узла, в котором нет разветвления и вместо условия в нем записано искомое значение функции. Определим по дереву значение функции для х=1:
Начинаем из корня дерева, условие x<4 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1)=1.
Повторим операцию для х=2. x<4, да. Идем по левой ветке. х<2, нет. Идем по правой ветке. Значение функции f(2)=2.
Аналогично получаем f(3)=2, f(4)=3, f(5)=3, f(6)=4, f(7)=4, ..., f(10000)=4.
А теперь обратим внимание на следующие важные особенности функции, заданной деревом решений:
- Она кусочно-постоянная. Т.е. на некоторых интервалах при изменении х, значение самой функции не меняется. Например, при 2<=х<4 (т.е. при х от 2 до 3,999999999....) f(x)
- При переходе х через условие ветвления, функция меняется скачком. Например, f(3,9999999)=2, f(4)=3.
Для наглядности построим график этой функции:
Рисунок 2. График функции, заданной деревом решений.
Теперь усложним пример и рассмотрим функцию от двух переменных f(x1,x2) (рисунок 3.):
Рисунок 3. Функция двух аргументов, заданная деревом решений.
Вычислим значение функции для х1=1 х2=1.
Начинаем из корня дерева, условие x1<3 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x2<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1,1)=1.
Повторим операцию для х1=2, х2=2. x1<3, да. Идем по левой ветке. х2<2, нет. Идем по правой ветке. Значение функции f(2,2)=2.
Аналогично получаем f(3,1)=3, f(3,2)=4, f(3,3)=4 и т.д.
Теперь рассмотрим пример с hk(q,d). Главное отличие дерева для этой функции от рассмотренных выше в том, что условиями ветвления выступают не аргументы функции (q-запрос, d-документ), а некоторые функции от них f1(q,d), f2(q,d), именуемые признаками документа. В качестве признаков могут выступать: количество точных вхождений запроса в документ, количество точных вхождений в заголовок документа, количество вхождений лемм слов запроса в документ, длина документа и т.д. В общем все то, что Яндекс считает свойствами документа, а также комбинации этих свойств (например произведения). Рассмотрим простенькое дерево для функции h(q,d). (рисунок 4):
Рисунок 4. Пример простейшего дерева для функции h(q,d).
В нашем примере f1(q,d) - TF - число вхождений лемм слов запроса в документ, f2(q,d) - отношение числа вхождений леммы в заголовок документа к длине заголовка, f3(q,d) - отношение числа вхождений леммы в теги H1-H6 к длине текста включенного в эти теги.
Пусть некоторый документ d при запросе q имеет следующие свойства: f1(q,d)=5, f2(q,d)=1 f3(q,d)=0,2. Найдем значение функции h(q,d) для этого документа:
f1(q,d)<10, да. Спускаемся по левой ветви.
f2(q,d)<0,5, нет. Спускаемся по правой ветви.
f3(q,d)<0,2, да. Спускаемся по левой ветви.
Результат h(q,d)=3.
Реальные деревья решений, полученные при помощи алгоритма MatrixNet, обладают следующими свойствами:
Глубина (т.е. число горизонтальных уровней или число ветвлений) дерева - число ограниченное. По некоторым данным это ограничение равно 10, т.е. на нижнем (10-м) уровне имеется 210 - узлов соответствующих значениям фунции h(q,d). По другим данным - глубина деревьев равна 6.
На каждом уровне ветвление происходит по одному и тому же условию (собственно, только такие примеры мы и рассматривали). Т.е. всего в каждой функции может использоваться не более 10-ти (или 6-ти) признаков документа.
Эти два условия и являются особенностью метода MatrixNet.
Ну и в заключении еще раз отметим основные особенности функций hk(q,d) заданных деревом. Во-первых, кусочно-постоянный характер функций дает следующий эффект. Документы с незначительно отличающимися значениями свойств могут восприниматься алгоритмом как равнозначные. При этом один документ может быть «чуть более» релевантным относительно другого, однако значение функции hk(q,d) у них будет одинаковым.
Для пояснения этого эффекта рассмотрим два документа d1 и d2, запрос один и тот же q. Каждый из документов имеет следующие признаки первый: f1(q,d1)=2, f2(q,d1)=0,1 f3(q,d1)=0,1, второй: f1(q,d2)=9, f2(q,d2)=0,4 f3(q,d2)=0,2. Определим значения h(q,d), дерево решений которой представлено на рисунке 4, для этих двух документов: h(q,d1)=1, h(q,d2)=1. Как видно, значения признаков отличаются довольно сильно, а значения функции h(q,d) у документов одинаковое.
Обратная сторона этой медали, документы с незначительно отличающимися свойствами могут иметь сильно отличающиеся значения функций hk. Опять рассмотрим два документа с признаками: f1(q,d1)=9, f2(q,d1)=0,4 f3(q,d1)=0,2, второй: f1(q,d2)=10, f2(q,d2)=0,5 f3(q,d2)=0,3. Значения функции h для документов равны h(q,d1)=1, h(q,d2)=8. Разница между значениями признаков у документов незначительна (существенно меньше, чем в предыдущем примере), при этом значения функции h(q,d) отличаются очень сильно.
Во-вторых, это непрямая зависимость функций от свойств документа, которая делает поведение функций hk и в конечном итоге фунции релевантности в зависимости от fi(q,d) более непредсказуемым с точки зрения внешнего анализа.
В чем была настоятельная необходимость вводить Matrixnet? Хотелось научить машину хотя бы частично выполнять функции асессоров. В результате был разработан алгоритм обучения поисковой машины и уменьшилось количество ошибочных оценок важности тех или иных факторов. Говоря проще, поисковая машина, обученная с помощью MatrixNet, перестала выдавать желаемое за действительное, придавая несущественным поисковым критериям большой вес.
Возможность точной настройки процедуры ранжирования позволяет отсеивать, так сказать, нетематические страницы, содержащие тематические запросы.