Прим переводчика
Вообще я продакт, часто приходилось привлекать дата сайентистов к сложным случаям в датасетах, но не припомню, чтобы применяли или хотя бы обсуждали другие меры кроме простых линейных корреляций. Поэтому заинтересовался и для лучшего понимания перевёл. P.s. у кого ещё нет ачивок за добавление статей в википедию — про Василия Хёфдинга много пустых страниц.
Предположим, у вас есть две последовательности чисел, которые вы хотите сравнить, чтобы измерить, насколько они связаны или зависимы друг от друга. Это действительно довольно общий сеттинг: две последовательности могут представлять временные ряды, так что у вас есть таблица с тремя столбцами и кучей строк. Первый столбец будет временем (скажем, с часовыми интервалами), а затем по одному столбцу для каждой последовательности; первый, например, может быть средней ценой акции за этот интервал, а второй - объемом торгуемых акций за этот интервал. Или вы могли бы сравнить процентное изменение цены одной акции по сравнению с другой. Конечно, это вовсе не обязательно должны быть временные ряды: у вас также может быть всего два столбца (то есть вообще без столбца времени). Первый может быть ростом американца старше 30 лет в дюймах, а второй — весом того же человека в фунтах. Или, чтобы использовать более актуальный пример, каждый столбец может представлять вектор эмбеддингов некоторых предложений на английском языке от определенной модели LLM. Первый столбец может быть вектором от модели Mixtral 8x7B для строки "I love my 3 sons" (Я люблю моих трех сыновей), а другой — от той же модели для строки "I cherish my 5 daughters" (Я дорожу моими пятью дочерьми).
В каждом из этих случаев у нас есть две последовательности данных, которые мы хотим сравнить. Проблема заключается в том, что в самой общей ситуации мы не имеем ни малейшего представления о том, какова может быть природа связи, или даже есть ли связь, о которой стоит говорить. Что, если две последовательности полностью независимы, как записи бросков двух разных честных кубиков? Что, если данные немного искажены и содержат некоторые экстремальные выбросы, которые искажают наиболее общие виды мер, на которые вы могли бы захотеть посмотреть, такие как среднее значение и дисперсия каждого столбца отдельно? Вы могли бы подумать сейчас: «Погодите, разве ответ на это — просто посмотреть на корреляцию?» И это действительно хорошая идея для проверки, поскольку это наиболее часто используемая мера ассоциации между двумя наборами данных.
Чтобы уточнить наши термины, под «корреляцией» обычно подразумевается коэффициент корреляции Пирсона, который появился в 1800-х годах. Эта корреляция на самом деле просто пересчитанная ковариация между данными, чтобы дать меру, которая не зависит от конкретных используемых единиц. Но тогда, что такое ковариация? Интуитивно вы сначала смотрите на каждую из последовательностей по отдельности и вычисляете ее среднее значение. Затем смотрите, как отдельные точки данных для этой последовательности отклоняются от этого среднего (то есть вы просто вычитаете каждую точку данных из среднего значения для этой последовательности). Затем вы сравниваете эти меры для каждой последовательности, умножая их друг на друга. Если последовательности демонстрируют схожий паттерн: когда запись в первой последовательности имеет тенденцию быть больше, чем среднее значение для этой первой последовательности «в то же время», как это справедливо для второй последовательности — то это предполагает, что они связаны, и произведение этих мер будет выше. (Я поставил «в то же время» в кавычки, потому что на самом деле мы имеем в виду «в K-й записи для обеих последовательностей», поскольку последовательности не обязаны быть временными рядами; говорить о времени просто упрощает понимание). Если последовательности действительно не имеют ничего общего друг с другом (как в случае с бросками игральных костей), то это произведение будет близко к нулю, поскольку с такой же вероятностью одна из последовательностей может иметь запись, значение которой выше ее среднего значения, в то время как в другой последовательности есть запись, значение которой ниже ее среднего значения.
Корреляция Пирсона, при которой мы масштабируем ковариацию, чтобы получить безразмерное число, дает хороший, легко интерпретируемый результат: она всегда находится между -1,0 и 1,0; если оно равно или 0,0, то между последовательностями «нет связи»; если 1.0, то они прекрасно коррелируют друг с другом и движутся синхронно. Если это -1,0, то все наоборот: когда один растет, другой падает на такую же величину. Так что это звучит как довольно хорошая мера, не так ли? В чем именно проблема? Проблема в том, что, когда вы используете корреляцию Пирсона, вы неявно ищете определенный вид отношений между двумя последовательностями: линейную связь. И в жизни есть много-много вещей, которые вы, возможно, захотите сравнить, но которые даже отдаленно не являются линейными по своей природе.
Давайте воспользуемся некоторыми конкретными примерами, чтобы сделать вещи более осязаемыми, и воспользуемся упомянутым выше примером роста и веса людей. Мы ожидаем, что здесь будет примерно линейная зависимость. Конечно, есть очень низкие, но очень толстые люди, а есть очень высокие, но очень худые люди, но в среднем мы ожидаем, что будет примерно линейная зависимость. Так что, если вы посмотрите на диаграмму рассеяния, показывающую рост по оси X и вес по оси Y, где каждая точка представляет человека в вашей выборке, при этом достаточное количество людей взято из совокупности в целом без смещения, вы сможете получить приблизительную модель, подобрав линию этим данным. Степень точности этой модели по сравнению с фактическими точками данных в деталях называется R-квадратом; по сути, это то, какой процент дисперсии одной последовательности данных объясняется другой.
В этом случае корреляция Пирсона работает хорошо, и поскольку ее относительно просто и быстро вычислить (вы можете легко сделать это, например, в Excel), а также легко понять и интерпретировать, она стала «популярной» мерой связи или зависимости. Однако можно придумать множество других ситуаций с очевидной и наглядной связью между двумя последовательностями данных, которая не является такой линейной. Например, подумайте о весе взрослого человека и его максимальной скорости, достигнутой в забеге на 100 метров с максимальной возможной скоростью. Можно предположить, что у очень худых людей может быть не так много быстро сокращающихся мышц ног, и поэтому они могут быть более медленными, а затем, когда вес сначала увеличивается, средняя максимальная скорость увеличивается. Но тогда очевидно, что люди с избыточным весом будут бежать медленнее, поэтому средняя максимальная скорость в какой-то момент начнет падать, а затем резко упадет, как только вес достигнет уровня очень болезненного ожирения. Короче говоря, это не то, что вы могли бы очень хорошо соотнести. Проблема с корреляцией Пирсона в том, что в такой ситуации она ненадежна.
Ранее упоминался еще один недостаток корреляции Пирсона: чувствительность к выбросам. Что произойдет, если человек, вводящий данные о бегунах, перепутал и пропустил номер? Или добавили к весу кого-то из людей несколько нулей? Даже если у вас есть набор данных из тысячи человек, если один из людей ошибочно введен в данные как весящий 2 миллиона килограмм, это может сильно испортить все ваши измерения. И хотя этот конкретный пример может показаться надуманным, такого рода проблемы с плохими вводными очень распространены на практике, особенно при работе с большими наборами данных.
Для решения проблемы выбросов были предложены небольшие модификации корреляции Пирсона. Например, Ро (греческая буква rho (ρ) или rs) Спирмена — это, по сути, просто корреляция Пирсона, в которой вы сначала заменяете каждую точку данных ее рангом в соответствующей последовательности. Так, например, если самый тяжелый человек в предыдущем примере весил 2 миллиона килограмм, это сверхвысокое значение будет заменено на 1000 (поскольку в этом наборе данных было 1000 человек, а тот тяжеловес был бы самым тяжелым в этом наборе).Это дает показатель, который в целом работает аналогично методу Пирсона, но устойчив к выбросам.
Есть еще одно усовершенствование подхода Спирмена, называемое Тау Кендалла. Он также заменяет точки данных их рангами, но вместо того, чтобы рассматривать их все вместе, как это делает Ро Спирмена, он оперирует отдельными пары точек данных. Например, вы можете взять третью точку данных из каждой последовательности и сравнить их друг с другом, спросив, находятся ли их ранги в соответствующих последовательностях в гармонии (оба ранга выше или ниже, чем у другой пары) или в конфликте (на один ранг выше в одной паре последовательности, но ниже в другой — они называются «согласованными» и «несогласными» парами). Вы повторяете этот процесс для всех точек данных, и по сути это похоже на подсчет согласия и разногласий среди всех возможных пар. Здесь есть один тонкий момент: как обрабатывать случай связей, когда K-я запись каждой последовательности имеет одинаковый ранг в соответствующей последовательности. Тау Кендалла учитывает количество связей, чтобы мы могли эффективно «изменить масштаб» или нормализовать полученную меру связи. Интуитивно понятно, что если бы у нас было два вектора X и Y, каждый из которых содержал один миллион числовых наблюдений, и все из них, кроме 5, были бы одинаковыми поэлементно между X и Y, это совсем другая ситуация, когда X и Y имеют длину только 10 с 5 разных записей.
Таким образом, Тау Кендалла эффективно работает с выбросами и, в отличие от корреляции Пирсона, не предполагает существования линейной зависимости между последовательностями. Однако у него по-прежнему возникают серьезные проблемы, когда дело доходит до надежного обнаружения существования определенных видов связей, которые могут существовать между двумя последовательностями, особенно при выявлении сложных нелинейных связей. Одним из недостатков Тау Кендалла и многих других ранговых методов является то, что они не работают, когда вы имеете дело с более сложными моделями ассоциаций, такими как отношения, которые являются циклическими или включают в себя несколько переменных, взаимодействующих немонотонным образом. Это потому, что Тау Кендалла фокусируется на согласовании и несогласии между парами, что хорошо работает только для монотонных отношений, когда переменные движутся в одном последовательном направлении относительно друг друга.
Вопрос на самом деле более сложен, чем просто монотонна эта связь или нет. Лучший способ оценить проблему во всей ее общности — это подумать о каких-нибудь странно выглядящих диаграммах рассеяния, которые мгновенно наводят на мысль человека, смотрящего на них визуально, и можно было бы сказать что-то очевидное и ясное о взаимосвязи между двумя последовательностями, но где меры, которые мы обсуждали до сих пор, мало что нам говорят. Например, предположим, что диаграмма рассеяния выглядит как кольцо или форма «Х». Обе эти формы могут казаться имеющими близкую к нулю связь, если измерять их только с помощью тау Кендалла или корреляции Пирсона, но если бы вы спросили человека, выполняющего визуальный анализ, куда, по его мнению, должна была бы попасть точка на вертикальной оси, учитывая горизонтальное положение точки (или наоборот), он мог бы иметь очень хорошее представление (хотя это могло бы быть выражено как-то вроде «либо верхняя часть кольцевой структуры здесь, либо нижняя часть кольцевой структуры здесь — но скорее одно из двух»). Такого рода взаимосвязь очень далека от случайной, и все же она в значительной степени «невидима» для этих более простых мер ассоциации, поскольку нарушает некоторые базовые предположения (т. е., что взаимосвязь может быть описана с помощью функции одной переменной, которая передает тест «вертикальная линия», который вы, возможно, помните из курса математического анализа).
Если вы подходите к этой теме с точки зрения LLM и встроенного векторного сходства, используемого для количественной оценки «семантического сходства» между строками языкового текста, вы можете спросить: «А как насчет косинусного сходства? Разве это не золотой стандарт, используемый почти всеми векторными базами данных и конвейерами RAG?». Хороший вопрос! Косинусное подобие действительно очень полезно и, что немаловажно, быстро и эффективно для вычислений на миллионах или даже миллиардах векторов. На интуитивном уровне косинусное подобие работает, рассматривая каждую последовательность как точку в N-мерном пространстве. Итак, если каждый из ваших векторов эмбеддингов имеет длину 2048 чисел и у вас есть 2 таких вектора, вы можете думать о них как о двух отдельных точках в 2048-мерном пространстве. Затем вы сравниваете угол, который каждая из этих точек образует относительно начала координат в этих различных измерениях. Если точки охватывают векторы, которые образуют одинаковые углы с началом координат, то они в некотором смысле «указывают в одном общем направлении» в этом многомерном пространстве и, таким образом, «похожи» друг на друга. Проблема с таким подходом к концептуализации заключается в том, что наша интуиция о пространстве перестает действовать, как только мы достигаем трехмерности, а к тому времени, когда вы достигаете 2048 измерений, все становится очень странным и неинтуитивным. Например, при обобщении сферы или куба в таком многомерном пространстве почти весь ее объем будет находиться вблизи ее поверхности, тогда как для трехмерной сферы или куба верно обратное.
Тем не менее, косинусное сходство чрезвычайно удобно для поиска приблизительного местоположения иглы в стоге сена. Если у вас есть векторы эмбеддингов для миллионов предложений из тысяч книг в базе данных векторов, и вы хотите найти предложения, похожие на предложение «Величайшим математиком античности обычно считается Архимед», то это очень эффективно для быстрого исключения 99,999% этих миллионов предложений, которые не имеют ничего общего с этой очень конкретной мыслью, поскольку большинство из этих предложений будут соответствовать векторам, указывающим на совершенно другие места в пространстве вложений. Но что делать после того, как вы отфильтровали почти все сохраненные векторы и у вас осталось 20 «самых похожих» предложений, и теперь вы хотите упорядочить их так, чтобы самое релевантное было показано первым? Я бы предположил, что здесь косинусное сходство может быть несколько тупым инструментом, которое может быть искажено различными способами. Но более подходящим примером может быть случай, когда в вашей базе данных векторов просто нет очевидно релевантного предложения, так что ни одно из 20 «самых похожих» предложений, найденных через косинусное сходство, не выглядит особенно релевантным. В этом случае мы могли бы захотеть иметь другую меру связи или зависимости, которую мы могли бы применить к верхним 1% или 0,1% релевантных векторов, найденных через косинусное сходство, чтобы получить ранжирование этих векторов.
Итак, теперь вы можете видеть, почему мы могли бы захотеть найти более мощную, общую меру связи или зависимости, которая не делает предположений о природе возможной связи между нашими двумя последовательностями данных, которая не требует, чтобы отношение было функцией один к одному или монотонным, которая может легко терпеть ошибочную выбросную точку данных, не разрушаясь полностью. Мое утверждение заключается в том, что D Хефдинга — это лучшая на сегодняшний день обнаруженная мера для этих целей. Впервые она была представлена польским математиком Василием Хёфдингом в его статье 1948 года под названием «Непараметрический тест независимости» (A nonparametric test for independence). В этой 12-страничной статье Хефдинг определяет то, что он называет D (за зависимость). Если у вас есть математическая подготовка, вы возможно захотели прочитать его оригинальную работу, но я подозреваю, что большинство людей нашли бы ее довольно трудной для понимания и неинтуитивной. И тем не менее это не такая уж фундаментально сложная концепция, которую вы не могли бы понять, если бы она была представлена самым простым и интуитивно понятным способом, что я сейчас и попытаюсь сделать.
Как и в случае с тау Кендалла, расчет D Хефдинга начинается аналогичным образом: сначала вы заменяете каждое значение в ваших двух последовательностях на ранг этого значения в соответствующей последовательности; если несколько значений точно равны и, таким образом, у вас есть «связи», то вы берете среднее значение рангов для равных значений. Таким образом, если значение 4.2 должно было бы дать конкретной точке данных ранг 252 из 1000 точек данных в одной из ваших последовательностей, но на самом деле в последовательности есть 4 такие точки с точным значением 4.2, тогда каждая из этих точек получит средний ранг (252 + 253 + 254 + 255)/4 = 253.5. Затем вы также смотрите на пары точек из каждой последовательности и смотрите, сколько из них «согласованы» или «несогласованы», опять же, аналогично тому, как работает тау Кендалла. Но затем процесс расходится: после ранжирования данных и рассмотрения согласованности и несогласованности среди пар, D Хефдинга вводит уникальный подход для количественной оценки зависимости между двумя последовательностями. Он рассчитывает статистику на основе разницы между наблюдаемым «совместным распределением» рангов и тем, что ожидалось бы, если бы две последовательности были независимы.
Давайте сначала сделаем шаг назад и объясним, что мы подразумеваем под «совместным распределением» по сравнению с индивидуальным или «маргинальным» распределением в каждой из наших двух последовательностей. В контексте D Хефдинга, когда мы говорим о «совместном распределении рангов», мы имеем в виду, как ранги двух последовательностей сочетаются или относятся друг к другу по всем парам точек данных. Представьте, что вы строите график, где ось x представляет ранги из одной последовательности, а ось y — ранги из другой. Каждая точка на этом графике затем представляет пару рангов — один из каждой последовательности. Паттерн, который формируют эти точки на графике, отражает их совместное распределение: он показывает нам, как ранги в одной последовательности связаны с рангами в другой последовательности.
С другой стороны, «маргинальное распределение» — относится к рангам внутри одной последовательности, рассматриваемой изолированно. Если бы мы смотрели только на одну ось упомянутого выше графика (либо x, либо y) и игнорировали другую, распределение точек вдоль этой оси представляло бы маргинальное распределение для этой последовательности. Оно говорит нам о разбросе или распределении рангов внутри этой последовательности в отдельности, без учета того, как эти ранги могут быть сопоставлены с рангами из другой последовательности.
Понимание различия между совместным и маргинальным распределениями критически важно для осознания принципа работы D Хефдинга. Эта мера по сути оценивает, отклоняется ли наблюдаемое совместное распределение рангов от того, что можно было бы ожидать, если бы последовательности были независимы. При независимости совместное распределение было бы простым произведением маргинальных распределений — то есть, способ, которым ранги сопоставлены между последовательностями, был бы случайным, без узнаваемого паттерна. Однако, если между последовательностями существует зависимость, наблюдаемое совместное распределение будет отличаться, указывая на то, что ранги в одной последовательности систематически связаны с рангами в другой. D Хефдинга количественно оценивает это различие, предоставляя статистическую меру зависимости между последовательностями.
Для этого D Хефдинга рассматривает все возможные "четверки" пар рангов. То есть, для любых четырех различных точек данных он исследует, согласуется ли ранжирование одной пары с ранжированием другой пары внутри последовательностей. Это включает сравнение каждой пары точек данных со всеми другими парами, процесс, который более всесторонний, чем попарные сравнения в тау Кендалла, которые смотрят только на согласованные и несогласованные пары. Сущность D Хефдинга заключается в его оценке совместного ранжирования точек данных. Он рассчитывает сумму определенных членов, полученных из этих сравнений, отражающих степень согласованности и несогласованности по всем парам и четверкам. Эти термины учитывают количество раз, когда точка данных в одной последовательности ранжируется как выше, так и ниже другой точки при сравнении по обеим последовательностям, с поправкой на связи.
Окончательный расчет D Хефдинга включает формулу, которая нормализует эту сумму, учитывая общее количество точек данных и ожидаемые значения при предположении независимости. Результатом является мера, которая варьируется от -0,5 до 1, где чем выше число, тем сильнее две последовательности зависят друг от друга. Как вы, вероятно, можете представить, вычисление D Хефдинга для двух последовательностей определенной длины (скажем, 5000 чисел в каждой из двух последовательностей) влечет за собой огромное количество индивидуальных сравнений и расчетов — гораздо больше, чем используется для достижения Тау Кендалла, не говоря уже о Ро Спирмена или корреляции Пирсона, поскольку мы учитываем всю последовательность, а не только отдельные пары, и потом также углубляемся на уровни отдельных пар.
Для двух последовательностей, каждая из которых содержит 5000 чисел, D Хефдинга не просто сравнивает каждую точку с каждой другой точкой один раз (что уже было бы значительно); он исследует отношения среди всех возможных четверок точек из объединенного набора данных. Чтобы поставить это в перспективу, если бы вы сравнили каждую пару точек в одной последовательности из 5000 чисел, вы бы сделали около 12.5 миллиона сравнений (поскольку из 5000 выбрать 2 примерно равно 12.5 миллиона). Но D Хефдинга требует сравнения четверок. Количество уникальных четверок в последовательности из 5000 задается комбинаторной формулой "из n выбрать 4", которая для 5000 составляет около 6.2 миллиарда четверок. И для каждой из этих четверок D Хефдинга включает в себя множество сравнений и расчетов для оценки их согласованности и несогласованности в контексте всего набора данных.
Это экспоненциальное увеличение числа сравнений подчеркивает, почему D Хефдинга значительно более требователен к вычислительным ресурсам. Речь идет не только о масштабе; это глубина и широта анализа, который выполняет D Хефдинга, чтобы зафиксировать сложные зависимости между двумя последовательностями. Этот всесторонний подход позволяет D Хефдинга обнаруживать тонкие и сложные ассоциации, которые более простые меры могут упустить, но это также означает, что его вычисление может быть ресурсоемким, особенно для больших наборов данных. Но я бы утверждал, что в эпоху дешевых и быстрых вычислений настало время начать использовать многочисленные преимущества D Хефдинга. В дополнение к возможности нахождения любого вида отношения между двумя последовательностями без каких-либо предположений о их распределениях и устойчивости к выбросам, D Хефдинга также имеет несколько других преимуществ: он симметричен, так что hoeffd(X, Y) то же самое, что и hoeffd(Y, X), он всегда ограничен (результат никогда не будет меньше -0.5 или больше 1.0), и когда одна из последовательностей является константой, D Хефдинга стремится к нулю. Это не относится к некоторым другим мощным мерам связи, таким как взаимная информация (о которой мы здесь не говорили).
Теперь, когда мы дали базовый обзор, давайте перейдем к подробностям того, как это все делается на самом деле. Сначала я дам вам объяснение словами с одной формулой (это единственное место, где попытка избежать использования формулы, вероятно, сделала бы вещи еще более запутанными и сложными, чем они уже есть!). Не волнуйтесь, если это кажется супер запутанным и мало что имеет смысл. Полезно видеть, как обычно представляются идеи (поверьте мне, оригинальная статья 1948 года еще более сложна для понимания!). Затем мы разберем это по частям и попытаемся дать интуицию для каждой части. Наконец, мы рассмотрим фактическую (но медленную) реализацию D Хефдинга на Python, которая подробно прокомментирована.
Разобьем по шагам:
Ранжирование и парные сравнения :
Первоначально каждая точка данных в обеих последовательностях заменяется ее рангом в соответствующей последовательности, учитывая связи путем присвоения среднего ранга связанным значениям.
Сравнение включает в себя просмотр всех возможных пар внутри этих ранжированных последовательностей, чтобы определить, являются ли они согласованными (оба ранга увеличиваются или уменьшаются вместе) или несогласованными (один ранг увеличивается, а другой уменьшается).
Сравнение четверок:
Помимо парных сравнений, D Хефдинга оценивает все возможные четверки точек данных. Для каждой четверки эта мера оценивает, соответствует ли порядок внутри одной пары рангов порядку внутри другой пары. Этот шаг имеет решающее значение для выявления более сложных зависимостей, выходящих за рамки простых парных ассоциаций. Мы сохраняем эти ранги в массиве, который мы обозначаем как Q, который содержит значение для каждой точки данных, отражающее ее отношение к другим точкам с точки зрения соответствия и несоответствия рангов. Для каждой точки данных Q накапливает подсчеты того, сколько пар (четверок, если рассматривать их с другой точкой данных) демонстрируют последовательное (согласованное) или противоречивое (несогласованное) поведение при ранжировании. Этот шаг важен для выявления сложных зависимостей, которые могут быть упущены при парном сравнении.
Суммирование:
Суть расчета D Хефдинга включает в себя суммирование определенных членов, полученных на основе оценок согласия и несогласия по всем четверкам. Эта сумма отражает степень отклонения наблюдаемого совместного распределения рангов от ожидаемого, если бы последовательности были независимыми.
Нормализация:
Окончательный расчет включает нормализацию суммы, полученной на предыдущем шаге. Эта нормализация учитывает общее количество точек данных (N) и корректирует ожидаемые значения в предположении независимости. Целью этой нормализации является масштабирование статистики Хеффдинга D, что делает ее сопоставимой для разных размеров выборки и распределений.
Формула нормализации:
Где D_1, D_2 и D_3 представляют собой промежуточные суммы, включающие комбинации рангов и их оценок согласия/несогласия. Конкретно:
D_1 относится к сумме произведений разностей рангов для всех четверок, отражающих общее согласие/несогласие.
D_2 корректирка с учётом индивидуальной изменчивости внутри каждой последовательности.
D_3 учитывает взаимодействие между последовательностями.
Поскольку всё это всё ещё выглядит довольно сложным, давайте разберемся, что мы подразумеваем под четверками, Q и элементами D_1, D_2 и D_3.
Что такое Q и зачем оно?
Q представляет собой взвешенное количество для каждой точки данных с учетом того, сколько других точек имеют ранги ниже ее собственного по обоим измерениям (например, росту и весу) и с поправкой на связи.
Это крайне важно для определения степени совпадения и несоответствия между точками данных, выходя за рамки простых парных сравнений.
Вычисление Q включает корректировки на связи, гарантируя, что связанные ранги вносят соответствующий вклад в общий показатель.
Учитывая все остальные точки относительно заданной точки и включая поправки на связи, значения Q обеспечивают детальное представление о положении каждой точки в совместном распределении рангов, что является основой для оценки зависимости между двумя последовательностями.
Пояснения D_1, D_2, D_3:
Эти промежуточные суммы играют различную роль в вычислении D Хёфдинга:
D_1 отражает совокупное совпадение/расхождение между всеми четверками точек данных, скорректированное на ожидаемую сумму при независимости. Это мера того, насколько фактические данные отклоняются от того, что можно было бы ожидать, если бы между последовательностями не было никакой связи.
Интуиция для D_1: Думайте о D_1 как о количественном измерении степени скоординированных изменений между двумя последовательностями, выходящими за пределы того, что может вызвать случайная случайность. Он эффективно фиксирует степень взаимного влияния в ранжировании, оценивая, имеют ли парные наблюдения тенденцию двигаться вместе по последовательной схеме чаще, чем можно было бы ожидать по совпадению.
Очень простая интуиция для D_1: Представьте, что вы сравниваете синхронность танцевальных движений двух танцоров в разных выступлениях. D_1 представляет степень, в которой их движения синхронизированы (или не синхронизированы) больше, чем можно было бы ожидать по чистой случайности, если бы они танцевали независимо. Он отражает суть их партнерства путем количественной оценки их скоординированных (или нескоординированных) усилий.
D_2 представляет собой произведение дисперсий рангов внутри каждой последовательности, предлагая базовую меру изменчивости, независимую от каких-либо отношений между последовательностями. Это помогает изолировать эффект внутренней изменчивости последовательностей от их взаимной зависимости.
Интуиция для D_2: D_2 самостоятельно оценивает присущую изменчивость или дисперсию внутри каждой последовательности. Это похоже на оценку разброса точек данных в каждой последовательности, чтобы понять, насколько каждая последовательность варьируется независимо. Это помогает различать зависимости, возникающие из-за внутренней изменчивости самих последовательностей, и зависимости, возникающие в результате их взаимодействия.
Очень простая интуиция для D_2: Рассмотрим D_2 как оценку диапазона танцевальных стилей, которые каждый танцор демонстрирует в своих выступлениях независимо от своего партнера. Он измеряет, насколько разнообразны и последовательны выступления каждого танцора. Понимая эту индивидуальную изменчивость, мы можем лучше понять, насколько их синхронизация (фиксируемая D_1) обусловлена их взаимодействием, а не их индивидуальными тенденциями.
D_3 служит частью взаимодействия, сочетая идеи D_1 с внутренней изменчивостью последовательностей, зафиксированных D_2. Он осуществляет точную настройку меры, учитывая, как отдельные совпадения рангов влияют на общую зависимость, принимая во внимание внутреннюю ранговую структуру каждой последовательности.
Интуиция для D_3: D_3 корректирует меру, учитывая, как индивидуальная изменчивость внутри каждой последовательности (фиксируемая D_2) влияет на наблюдаемое соответствие/несогласие (D_1). Речь идет о понимании того, как внутренняя структура каждой последовательности влияет на их совместное поведение, уточнении оценки их взаимоотношений путем учета роли индивидуальной изменчивости в их наблюдаемых зависимостях.
Очень простая интуиция для D_3: D_3 похож на исследование того, как индивидуальный стиль и последовательность каждого танцора (D_2) влияют на их совместное выступление (D_1). Если у танцора широкий диапазон стилей, как эта универсальность влияет на его синхронизацию с партнером? D_3 оценивает влияние изменчивости каждого танцора на их скоординированные усилия, предоставляя детальное представление об их партнерстве.
Окончательный расчет D Хёфдинга :
Окончательная формула для D Хёфдинга объединяет D_1, D_2 и D_3 вместе с коэффициентами нормализации для получения статистики в диапазоне от -0,5 до 1. Этот диапазон позволяет интерпретировать степень связи между последовательностями, при этом значения близкие к 0 указывают на отсутствие связи, значения ближе к 1 указывают на сильную положительную связь, а значения около -0,5 указывают на сильную отрицательную связь.
Интуиция для окончательного расчета: Окончательное значение D Хёфдинга представляет собой комплексную меру, которая объединяет наблюдаемое соответствие/расхождение, присущую каждой последовательности изменчивость и взаимодействие между этими факторами. Нормализация гарантирует, что показатель масштабируется соответствуя размеру выборки, что делает его надежным индикатором силы и направления связи между последовательностями. Он объединяет сложные взаимозависимости и индивидуальные различия в единую метрику, которая отражает общую взаимосвязь, принимая во внимание не только наличие взаимосвязи, но также ее характер и силу по сравнению с тем, что можно было бы ожидать в условиях независимости.
Очень простая интуиция для окончательного расчета: Итоговая оценка D Хёфдинга аналогична итоговой оценке танцевального соревнования, которая оценивает общую гармонию между двумя танцорами. Оценка около 1 будет означать, что танцоры идеально синхронизированы и двигаются как одно целое. Оценка, близкая к 0, не будет означать никакой особой связи, как будто они танцуют под разные мелодии. А оценка около -0,5 предполагает, что они движутся в противоположных направлениях, возможно, скорее сталкиваясь, чем дополняя друг друга. Эта финальная партитура объединяет все аспекты их выступлений — индивидуальные стили, последовательность и взаимное взаимодействие — в единую интерпретируемую меру их танцевального партнерства.
Хотя теперь вы, вероятно, имеете гораздо лучшее представление о том, как вычисляется D Хёфдинга, всё, вероятно, по-прежнему кажется абстрактным, и неясно, как бы вы на самом деле реализовали всё это на реальном языке программирования. Это мы и собираемся сделать сейчас с Python. Мы собираемся использовать библиотеки Numpy и Scipy: Numpy для эффективной работы с массивами (включая удобную индексацию) и Scipy для его функции «rankdata», которая эффективно вычисляет ранги, обрабатывая связи таким образом, который нам нужен, используя усреднение.
Чтобы сделать вещи более конкретными, мы собираемся использовать всего 10 фактических точек данных: это будут пары данных в форме (высота_в_дюймах, вес_в_фунтах):
X = np.array([55, 62, 68, 70, 72, 65, 67, 78, 78, 78]) # Высота в дюймах
Y = np.array([125, 145, 160, 156, 190, 150, 165, 250, 250, 250]) # Вес в фунтахРезультат запуска нашей программы на этом входе следующий:
Ranks of Heights (X): [1. 2. 5. 6. 7. 3. 4. 9. 9. 9.]
Ranks of Weights (Y): [1. 2. 5. 4. 7. 3. 6. 9. 9. 9.]
Q values: [1. 2. 4. 4. 7. 3. 4. 8.5 8.5 8.5]
Hoeffding's D for data: 0.4107142857142857Хотите верьте, хотите нет, но на самом деле мы можем реализовать весь D Хёфдинга всего за ~15 строк Python! Однако мы собираемся добавить множество комментариев, а также отобразить некоторые промежуточные значения, поскольку мы стремимся сделать это как можно более наглядным. В итоге у нас получится около 75 строк, включая пробелы, что всё равно не так уж и много, учитывая объем работы кода!
Если вы хотите запустить код, вы можете посмотреть этот блокнот Google Colab здесь.
Вот полный код:
import numpy as np
import scipy.stats
from scipy.stats import rankdata
def hoeffd_example():
# Новый датасет из 10 точек пар (height_in_inches, weight_in_pounds), с последними тремя в качестве связей:
X = np.array([55, 62, 68, 70, 72, 65, 67, 78, 78, 78]) # Рост в дюймах
Y = np.array([125, 145, 160, 156, 190, 150, 165, 250, 250, 250]) # Вес в фунтах
# Метод ранжирования «среднее» присваивает среднее значение рангов, которые были бы присвоены всем связанным значениям.
R = rankdata(X, method='average') # Ранги роста
S = rankdata(Y, method='average') # Ранги веса
# Выведем ряды для визуализации. Связи очевидны в последних трёх записях обоих рейтингов.
print(f"Ranks of Heights (X): {R}")
print(f"Ranks of Weights (Y): {S}")
N = len(X) # Общее количество точек
# Q — это массив, в котором будет храниться специальная сумма для каждой точки данных, что имеет решающее значение для вычисления D Хёфдинга.
Q = np.zeros(N)
# Цикл по каждой точке для расчета значения Q.
for i in range(N):
# Для каждой 'i' точки,подсчитайте, сколько точек имеют одновременно меньший ранг роста и веса (согласованные пары).
Q[i] = 1 + sum(np.logical_and(R < R[i], S < S[i]))
# Скорректируйте Q[i] для связей: когда оба ранга равны, это частично (1/4) вносит вклад в значение Q[i].
# "-1" означает, что сама точка не включается в собственное сравнение.
Q[i] += (1/4) * (sum(np.logical_and(R == R[i], S == S[i])) - 1)
# Когда есть связь только в ранге роста, но ранг веса ниже, он составляет половину (1/2) от значения Q[i].
Q[i] += (1/2) * sum(np.logical_and(R == R[i], S < S[i]))
# Аналогично, когда связан только ранг веса, но ранг роста ниже, это также дает половину (1/2).
Q[i] += (1/2) * sum(np.logical_and(R < R[i], S == S[i]))
# Выведем значения Q для каждой точки данных, указывая взвешенное количество точек, считающихся «нижними» или «равными».
print(f"Q values: {Q}")
# Посчитаем промежуточные суммы нужные для формулы D Хёфдинга:
# D1: Эта сумма использует значения Q, рассчитанные ранее. Каждое значение Q инкапсулирует информацию о том, как
# ранги точки данных связаны с другими в обеих последовательностях, включая согласованность и поправки на связи.
# Член (Q - 1) * (Q - 2) для каждой точки данных количественно определяет степень, в которой ранги этой точки
# согласуются с другими, с поправкой на ожидаемое соответствие при независимости.
# Суммирование этих терминов по всем точкам данных (D1) объединяет эту информацию о соответствии для всего набора данных.
D1 = sum((Q - 1) * (Q - 2))
# D2: Эта сумма включает в себя произведения ранговых различий для каждой последовательности, скорректированные на связи. Член
# (R - 1) * (R - 2) * (S - 1) * (S - 2) для каждой точки данных фиксирует взаимодействие между дисперсиями рангов
# внутри каждой последовательности, обеспечивая измерение того, насколько совместное распределение рангов отличается от того, что было бы
# можно ожидать в условиях независимости из-за изменчивости только рангов, без учета их попарности.
# Суммирование этих продуктов по всем точкам данных (D2) дает глобальную оценку этого расхождения.
D2 = sum((R - 1) * (R - 2) * (S - 1) * (S - 2))
# D3: Эта сумма представляет собой член взаимодействия, который объединяет результаты значений Q с различиями в рангах.
# Член (R - 2) * (S - 2) * (Q - 1) для каждой точки данных учитывает дисперсию ранга наряду со значением Q,
# определение того, как совпадение/расхождение рангов отдельных точек данных влияет на общую меру зависимости,
# с поправкой на ожидаемые значения в условиях независимости. Суммирование этих условий (D3) объединяет эти отдельные
# вкладов в комплексный член взаимодействия для набора данных.
D3 = sum((R - 2) * (S - 2) * (Q - 1))
# Окончательное вычисление D Хёфдинга объединяет D1, D2 и D3, а также коэффициенты нормализации.
# которые учитывают размер выборки (N). Нормализация гарантирует, что D Хёфдинга масштабируется соответствующим образом:
# позволяющее проводить значимое сравнение наборов данных разного размера. В формулу включены эти суммы
# и коэффициенты нормализации таким образом, чтобы сбалансировать вклады согласия, несогласия и ранговых отклонений,
# в результате чего получается статистика, которая надежно измеряет степень связи между двумя последовательностями.
D = 30 * ((N - 2) * (N - 3) * D1 + D2 - 2 * (N - 2) * D3) / (N * (N - 1) * (N - 2) * (N - 3) * (N - 4))
# Возвращаем посчитанное D Хёфдинга.
return D
hoeffd_d = hoeffd_example()
print(f"Hoeffding's D for data: {hoeffd_d}")Я упомянул, что эта реализация, хотя и правильная, но довольно медленная и неэффективная. Это может показаться удивительным, учитывая, что мы делаем «тяжелую работу», используя Numpy и Scipy, которые на самом деле реализованы на очень эффективном C++. Оказывается, что, учитывая огромное количество задействованных операций и сравнений, накладные расходы на функции настолько велики, что код действительно начинает тормозить даже на быстром железе, как только вы превысите 1000 точек данных, а для обработки 5000 точек данных потребуется чрезвычайно много времени.
К счастью, я написал на Rust гораздо более эффективную версию, которую легко использовать в качестве библиотеки Python. Вы можете использовать это, просто выполнив:
pip install fast_vector_similarity
Код можете найти здесь.
Обсуждение библиотеки на hacker news
Интересные критика и комментарии:
CrazyStat:
> Окончательная формула для D Хёфдинга объединяет D_1, D_2 и D_3 вместе с коэффициентами нормализации для получения статистики в диапазоне от -0,5 до 1. Этот диапазон позволяет интерпретировать степень связи между последовательностями, при этом значения близкие к 0 указывают на отсутствие связи, значения ближе к 1 указывают на сильную положительную связь, а значения около -0,5 указывают на сильную отрицательную связь.Это неверно.
D Хёфдинга не предназначался для использования в качестве описательной статистики для измерения силы или направления отношений, это просто статистика непараметрического теста на независимость. Оно взято из статьи Хеффдинга 1948 года «Непараметрический критерий независимости» [1]. Интерпретация этого показателя как меры прочности отношений сомнительна. Шкала... по большей части бессмысленна, за исключением того, что в качественном смысле значение, близкое к 0, близко к независимости (возможно, подробнее об этом позже), а близкое к 1 — это своего рода сильная связь. Но что означает D 0,2, 0,6 или 0,9? Кто знает! Это определенно не ваша традиционная шкала корреляции — не поддавайтесь искушению интерпретировать ее таким образом.
Интерпретировать его как меру направления отношений просто неправильно. Вы можете легко проверить, что D для двух векторов X и Y совпадает с D для X и (-Y). Это не дает вам никакой информации о направлении отношений. Иногда отрицательное значение D является просто артефактом того, как оно рассчитывается и масштабируется.
Возвращаясь к теме «возможно, близкой к независимости»: D Хефдинга слеп к определенным отклонениям от независимости. Вы можете иметь совместное распределение с четкой зависимостью, но D Хёфдинга будет равно 0. Некоторые примеры см. в разделе 4 из [2].
Если вы хотите использовать эзотерическую меру силы связи между двумя переменными, я бы вместо этого использовал корреляцию расстояний. По крайней мере, это имеет ясный смысл.
[1] https://projecteuclid.org/journals/annals-of-mathematical-st...
[2] https://arxiv.org/pdf/2010.09712.pdf
Ответ автора:
... Что касается полезности этой меры, я обнаружил, что она чрезвычайно удобна для выявления взаимосвязей, которые упускаются из виду при использовании обычных измерений корреляции.david_draco:
Другой подход заключается в создании синтетического совместного распределения путем независимого объединения маргинальных распределений и обучения random forest, чтобы отличать синтетическое объединение (synthetic joint) от реального соединения. Если классификатор не может этого сделать, распределения некоррелированы. https://arxiv.org/abs/1611.07526
