В сложных сетях с помощью различных процессов фильтрации могут быть выделены важные сетевые структуры, несущие содержательную информацию о сети. Среди сетевых структур традиционно рассматриваются: максимальное остовное дерево, максимально отфильтрованный планарный граф, отсеченный граф, максимальные клики и максимальные независимые множества отсеченного графа и другие.
В условиях статистической природы исходных данных возникает задача идентификации сетевых структур. Лекция, которую мы выбрали для вас сегодня, посвящена недавнему развитию этой темы в рамках теории одновременной проверки многих статистических гипотез (multiple decision statistical procedures, multiple test procedures). Такой подход позволяет разработать методы оценки статистической неопределенности сетевых структур и выделить оптимальные и устойчивые статистические процедуры идентификации. Оказывается, что сетевые структуры, построенные по вероятностям совпадения знаков, оказываются предпочтительными перед структурами, построенными по классическим корреляциям Пирсона. В рассказе рассмотрены приложения результатов к анализу фондовых рынков.
Доклад был прочитан на факультете компьютерных наук, открытом при поддержке Яндекса в Вышке. Лектор Валерий Калягин — доктор физико-математических наук, ординарный профессор НИУ ВШЭ. Заведует кафедрой прикладной математики и информатики и лабораторией алгоритмов и технологий анализа сетевых структур НИУ ВШЭ в Нижнем Новгороде.
Под катом — полная расшифровка лекции.
Задача идентификации сетевых структур для нас была совершенно новой – мы начали ею заниматься в 2012 году, когда была создана лаборатория. Одна из задач в этой лаборатории была связана именно с некоторыми сетевыми структурами. Мы заинтересовались ею иначе, чем она была поставлена. То, что я буду рассказывать, в большей степени математическая часть, чем прикладная.
Задача на первый взгляд очень несложная, понять ее смогут все. Есть полный взвешенный граф, назовем его сетью, в котором N узлов. Что эту задачу выделяет – так это то, что с каждым узлом мы связываем некую случайную величину. Тем самым у нас есть некоторый случайный вектор (многомерный, N-мерный случайный вектор). Затем, есть какие-то связи между этими случайными величинами. Они измеряются некоторой функцией (у нее очень много названий: similarity, association, dependence…), которая является характеристикой связи двух случайных величин. Вот такой, пока еще абстрактный поток. Сетевая структура для нас – это некоторый граф, который мы можем из этой сети извлечь, подграф этой сети. Не любой, а интересный, с какими-то хорошими, полезными может быть, свойствами.
Задача идентификации формулируется следующим образом: у нас имеется выборка длины n из этого случайного многомерного распределения, этого вектора, n наблюдений. И нам нужно отождествить по наблюдениям ту структуру, которая в сети каким-то образом по связям между случайными величинами была определена. То есть существует какая-то скрытая от нас структура, есть наблюдения, и мы должны по наблюдениям эту структуру восстановить. Типичная задача статистики. Единственное, что, может быть, объект немного непривычный: объектом, который нужно восстановить, является граф. Эта задача, естественно, в такой общей постановке (тем более что мы не знаем, что такое структура) никогда не решается.
Есть несколько примеров, так называемые гауссовские графические, или графовые модели. Это многомерные нормальные распределения, связь между узлами задается так называемыми частными корреляциями между двумя случайными величинами. Частные корреляции так называемую чистую связь, из которой исключено влияние всех остальных. На математическом языке эти случайные корреляции напрямую связаны с элементами обратной матрицы
?-1. В качестве сетевой структуры – граф концентрации. Граф концентрации строится очень просто: если между ними связь нулевая, то мы ребро не проводим, если ненулевая – проводим. На самом деле это для обратной матрицы ковариаций ноль или не ноль (для соответствующих ковариаций). Сама по себе теория гауссовских графовых (графических) моделей – довольно продвинутая вещь, есть много книг на эту тему. Там возникают очень интересные условные распределения.
Немного повозившись, можно увидеть, что если какие-то связи отсутствуют, то они могут отсутствовать еще где-то (пока так, очень неточно). И, соответственно, здесь исследуется, как устроены распределения, когда задан граф концентрации.
Более интересна здесь для нас задача идентификации – именно об этом я и хочу поговорить. Вы располагаете наблюдениями над этими случайными векторами и должны на базе этих наблюдений идентифицировать граф концентраций. И вот здесь появляется то новое, что, собственно, повлияло на всю остальную деятельность, – теперь вы должны проверять не одну гипотезу. Сейчас я попытаюсь это объяснить: мы можем выделить какое-то ребро и проверять гипотезу,, равны частные корреляции здесь нулю или нет. Такой подход будет неправильным; формально мы его применить можем, но какое качество будет у такой статистической процедуры идентификации графа концентраций, сказать трудно, и вот почему: изначально между этими случайными величинами есть связи, и в проверках каждой индивидуальной гипотезы эти связи могут сыграть роль. Если мы примитивно попытаемся проверять эти индивидуальные гипотезы, не учитывая существующие зависимости между случайными величинами, получатся не самые хорошие статистические процедуры. В последнее время для идентификации этого графа концентраций строится много процедур, все более точных, все более адекватных. Новое здесь то, что вы должны проверять сразу много гипотез – вот так правильно ставится задача. Проверять не по отдельности каждую, а сразу много. Позже покажу, в той постановке, как мы ее видим; просто априори графом концентраций может быть любой граф – и это одна гипотеза, и этих гипотез столько, сколько всего графов со всеми вершинами. И нам нужно из них из всех выбрать одну – наиболее адекватную наблюдениям, которые у нас есть.
Другая модель – это так называемая сетевая модель рынка: активы на рынке соответствуют вершинам сети, связь между активами задается некоторым взвешенным ребром, и вес ребра отражает общность (similarity) в поведении активов. Эта сеть получается полным взвешенным графом, случайные величины здесь – некоторые характеристики этих активов. Я написал цены, но цены в нашу модель не вкладываются, потому что ценообразование моделируется скорее мартингалом. Это более сложная конструкция, она уж точно никак не является таким случайным процессом – понятно, что цена в каждый новый момент времени зависит от предыдущего. Если сделать некоторые предположения, то будет некоторый случайный процесс со свойством мартингала, но вот доходности, объемы продаж вполне в эту модель укладываются. Доходности обладают нужными нам свойствами, можно считать их независимыми и одинаково распределенными, потому что у нас там выборка, которую мы делаем. Это стандартная выборка: независимые, одинаково распределенные случайные величины. В литературе используются различные меры связи между случайными величинами, в нашем случае – между активами: корреляции Пирсона, частные корреляции, корреляции знаков, ? (тау) корреляции Кендалла, корреляции Краскала, Спирмена и многие другие.
Зная истинные значения этих связей ? между случайными величинами, мы получаем то, что мы назвали reference network, или базовая сеть, основа. Та, которая имеет место, если мы посчитали характеристики между случайными величинами, провели ребра, и это их веса. Это сеть, которая не зависит ни от каких наблюдений, – она как бы предполагает, что это наша модель, модель нашей сети.
Вот такие структуры были популярны и популярны до сих пор.
Maximum Spanning Tree (MST): в полном графе любая последовательность вершин — это остовное дерево, но среди них надо выбрать с максимальной близостью (с тотальной близостью), и эта характеристика получила название максимальное остовное дерево. Вообще эта тема появилась в рамках темы «эконофизики» – когда профессиональные физики занимаются экономикой. Получается иногда хорошо, а иногда плохо.
Есть такой Eugene Stanley, очень известный человек, экономист и математик. Он это дело когда-то породил и поддерживал. И вот в рамках этого направления родились попытки анализа сетевых структур. С помощью MST был сделан анализ существующих рынков, чисто эмпирический анализ. Было замечено, что есть некие иерархические структуры, есть какие-то интересные наблюдения – можно это отнести к какому-то примитивному data mining. Вот мы хотим узнать, нет ли чего-то такого на рынке, чего мы пока не видим: построим вот это дерево, посмотрим, как оно изменяется (в момент кризиса там есть некоторые изменения) и т. д. То есть вокруг этого максимального остовного дерева есть какая-то деятельность.
Затем эта же группа людей (их там несколько, в том числе Мантенья) опубликовала в хорошем журнале интересную статью: они предложили взять в качестве характеристики не остовное дерево.
Planar Maximally Filtered Graph (PMFG) устроен так: берем алгоритм Краскала для построения остовного дерева, он очень простой: вы упорядочиваете все ребра и добавляете их в вашу конструкцию до тех пор пока не появляется цикл. Появляется цикл – его пропускаете и т. д. Так строится минимальное (максимальное в нашем случае, просто порядок надо другой сделать) остовное дерево. Эта структура бедновата. Почему? Там нет ни одной клики, то есть нет трех связанных между собой вершин, хотя в реальном рынке, скажем российском, максимальная клика графа рынка состоит из восьми компаний, которые очень тесно связаны между собой. Вы их всех знаете. И эти восемь компаний составляют 97% объема торгов всего рынка. Ни в одном другом рынке такой концентрации в максимальной клике нет. Максимальные клики, то есть тесно связанные между собой активы, есть и в американском, а в английском, и во французском, и в немецком, и в японском рынках, но они не представляют собой такого важного по капитализации или по объему торгов.
Теперь мы хотим построить не остовное дерево, а планарный граф с максимальными связями между этими активами. И делается так: упорядочивается снова и добавляем ребра, пока граф остается планарным. Если он перестает быть планарным, выбрасываем ребро и т. д. Так они предложили, и это была интересная работа. Ну почему только планарный? Тор, сфера с двумя ручками – на любой поверхности заданного рода вы можете построить такую конструкцию.
Какой интерес на поверхности рода G? У такого построенного графа будет всегда ограничен размер клики, и вроде бы это одно из достоинств – это не объяснялось, просто это некая характеристика. Парлаусен с учениками предложили такую конструкцию, она давно известна в теории графов, это так называемый threshold-метод, или отсеченный граф. Такая конструкция используется во многих методах data mining с применением графов. Фиксируем некоторый порог (specified threshold) и удаляем все ребра, вес которых меньше этого порога или равен ему, то есть оставляем только связи, которые представляют собой какую-то значимую величину, начиная с какого-то значения меры близости.
Если в графе для российского рынка найти максимальную клику, она окажется так устроена. Но тут могут быть интересны не только максимальные клики, в этом графе есть еще максимальные независимые множества (maximum independent sets). Оказалось (про это была небольшая эмпирическая работа), что они могут быть полезны, если мы хотим построить оптимальный портфель в модели Марковица. Наша цель – сохранить в портфеле небольшое число активов. В принципе вы можете использовать весь рынок и строить самый хороший портфель инвестиций с разных точек зрения, но в модели Марковица величина, которую мы хотим контролировать, вполне определенная: это полезность, в которой замешаны риск и доходность. Конечно, на рынке активов много – как найти те, что позволят построить хороший портфель? Оказалось, что независимые множества могут быть здесь полезными.
В частности, граф концентрации вот с таким графом связан, потому что на самом деле это одностороннее отсечение, а здесь нужно делать двухстороннее отсечение. Мы проверяем, что ноль или не ноль у нас частные корреляции, а можем строить доверительные интервалы – и получится задача, не сказать что в точности такая, но похожая.
Простой пример, он в точности взят из этой работы, как у нас, про Planar Maximally Filtered Graph. Подобрали аккуратно 10 активов, для чего:
Вот матрица корреляций, которые эмпирически сосчитаны по наблюдениям.
Вот maximum spanning tree (здесь minimum). Мы специально так подобрали – здесь один и второй кластер соединены между собой (и далее можно много рассуждать на эту тему, но нас это не интересует). Вот такой получилась эта структура.
Вот этот плоский граф – он уже не имеет красивой, хорошей визуализации, но у него мы можем посчитать.
Что касается отсеченного графа, вот здесь порог порядка 0,55, то вот он сам, в нем есть вот эта максимальная клика, шесть узлов, шесть активов очень тесно связаны между собой среди этих десяти, ну и вот еще нарисовано максимальное независимое множество. Независимых множеств здесь много, но вот это множество минимального веса (нарисовано). И максимальных клик тоже может оказаться много, и тоже можно выбрать ту, у которой максимальный вес (но это для примера).
Задача идентификации. Снова у нас есть набор наблюдений, ставим задачу так: у нас есть reference network, какая-то структура, ну например максимальное основное дерево или граф рынка. И мы хотим по наблюдениям эту структуру восстановить. Что интересно: сразу дано, что таких сетей мы можем построить очень много, в зависимости от того какую взяли меру близости. Сначала было непонятно, в чем между ними разница, потом выяснилось очень интересное (я вам это покажу) явление. Люди, не задумываясь, в значительной части работ просто берут рынок, берут какую-нибудь меру связи, считают, находят характеристики. Пытаются их интерпретировать или сделать какой-то анализ, на что это похоже и как бы это можно было с точки зрения рыка проанализировать. Наиболее интересно вот что: когда время идет, характеристики меняются, связи меняются. Что происходит в моменты кризиса? Наверное, не так трудно догадаться, что в моменты кризиса происходит увеличение связей. То есть все идут либо вниз, либо, если перед кризисом, они все дружно идут вверх. Такие феномены наблюдаются, на этом даже пытаются строить алгоритмы предсказания каких-то кризисов.
Что нас будет интересовать: как построить какую-нибудь процедуру идентификации? Я сейчас скажу про одну, примитивную, которой все пользуются. Как измерить неопределенность или качество этой процедуры (поскольку каждая процедура дает ошибку, как мы можем оценить эту ошибку?), ну а качество – это обратная величина к ошибке. Можем ли мы какие-то процедуры делать оптимальными и вообще говорить об этой оптимальности таких процедур.
И еще есть важная тема в статистике: для рынка является принципиально важным моментом, можем ли мы строить устойчивые, или робастные (robust) процедуры – то есть те, которые нечувствительны к рассматриваемому нами распределению. Потому что часто нам распределение неизвестно. Мы можем построить оптимальную для данного распределения процедуру, как только мы чуть-чуть это распределение меняем (ну например, мы не знаем, какое оно, оно у нас другое), то эта процедура дает значительно худший результат, чем какие-нибудь другие, более примитивные.
Вот на эти вопросы я постараюсь, как смогу, ответить.
Какая самая простая процедура приходит в голову? Мы же хотим восстановить структуру с некоторыми ?i,j, вот такими вот весами в взвешенном графе. Как будем делать? Давайте возьмем какую-нибудь оценку набора наблюдений, оценку этой характеристики ?i,j (с крышечкой).
Если это, например, корреляции Пирсона, то это будут выборочные корреляции Пирсона, если Кендалла – то выборочные корреляции Кендалла, знаковые корреляции (это совпадение знаков). И построим так называемый sample network (до этого у нас была reference network), это будет выборочная сеть.
Надо нам остовное дерево максимального веса – вот будем считать, что оно построено в этой выборочной сети. Тут его построим, вот оно у нас и есть. Нужен нам планарный максимально отфильтрованный граф – сделаем этот же самый алгоритм вот в этой сети (reference network) и будем считать, что это результат нашей идентификации, вот вы нашли ту структуру. Будет отсеченный граф (он задается характеристикой ?i,j? ?o), возьмем просто все выборочные связи, оценим и удалим те, которые меньше заданного порога или равны ему, и получим некий выборочный граф рынка. Собственно, это и есть объекты, с которыми все работают.
Если мы будем иметь другой набор наблюдений, понятно, что это у нас изменится. Здесь встает серьезная задача: как оценить ошибку, которая возникает, как оценить неопределенность той или иной структуры и как оценить качество тех процедур, которые мы можем предложить для этой идентификации.
Пойдем по этим задачам: возьмем самую простую модель – гауссово многомерное распределение. Между этими случайными величинами задана какая-то мера, мера близости, вот у нас стандартная статистическая модель Х(t): случайные величины, одинаково распределенные с этими в каждый момент времени t. Зададим вот этот граф reference threshold graph или reference marking graph с помощью некоторой матрицы инцидентности, будет 0, если ребра нет, 1– если ребро есть, ?o – это некоторый порог, просмотрим все такие матрицы инцидентности, какие только могут быть с N узлами.
И теперь мы можем сформулировать проблему идентификации как статистическую задачу со многими гипотезами. Есть разные термины: multiple decision problem и т. д. Нам нужно выбрать одну гипотезу из тех, которые здесь перечислены. Гипотез ровно столько, сколько есть этих матриц. И по наблюдениям нам нужно выбрать одну из них.
Что такое статистическая процедура, решающая правило будет в данном случае? Это отображение из пространства наблюдений в пространство решений. В качестве решения мы выбираем один из возможных графов из этого семейства. Одно построение я уже привел, но можно подойти к этой задаче и по-другому. Можно попытаться начать с тестирования так называемых индивидуальных гипотез. Тех, которые по каждому ребру отдельны. Индивидуальные гипотезы в этой модели – такие. Для максимального остовного дерева сформулировать индивидуальные гипотезы более сложно, но для данной задачи это возможно.
Дальше мы каким-то стандартным образом, с помощью некоторой статистики, строим решающее правило для каждой индивидуальной гипотезы и строим общее решающее правило ?(х), которое на каждый набор наблюдений, вот этот вот х, дает нам некую матрицу смежности того графа, который вы выбираете в качестве решения.
Теперь мы можем оценить ошибки, они бывают, как всегда в статистике, двух типов: ребро включено в построенный граф, но отсутствует в исходном графе или, наоборот, его нет в построенном графе, а в исходном оно было. Это стандартная ситуация с ошибками, и дальнейшее зависит от того, как мы определим функции потери. Для того чтобы измерять неопределенность или качество статистической процедуры, мы должны ввести некие функции потерь. Вот первая и вторая – достаточно простые и, в общем-то, стандартные. Здесь первая функция равна 0 только тогда, когда нет ошибок первого рода, а вторая – только когда нет ошибок второго рода. Можно сказать, что все, что связано
Есть еще один вариант введения потерь, который учитывает не только есть ошибка или нет, но и сколько их. Это так называемая аддитивная функция потерь, строится она так: мы можем оценить потери от ошибки первого рода для фиксированного ребра и от ошибки второго рода. Эти две ошибки являются потерями при проверке индивидуальной гипотезы, а аддитивная функция потерь будет складываться из этих индивидуальных потерь.
Ну и само качество статистической процедуры может быть измерено с помощью так называемого условного риска, который является математическим ожиданием этой функции потерь. Что касается первой функции потерь, то это будет просто вероятность совершить хотя бы одну ошибку первого рода, это будет вероятность совершить хотя бы одну ошибку второго рода. Как обычно в статистике классической теории, что доказано и какие общепринятые результаты используются, как мы строим хорошие тесты? Мы фиксируем уровень ошибки первого рода, вот эту вероятность, и стараемся подобрать такой тест, чтобы он минимизировал нам ошибку второго рода, она еще называется «мощность теста». И с помощью леммы Неймана – Пирсона вы можете строить равномерно наиболее мощные тесты.
Вот, к сожалению, для проверки многих гипотез это перестает работать. Здесь вы ничего практически не можете контролировать. Даже если каким-то образом получится контролировать ошибку первого рода, то полностью выпадает из под контроля ошибка второго рода. Не найдено способов или теоретических результатов, позволяющих строить хоть в каком-то смысле хорошие статистические процедуры. Какие есть практические статистические процедуры? Тут многие из них перечислены – их общая идея в том, что надо последовательно отбирать, рассматривать не сразу все, а одну гипотезу за другой, изменяя каждый раз уровень значимости теста, который делает этот отбор. Если мы возьмем известную процедуру Холма, то сначала мы отбираем, берем максимум. Скажем, мы хотим построить такой же отсеченный граф статистику максимальное значение всех статистик, которые построили в виде индивидуального теста, и сравниваем с порогом соответствующему уровню значимости альфа делить на n – с очень большим порогом. И потом, каждый раз отсекая лишнее, добираемся до последнего актива. Такие применяются практические процедуры. Никто не знает, что происходит при этом с ошибкой второго рода. Потому что что-то мы контролируем и довольствуемся тем, что удается сделать.
Используем другую характеристику в качестве качества статистической процедуры, связанную с аддитивной функцией потерь, – здесь эта характеристика написана формально. Что в ней нового? То, что, во-первых, мы измеряем потери от каждого индивидуального ошибочного решения и, во-вторых, эти потери складываем. То есть важно не только то, что у нас есть ошибка, но и то,, сколько у нас ошибок. Такая функция потерь, на наш взгляд, в ситуации с отсеченным графом является более адекватной, чем просто оценка того, что есть хотя бы одна ошибка первого или второго рода.
Такой вариант позволяет нам измерить статистическую неопределенность любой статистической процедуры с помощью этого условного риска.
Например, таким образом мы фиксируем какой-то уровень условного риска и подсчитываем необходимое число наблюдений для того, чтобы этого уровня достичь.
Здесь мы видим довольно интересные результаты. Эту ситуацию можно немного упростить для вычислений, вот здесь рассмотрен частный случай аддитивной функции потерь, которая связана в чистом виде с количеством ошибок первого рода, второго – вот эти две случайные величины.
Вводим две характеристики: максимально возможное количество ошибок первого или второго рода, вводим такую характеристику, снова случайную величину, и получаем «ожидаемое значение» общего уровня ошибки. Это будет условный риск аддитивной функции потерь при таком выборе потерь в первом и во втором случае, а в принципе аддитивные функции потерь вы можете более широко варьировать, для того чтобы измерять эту неопределенность. Еще это имеет название Per Family Error Rate.
Это характеристика, которую мы считаем как условный риск от этих случайных величин. И это может служить оценкой неопределенности определения той или иной структуры при заданной статистической процедуре, которую вы используете.
Для МST максимальное число ошибок первого и второго рода одинаково, = N-1.
Для PMFG – вот такое число. Для отсеченного графа они разные, но фиксированные. Тут потери мы считаем с учетом того, сколько всего можем потерять, это некоторая особенность.
Эксперименты неожиданно для нас показали неожиданный результат: вот, уже на реальных рынках (это представлен французский рынок), самым неопределенным оказывается Planar Maximally Filtered Graph, вот его картинка, затем идет MST, и граф рынка, и этот отсеченный граф имеют более хорошее качество идентификации. Процедура, которую я описал, самая примитивная: делаем оценку корреляций Пирсона и просто по ней строим соответствующую структуру. Интересно, что для правильного определения максимального остовного дерева с уровнем в 0,1 с точностью в 10% не хватает 10 000 наблюдений. В принципе, ни на каком рынке у вас столько нет.
Этот феномен на всех рынках, какой бы вы ни взяли, и на каждом из них всегда всех хуже по PMFG, потом по MST и потом уже отсеченные графы. Рецензенты нам пишут, что PMFG не может быть плохим, потому что он эффективно используется при кластеризации. Но после наших аргументов, они признали и статья была опубликована. Но этот феномен это какое-то свойство корреляционных матриц, это не общее свойство, легко придумать матрицу ковариаций, то есть связей, где наоборот все будет, где будет хорошо определяться PMFG, можно сделать любой порядок, надо только аккуратно подобрать эти связи.
Существует другой подход: в 50-е годы американский статистик Ленман развивал теорию множественной проверки гипотез и он именно хотел строить в каком-то смысле оптимальные процедуры. Ему была важна аддитивность функции потерь, было важно иметь индивидуальные гипотезы, которые мы проверяем, в его понимании они называются generating hypotheses, тут мы не вникаем в детали, но наиболее важным условием подбора этих гипотез является условие совместимости. Грубо говоря, чтобы мы без противоречий могли комбинировать из них основные гипотезы, множественные, из которых надо сделать вывод. Это всегда требует проверки. А главный его результат состоял в том, что если порождающие гипотезы хорошо выбрать, и подобрать для них оптимальные тесты, и использовать в качестве целевой функции качества статистической процедуры аддитивную функцию потерь, то из оптимальности тестов для порождающей гипотезы будет следовать оптимальность тестов множественной проверки гипотез при условии несмещенности. Несмещенность без множественной проверки – понятная вещь. А когда у вас много гипотез, непонятно, что значит несмещенная статистическая процедура.
Здесь написано оно из определений, которое предложил Ленман. Его смысл такой: в качестве параметра для нормального распределения матрица ? будет влиять на функцию потерь.
Должно быть такое неравенство для несмещенной статистической процедуры. Если S связано с параметром так, что они согласованы, то, какую-то бы другую гипотезу ни взять, она будет хуже. Статистическая процедура на ней даст более плохой результат. Тогда она считается несмещенной. Несмещенность интересно проявляет себя в разных задачах.
Например, в сети Пирсона корреляций, применяя эту теорию аккуратно, оценив, что значит несмещенность, получается достаточно хорошо. Порождающие гипотезы надо по-настоящему проверять – строить оптимальный, равномерный и наиболее мощный тест, он существует. И мы можем гарантировать оптимальность полученного теста для множественной проверки гипотез. Но вот при таком условии: если а+b=1, положительно, это будет уровень ошибки первого рода, а это будет уровень ошибки второго рода. Характеристика теста вполне естественная, несмещенность для индивидуальных гипотез означает ровно это свойство.
Теперь вернемся к самому началу. Было выполнено много разных работ с разными корреляциями. Все они между собой очень интересно связаны, это работа Краскала. Оказывается, для нормального распределения между этими величинами, всеми корреляциями есть простая связь, что интересно – связь монотонная. Это означает, что если вы строите минимальное остовное дерево в одной сети, то точно таким же оно будет в другой сети, потому что процедура основана на упорядочивании. Отсеченный граф точно такой же, только надо выбрать другой порог, согласованный с этим. Planar Мaximally Filtered Graph – тоже, то есть по сути дела, сами по себе эти структуры никак не зависят от того, что мы выбрали другую меру связи. Однако если мы начнем применять статистическую процедуру – любую, даже самую примитивную,, мы увидим, что они совершенно разные – у этих статистических процедур разные качества, разные свойства, никакой связи между ними уже нет. Хорошо это или плохо? Оказалось, что хорошо.
Возьмем такую простую характеристику, как похожесть знаков. Это вероятность совпадения знаков случайной величины по отношению к среднему. Что касается, например, двух временных рядов на финансовом рынке, то это вообще естественная характеристика: были ли у них в этот момент доходности положительными, или отрицательными, или разнонаправленными. Совпадение знаков – это просто их движение: либо оба вверх, либо оба вниз. Для этой характеристики тоже с точки зрения условного риска и функции потери, подбора порождающих гипотез можно построить соответствующую оптимальную статистическую процедуру.
Небольшое введение: пока мы рассматривали только гауссовские равномерные распределения, но существует много разных других, и была бы интересна задача в более широком классе. Такой класс, естественно, известен – так называемые эллиптические распределения, постоянные на эллипсоидах. Там есть нормальные распределения (все зависит от функции G), но там есть и распределения Стьюдента. Чем они отличаются – вот у этого распределения тяжелые хвосты, тут даже может не быть каких-то моментов, начиная с некоторого места. аА у нормального распределения все хорошо, никаких тяжелых хвостов нет, и если рыночные доходности моделировать, то с тяжелыми хвостами встречаются, поэтому эта характеристика важна.
Основное утверждение, неожиданное для нас, оказалось такое: этот условный риск в сети, построенной на совпадении знаков, не зависит от распределения (лишь бы одна матрица сигма была), соответствующая статистическая процедура оказывается устойчивой (просто имеет одинаковые значения) и остается оптимальной. Если брать сеть корреляций Пирсона, то там построенная оптимальная статистическая процедура сразу перестает быть оптимальной при небольших отклонениях от гауссова распределения в сторону Стьюдента – это легко моделируется на графике.
И заодно доказали, что все связи между этими мерами, которые Краскал вывел для гауссовских распределений, в этом классе распределений тоже верны.
Что это дает? Во-первых, с нашей точки зрения, совпадение знаков становится привлекательной мерой близости для этих задач. Не зная распределения, у нас больше уверенность, что мы получим точный результат, из-за того, что получилась робастная статистическая процедура, вот та, которую мы построили, только о ней идет речь, оптимальная.
Куда двигаться? В идентификации графа концентраций мы тоже можем построить для аддитивной функции потерь (а я не знаю, почему в графе концентраций рассматривают только эти ошибки. Даже там, ну неужели важно, чтобы было – одно ребро не провели и вот, ошибка? Там так же важно, сколько ребер мы ошиблись, сколько неправильных связей добавилось, сколько исчезло). Оптимальная процедура имеет очень интересный, неожиданный вид – это так называемые структуры Неймана. Это означает, что в оптимальной процедуре при построении статистики мы должны учитывать значения всех наблюдений (хотя мы проверяли гипотезу для двух). В этой задаче проверка ноль или не ноль, проверяют всего частные корреляции, гипотезу о частных корреляциях двух случайных величин, но тест включает в себя значения всех остальных.
Другое интересное направление, что было замечено для этого отсеченного графа на реальных финансовых рынках: если распределение степеней вершин подчиняется степенному закону – да, при некоторых значениях порога, никто не знает, что это, но наблюдается. На логарифмической шкале какая-то такая связь. Дальше я бы выделил, что есть определенные предпочтения в порядке неопределенности между этими структурами, общее для всех. Еще одно явление было выявлено: что если брать ансамбль Вишера-Лагерра, то по теореме Пастура-Марченко при определенном соотношении между числом наблюдений и размерностью этой матрицы собственные значения попадают в интервал Там есть круговое распределение, закон этих собственных значений. А для этих матриц рынка, ковариационных и вариационных обнаружилось, что явление, которое отличает, как бы они выходят за рамки этой теории, то есть они чем-то отличаются – на всех практически рынках есть одно большое собственное значение, значительно превышающее все остальные. Оно одно выделяется, а дальше как бы все к этому интервалу начинают приближаться. Этому есть объяснение, есть такое понятие как индекс рынка. А что такое собственное значение, оно чему соотвествует – когда вы матрицу на транспонируемую умножаете, то первое собственное значение это будет первый фактор в методе главных компонент. И у вас в чистом виде выделяется так называемый индекс рынка – та характеристика, изменения которой связаны с изменениями всех остальных с достаточно большой точностью.
Мера совпадения знаков очень легко распространяется на 3, 4, 5 случайных величин, и мы уже можем строить гиперграф. Взвешенный гиперграф – когда вы берете вершины, любое подмножество вершин имеет весы. Легко этот вес вот это и будет общность их знаков, вероятность совпадения знаков этих вершин. Как только у вас такой гиперграф есть, известно, что из него можно сделать некоторое распределение Бернулли на этих вершинах. Смысл этого распределения мы пока не понимаем, но кажется, там будет что-то интересное. Это именно то, чем мы сейчас занимаемся.
Несколько публикаций на эту тему.
***
Коллоквиум факультета компьютерных наук ВШЭ – специальные семинары, на которые могут приходить не только студенты или сотрудники ФКН, но и все желающие. Их проводят учёные не только из Вышки, но и из других вузов и научных центров — МГУ, МФТИ, Математического института и института системного анализа РАН, MIT, Microsoft Research, Школы анализа данных Яндекса. Найти все прошедшие коллоквиумы можно здесь. По этой же ссылке можно будет и записаться на будущие занятия, когда начнётся новый учебный год.
В условиях статистической природы исходных данных возникает задача идентификации сетевых структур. Лекция, которую мы выбрали для вас сегодня, посвящена недавнему развитию этой темы в рамках теории одновременной проверки многих статистических гипотез (multiple decision statistical procedures, multiple test procedures). Такой подход позволяет разработать методы оценки статистической неопределенности сетевых структур и выделить оптимальные и устойчивые статистические процедуры идентификации. Оказывается, что сетевые структуры, построенные по вероятностям совпадения знаков, оказываются предпочтительными перед структурами, построенными по классическим корреляциям Пирсона. В рассказе рассмотрены приложения результатов к анализу фондовых рынков.
Доклад был прочитан на факультете компьютерных наук, открытом при поддержке Яндекса в Вышке. Лектор Валерий Калягин — доктор физико-математических наук, ординарный профессор НИУ ВШЭ. Заведует кафедрой прикладной математики и информатики и лабораторией алгоритмов и технологий анализа сетевых структур НИУ ВШЭ в Нижнем Новгороде.
Под катом — полная расшифровка лекции.
Задача идентификации сетевых структур для нас была совершенно новой – мы начали ею заниматься в 2012 году, когда была создана лаборатория. Одна из задач в этой лаборатории была связана именно с некоторыми сетевыми структурами. Мы заинтересовались ею иначе, чем она была поставлена. То, что я буду рассказывать, в большей степени математическая часть, чем прикладная.
Задача на первый взгляд очень несложная, понять ее смогут все. Есть полный взвешенный граф, назовем его сетью, в котором N узлов. Что эту задачу выделяет – так это то, что с каждым узлом мы связываем некую случайную величину. Тем самым у нас есть некоторый случайный вектор (многомерный, N-мерный случайный вектор). Затем, есть какие-то связи между этими случайными величинами. Они измеряются некоторой функцией (у нее очень много названий: similarity, association, dependence…), которая является характеристикой связи двух случайных величин. Вот такой, пока еще абстрактный поток. Сетевая структура для нас – это некоторый граф, который мы можем из этой сети извлечь, подграф этой сети. Не любой, а интересный, с какими-то хорошими, полезными может быть, свойствами.
Задача идентификации формулируется следующим образом: у нас имеется выборка длины n из этого случайного многомерного распределения, этого вектора, n наблюдений. И нам нужно отождествить по наблюдениям ту структуру, которая в сети каким-то образом по связям между случайными величинами была определена. То есть существует какая-то скрытая от нас структура, есть наблюдения, и мы должны по наблюдениям эту структуру восстановить. Типичная задача статистики. Единственное, что, может быть, объект немного непривычный: объектом, который нужно восстановить, является граф. Эта задача, естественно, в такой общей постановке (тем более что мы не знаем, что такое структура) никогда не решается.
Есть несколько примеров, так называемые гауссовские графические, или графовые модели. Это многомерные нормальные распределения, связь между узлами задается так называемыми частными корреляциями между двумя случайными величинами. Частные корреляции так называемую чистую связь, из которой исключено влияние всех остальных. На математическом языке эти случайные корреляции напрямую связаны с элементами обратной матрицы
?-1. В качестве сетевой структуры – граф концентрации. Граф концентрации строится очень просто: если между ними связь нулевая, то мы ребро не проводим, если ненулевая – проводим. На самом деле это для обратной матрицы ковариаций ноль или не ноль (для соответствующих ковариаций). Сама по себе теория гауссовских графовых (графических) моделей – довольно продвинутая вещь, есть много книг на эту тему. Там возникают очень интересные условные распределения.
Немного повозившись, можно увидеть, что если какие-то связи отсутствуют, то они могут отсутствовать еще где-то (пока так, очень неточно). И, соответственно, здесь исследуется, как устроены распределения, когда задан граф концентрации.
Более интересна здесь для нас задача идентификации – именно об этом я и хочу поговорить. Вы располагаете наблюдениями над этими случайными векторами и должны на базе этих наблюдений идентифицировать граф концентраций. И вот здесь появляется то новое, что, собственно, повлияло на всю остальную деятельность, – теперь вы должны проверять не одну гипотезу. Сейчас я попытаюсь это объяснить: мы можем выделить какое-то ребро и проверять гипотезу,, равны частные корреляции здесь нулю или нет. Такой подход будет неправильным; формально мы его применить можем, но какое качество будет у такой статистической процедуры идентификации графа концентраций, сказать трудно, и вот почему: изначально между этими случайными величинами есть связи, и в проверках каждой индивидуальной гипотезы эти связи могут сыграть роль. Если мы примитивно попытаемся проверять эти индивидуальные гипотезы, не учитывая существующие зависимости между случайными величинами, получатся не самые хорошие статистические процедуры. В последнее время для идентификации этого графа концентраций строится много процедур, все более точных, все более адекватных. Новое здесь то, что вы должны проверять сразу много гипотез – вот так правильно ставится задача. Проверять не по отдельности каждую, а сразу много. Позже покажу, в той постановке, как мы ее видим; просто априори графом концентраций может быть любой граф – и это одна гипотеза, и этих гипотез столько, сколько всего графов со всеми вершинами. И нам нужно из них из всех выбрать одну – наиболее адекватную наблюдениям, которые у нас есть.
Другая модель – это так называемая сетевая модель рынка: активы на рынке соответствуют вершинам сети, связь между активами задается некоторым взвешенным ребром, и вес ребра отражает общность (similarity) в поведении активов. Эта сеть получается полным взвешенным графом, случайные величины здесь – некоторые характеристики этих активов. Я написал цены, но цены в нашу модель не вкладываются, потому что ценообразование моделируется скорее мартингалом. Это более сложная конструкция, она уж точно никак не является таким случайным процессом – понятно, что цена в каждый новый момент времени зависит от предыдущего. Если сделать некоторые предположения, то будет некоторый случайный процесс со свойством мартингала, но вот доходности, объемы продаж вполне в эту модель укладываются. Доходности обладают нужными нам свойствами, можно считать их независимыми и одинаково распределенными, потому что у нас там выборка, которую мы делаем. Это стандартная выборка: независимые, одинаково распределенные случайные величины. В литературе используются различные меры связи между случайными величинами, в нашем случае – между активами: корреляции Пирсона, частные корреляции, корреляции знаков, ? (тау) корреляции Кендалла, корреляции Краскала, Спирмена и многие другие.
Зная истинные значения этих связей ? между случайными величинами, мы получаем то, что мы назвали reference network, или базовая сеть, основа. Та, которая имеет место, если мы посчитали характеристики между случайными величинами, провели ребра, и это их веса. Это сеть, которая не зависит ни от каких наблюдений, – она как бы предполагает, что это наша модель, модель нашей сети.
Вот такие структуры были популярны и популярны до сих пор.
Maximum Spanning Tree (MST): в полном графе любая последовательность вершин — это остовное дерево, но среди них надо выбрать с максимальной близостью (с тотальной близостью), и эта характеристика получила название максимальное остовное дерево. Вообще эта тема появилась в рамках темы «эконофизики» – когда профессиональные физики занимаются экономикой. Получается иногда хорошо, а иногда плохо.
Есть такой Eugene Stanley, очень известный человек, экономист и математик. Он это дело когда-то породил и поддерживал. И вот в рамках этого направления родились попытки анализа сетевых структур. С помощью MST был сделан анализ существующих рынков, чисто эмпирический анализ. Было замечено, что есть некие иерархические структуры, есть какие-то интересные наблюдения – можно это отнести к какому-то примитивному data mining. Вот мы хотим узнать, нет ли чего-то такого на рынке, чего мы пока не видим: построим вот это дерево, посмотрим, как оно изменяется (в момент кризиса там есть некоторые изменения) и т. д. То есть вокруг этого максимального остовного дерева есть какая-то деятельность.
Затем эта же группа людей (их там несколько, в том числе Мантенья) опубликовала в хорошем журнале интересную статью: они предложили взять в качестве характеристики не остовное дерево.
Planar Maximally Filtered Graph (PMFG) устроен так: берем алгоритм Краскала для построения остовного дерева, он очень простой: вы упорядочиваете все ребра и добавляете их в вашу конструкцию до тех пор пока не появляется цикл. Появляется цикл – его пропускаете и т. д. Так строится минимальное (максимальное в нашем случае, просто порядок надо другой сделать) остовное дерево. Эта структура бедновата. Почему? Там нет ни одной клики, то есть нет трех связанных между собой вершин, хотя в реальном рынке, скажем российском, максимальная клика графа рынка состоит из восьми компаний, которые очень тесно связаны между собой. Вы их всех знаете. И эти восемь компаний составляют 97% объема торгов всего рынка. Ни в одном другом рынке такой концентрации в максимальной клике нет. Максимальные клики, то есть тесно связанные между собой активы, есть и в американском, а в английском, и во французском, и в немецком, и в японском рынках, но они не представляют собой такого важного по капитализации или по объему торгов.
Теперь мы хотим построить не остовное дерево, а планарный граф с максимальными связями между этими активами. И делается так: упорядочивается снова и добавляем ребра, пока граф остается планарным. Если он перестает быть планарным, выбрасываем ребро и т. д. Так они предложили, и это была интересная работа. Ну почему только планарный? Тор, сфера с двумя ручками – на любой поверхности заданного рода вы можете построить такую конструкцию.
Какой интерес на поверхности рода G? У такого построенного графа будет всегда ограничен размер клики, и вроде бы это одно из достоинств – это не объяснялось, просто это некая характеристика. Парлаусен с учениками предложили такую конструкцию, она давно известна в теории графов, это так называемый threshold-метод, или отсеченный граф. Такая конструкция используется во многих методах data mining с применением графов. Фиксируем некоторый порог (specified threshold) и удаляем все ребра, вес которых меньше этого порога или равен ему, то есть оставляем только связи, которые представляют собой какую-то значимую величину, начиная с какого-то значения меры близости.
Если в графе для российского рынка найти максимальную клику, она окажется так устроена. Но тут могут быть интересны не только максимальные клики, в этом графе есть еще максимальные независимые множества (maximum independent sets). Оказалось (про это была небольшая эмпирическая работа), что они могут быть полезны, если мы хотим построить оптимальный портфель в модели Марковица. Наша цель – сохранить в портфеле небольшое число активов. В принципе вы можете использовать весь рынок и строить самый хороший портфель инвестиций с разных точек зрения, но в модели Марковица величина, которую мы хотим контролировать, вполне определенная: это полезность, в которой замешаны риск и доходность. Конечно, на рынке активов много – как найти те, что позволят построить хороший портфель? Оказалось, что независимые множества могут быть здесь полезными.
В частности, граф концентрации вот с таким графом связан, потому что на самом деле это одностороннее отсечение, а здесь нужно делать двухстороннее отсечение. Мы проверяем, что ноль или не ноль у нас частные корреляции, а можем строить доверительные интервалы – и получится задача, не сказать что в точности такая, но похожая.
Простой пример, он в точности взят из этой работы, как у нас, про Planar Maximally Filtered Graph. Подобрали аккуратно 10 активов, для чего:
Вот матрица корреляций, которые эмпирически сосчитаны по наблюдениям.
Вот maximum spanning tree (здесь minimum). Мы специально так подобрали – здесь один и второй кластер соединены между собой (и далее можно много рассуждать на эту тему, но нас это не интересует). Вот такой получилась эта структура.
Вот этот плоский граф – он уже не имеет красивой, хорошей визуализации, но у него мы можем посчитать.
Что касается отсеченного графа, вот здесь порог порядка 0,55, то вот он сам, в нем есть вот эта максимальная клика, шесть узлов, шесть активов очень тесно связаны между собой среди этих десяти, ну и вот еще нарисовано максимальное независимое множество. Независимых множеств здесь много, но вот это множество минимального веса (нарисовано). И максимальных клик тоже может оказаться много, и тоже можно выбрать ту, у которой максимальный вес (но это для примера).
Задача идентификации. Снова у нас есть набор наблюдений, ставим задачу так: у нас есть reference network, какая-то структура, ну например максимальное основное дерево или граф рынка. И мы хотим по наблюдениям эту структуру восстановить. Что интересно: сразу дано, что таких сетей мы можем построить очень много, в зависимости от того какую взяли меру близости. Сначала было непонятно, в чем между ними разница, потом выяснилось очень интересное (я вам это покажу) явление. Люди, не задумываясь, в значительной части работ просто берут рынок, берут какую-нибудь меру связи, считают, находят характеристики. Пытаются их интерпретировать или сделать какой-то анализ, на что это похоже и как бы это можно было с точки зрения рыка проанализировать. Наиболее интересно вот что: когда время идет, характеристики меняются, связи меняются. Что происходит в моменты кризиса? Наверное, не так трудно догадаться, что в моменты кризиса происходит увеличение связей. То есть все идут либо вниз, либо, если перед кризисом, они все дружно идут вверх. Такие феномены наблюдаются, на этом даже пытаются строить алгоритмы предсказания каких-то кризисов.
Что нас будет интересовать: как построить какую-нибудь процедуру идентификации? Я сейчас скажу про одну, примитивную, которой все пользуются. Как измерить неопределенность или качество этой процедуры (поскольку каждая процедура дает ошибку, как мы можем оценить эту ошибку?), ну а качество – это обратная величина к ошибке. Можем ли мы какие-то процедуры делать оптимальными и вообще говорить об этой оптимальности таких процедур.
И еще есть важная тема в статистике: для рынка является принципиально важным моментом, можем ли мы строить устойчивые, или робастные (robust) процедуры – то есть те, которые нечувствительны к рассматриваемому нами распределению. Потому что часто нам распределение неизвестно. Мы можем построить оптимальную для данного распределения процедуру, как только мы чуть-чуть это распределение меняем (ну например, мы не знаем, какое оно, оно у нас другое), то эта процедура дает значительно худший результат, чем какие-нибудь другие, более примитивные.
Вот на эти вопросы я постараюсь, как смогу, ответить.
Какая самая простая процедура приходит в голову? Мы же хотим восстановить структуру с некоторыми ?i,j, вот такими вот весами в взвешенном графе. Как будем делать? Давайте возьмем какую-нибудь оценку набора наблюдений, оценку этой характеристики ?i,j (с крышечкой).
Если это, например, корреляции Пирсона, то это будут выборочные корреляции Пирсона, если Кендалла – то выборочные корреляции Кендалла, знаковые корреляции (это совпадение знаков). И построим так называемый sample network (до этого у нас была reference network), это будет выборочная сеть.
Надо нам остовное дерево максимального веса – вот будем считать, что оно построено в этой выборочной сети. Тут его построим, вот оно у нас и есть. Нужен нам планарный максимально отфильтрованный граф – сделаем этот же самый алгоритм вот в этой сети (reference network) и будем считать, что это результат нашей идентификации, вот вы нашли ту структуру. Будет отсеченный граф (он задается характеристикой ?i,j? ?o), возьмем просто все выборочные связи, оценим и удалим те, которые меньше заданного порога или равны ему, и получим некий выборочный граф рынка. Собственно, это и есть объекты, с которыми все работают.
Если мы будем иметь другой набор наблюдений, понятно, что это у нас изменится. Здесь встает серьезная задача: как оценить ошибку, которая возникает, как оценить неопределенность той или иной структуры и как оценить качество тех процедур, которые мы можем предложить для этой идентификации.
Пойдем по этим задачам: возьмем самую простую модель – гауссово многомерное распределение. Между этими случайными величинами задана какая-то мера, мера близости, вот у нас стандартная статистическая модель Х(t): случайные величины, одинаково распределенные с этими в каждый момент времени t. Зададим вот этот граф reference threshold graph или reference marking graph с помощью некоторой матрицы инцидентности, будет 0, если ребра нет, 1– если ребро есть, ?o – это некоторый порог, просмотрим все такие матрицы инцидентности, какие только могут быть с N узлами.
И теперь мы можем сформулировать проблему идентификации как статистическую задачу со многими гипотезами. Есть разные термины: multiple decision problem и т. д. Нам нужно выбрать одну гипотезу из тех, которые здесь перечислены. Гипотез ровно столько, сколько есть этих матриц. И по наблюдениям нам нужно выбрать одну из них.
Что такое статистическая процедура, решающая правило будет в данном случае? Это отображение из пространства наблюдений в пространство решений. В качестве решения мы выбираем один из возможных графов из этого семейства. Одно построение я уже привел, но можно подойти к этой задаче и по-другому. Можно попытаться начать с тестирования так называемых индивидуальных гипотез. Тех, которые по каждому ребру отдельны. Индивидуальные гипотезы в этой модели – такие. Для максимального остовного дерева сформулировать индивидуальные гипотезы более сложно, но для данной задачи это возможно.
Дальше мы каким-то стандартным образом, с помощью некоторой статистики, строим решающее правило для каждой индивидуальной гипотезы и строим общее решающее правило ?(х), которое на каждый набор наблюдений, вот этот вот х, дает нам некую матрицу смежности того графа, который вы выбираете в качестве решения.
Теперь мы можем оценить ошибки, они бывают, как всегда в статистике, двух типов: ребро включено в построенный граф, но отсутствует в исходном графе или, наоборот, его нет в построенном графе, а в исходном оно было. Это стандартная ситуация с ошибками, и дальнейшее зависит от того, как мы определим функции потери. Для того чтобы измерять неопределенность или качество статистической процедуры, мы должны ввести некие функции потерь. Вот первая и вторая – достаточно простые и, в общем-то, стандартные. Здесь первая функция равна 0 только тогда, когда нет ошибок первого рода, а вторая – только когда нет ошибок второго рода. Можно сказать, что все, что связано
Есть еще один вариант введения потерь, который учитывает не только есть ошибка или нет, но и сколько их. Это так называемая аддитивная функция потерь, строится она так: мы можем оценить потери от ошибки первого рода для фиксированного ребра и от ошибки второго рода. Эти две ошибки являются потерями при проверке индивидуальной гипотезы, а аддитивная функция потерь будет складываться из этих индивидуальных потерь.
Ну и само качество статистической процедуры может быть измерено с помощью так называемого условного риска, который является математическим ожиданием этой функции потерь. Что касается первой функции потерь, то это будет просто вероятность совершить хотя бы одну ошибку первого рода, это будет вероятность совершить хотя бы одну ошибку второго рода. Как обычно в статистике классической теории, что доказано и какие общепринятые результаты используются, как мы строим хорошие тесты? Мы фиксируем уровень ошибки первого рода, вот эту вероятность, и стараемся подобрать такой тест, чтобы он минимизировал нам ошибку второго рода, она еще называется «мощность теста». И с помощью леммы Неймана – Пирсона вы можете строить равномерно наиболее мощные тесты.
Вот, к сожалению, для проверки многих гипотез это перестает работать. Здесь вы ничего практически не можете контролировать. Даже если каким-то образом получится контролировать ошибку первого рода, то полностью выпадает из под контроля ошибка второго рода. Не найдено способов или теоретических результатов, позволяющих строить хоть в каком-то смысле хорошие статистические процедуры. Какие есть практические статистические процедуры? Тут многие из них перечислены – их общая идея в том, что надо последовательно отбирать, рассматривать не сразу все, а одну гипотезу за другой, изменяя каждый раз уровень значимости теста, который делает этот отбор. Если мы возьмем известную процедуру Холма, то сначала мы отбираем, берем максимум. Скажем, мы хотим построить такой же отсеченный граф статистику максимальное значение всех статистик, которые построили в виде индивидуального теста, и сравниваем с порогом соответствующему уровню значимости альфа делить на n – с очень большим порогом. И потом, каждый раз отсекая лишнее, добираемся до последнего актива. Такие применяются практические процедуры. Никто не знает, что происходит при этом с ошибкой второго рода. Потому что что-то мы контролируем и довольствуемся тем, что удается сделать.
Используем другую характеристику в качестве качества статистической процедуры, связанную с аддитивной функцией потерь, – здесь эта характеристика написана формально. Что в ней нового? То, что, во-первых, мы измеряем потери от каждого индивидуального ошибочного решения и, во-вторых, эти потери складываем. То есть важно не только то, что у нас есть ошибка, но и то,, сколько у нас ошибок. Такая функция потерь, на наш взгляд, в ситуации с отсеченным графом является более адекватной, чем просто оценка того, что есть хотя бы одна ошибка первого или второго рода.
Такой вариант позволяет нам измерить статистическую неопределенность любой статистической процедуры с помощью этого условного риска.
Например, таким образом мы фиксируем какой-то уровень условного риска и подсчитываем необходимое число наблюдений для того, чтобы этого уровня достичь.
Здесь мы видим довольно интересные результаты. Эту ситуацию можно немного упростить для вычислений, вот здесь рассмотрен частный случай аддитивной функции потерь, которая связана в чистом виде с количеством ошибок первого рода, второго – вот эти две случайные величины.
Вводим две характеристики: максимально возможное количество ошибок первого или второго рода, вводим такую характеристику, снова случайную величину, и получаем «ожидаемое значение» общего уровня ошибки. Это будет условный риск аддитивной функции потерь при таком выборе потерь в первом и во втором случае, а в принципе аддитивные функции потерь вы можете более широко варьировать, для того чтобы измерять эту неопределенность. Еще это имеет название Per Family Error Rate.
Это характеристика, которую мы считаем как условный риск от этих случайных величин. И это может служить оценкой неопределенности определения той или иной структуры при заданной статистической процедуре, которую вы используете.
Для МST максимальное число ошибок первого и второго рода одинаково, = N-1.
Для PMFG – вот такое число. Для отсеченного графа они разные, но фиксированные. Тут потери мы считаем с учетом того, сколько всего можем потерять, это некоторая особенность.
Эксперименты неожиданно для нас показали неожиданный результат: вот, уже на реальных рынках (это представлен французский рынок), самым неопределенным оказывается Planar Maximally Filtered Graph, вот его картинка, затем идет MST, и граф рынка, и этот отсеченный граф имеют более хорошее качество идентификации. Процедура, которую я описал, самая примитивная: делаем оценку корреляций Пирсона и просто по ней строим соответствующую структуру. Интересно, что для правильного определения максимального остовного дерева с уровнем в 0,1 с точностью в 10% не хватает 10 000 наблюдений. В принципе, ни на каком рынке у вас столько нет.
Этот феномен на всех рынках, какой бы вы ни взяли, и на каждом из них всегда всех хуже по PMFG, потом по MST и потом уже отсеченные графы. Рецензенты нам пишут, что PMFG не может быть плохим, потому что он эффективно используется при кластеризации. Но после наших аргументов, они признали и статья была опубликована. Но этот феномен это какое-то свойство корреляционных матриц, это не общее свойство, легко придумать матрицу ковариаций, то есть связей, где наоборот все будет, где будет хорошо определяться PMFG, можно сделать любой порядок, надо только аккуратно подобрать эти связи.
Существует другой подход: в 50-е годы американский статистик Ленман развивал теорию множественной проверки гипотез и он именно хотел строить в каком-то смысле оптимальные процедуры. Ему была важна аддитивность функции потерь, было важно иметь индивидуальные гипотезы, которые мы проверяем, в его понимании они называются generating hypotheses, тут мы не вникаем в детали, но наиболее важным условием подбора этих гипотез является условие совместимости. Грубо говоря, чтобы мы без противоречий могли комбинировать из них основные гипотезы, множественные, из которых надо сделать вывод. Это всегда требует проверки. А главный его результат состоял в том, что если порождающие гипотезы хорошо выбрать, и подобрать для них оптимальные тесты, и использовать в качестве целевой функции качества статистической процедуры аддитивную функцию потерь, то из оптимальности тестов для порождающей гипотезы будет следовать оптимальность тестов множественной проверки гипотез при условии несмещенности. Несмещенность без множественной проверки – понятная вещь. А когда у вас много гипотез, непонятно, что значит несмещенная статистическая процедура.
Здесь написано оно из определений, которое предложил Ленман. Его смысл такой: в качестве параметра для нормального распределения матрица ? будет влиять на функцию потерь.
Должно быть такое неравенство для несмещенной статистической процедуры. Если S связано с параметром так, что они согласованы, то, какую-то бы другую гипотезу ни взять, она будет хуже. Статистическая процедура на ней даст более плохой результат. Тогда она считается несмещенной. Несмещенность интересно проявляет себя в разных задачах.
Например, в сети Пирсона корреляций, применяя эту теорию аккуратно, оценив, что значит несмещенность, получается достаточно хорошо. Порождающие гипотезы надо по-настоящему проверять – строить оптимальный, равномерный и наиболее мощный тест, он существует. И мы можем гарантировать оптимальность полученного теста для множественной проверки гипотез. Но вот при таком условии: если а+b=1, положительно, это будет уровень ошибки первого рода, а это будет уровень ошибки второго рода. Характеристика теста вполне естественная, несмещенность для индивидуальных гипотез означает ровно это свойство.
Теперь вернемся к самому началу. Было выполнено много разных работ с разными корреляциями. Все они между собой очень интересно связаны, это работа Краскала. Оказывается, для нормального распределения между этими величинами, всеми корреляциями есть простая связь, что интересно – связь монотонная. Это означает, что если вы строите минимальное остовное дерево в одной сети, то точно таким же оно будет в другой сети, потому что процедура основана на упорядочивании. Отсеченный граф точно такой же, только надо выбрать другой порог, согласованный с этим. Planar Мaximally Filtered Graph – тоже, то есть по сути дела, сами по себе эти структуры никак не зависят от того, что мы выбрали другую меру связи. Однако если мы начнем применять статистическую процедуру – любую, даже самую примитивную,, мы увидим, что они совершенно разные – у этих статистических процедур разные качества, разные свойства, никакой связи между ними уже нет. Хорошо это или плохо? Оказалось, что хорошо.
Возьмем такую простую характеристику, как похожесть знаков. Это вероятность совпадения знаков случайной величины по отношению к среднему. Что касается, например, двух временных рядов на финансовом рынке, то это вообще естественная характеристика: были ли у них в этот момент доходности положительными, или отрицательными, или разнонаправленными. Совпадение знаков – это просто их движение: либо оба вверх, либо оба вниз. Для этой характеристики тоже с точки зрения условного риска и функции потери, подбора порождающих гипотез можно построить соответствующую оптимальную статистическую процедуру.
Небольшое введение: пока мы рассматривали только гауссовские равномерные распределения, но существует много разных других, и была бы интересна задача в более широком классе. Такой класс, естественно, известен – так называемые эллиптические распределения, постоянные на эллипсоидах. Там есть нормальные распределения (все зависит от функции G), но там есть и распределения Стьюдента. Чем они отличаются – вот у этого распределения тяжелые хвосты, тут даже может не быть каких-то моментов, начиная с некоторого места. аА у нормального распределения все хорошо, никаких тяжелых хвостов нет, и если рыночные доходности моделировать, то с тяжелыми хвостами встречаются, поэтому эта характеристика важна.
Основное утверждение, неожиданное для нас, оказалось такое: этот условный риск в сети, построенной на совпадении знаков, не зависит от распределения (лишь бы одна матрица сигма была), соответствующая статистическая процедура оказывается устойчивой (просто имеет одинаковые значения) и остается оптимальной. Если брать сеть корреляций Пирсона, то там построенная оптимальная статистическая процедура сразу перестает быть оптимальной при небольших отклонениях от гауссова распределения в сторону Стьюдента – это легко моделируется на графике.
И заодно доказали, что все связи между этими мерами, которые Краскал вывел для гауссовских распределений, в этом классе распределений тоже верны.
Что это дает? Во-первых, с нашей точки зрения, совпадение знаков становится привлекательной мерой близости для этих задач. Не зная распределения, у нас больше уверенность, что мы получим точный результат, из-за того, что получилась робастная статистическая процедура, вот та, которую мы построили, только о ней идет речь, оптимальная.
Куда двигаться? В идентификации графа концентраций мы тоже можем построить для аддитивной функции потерь (а я не знаю, почему в графе концентраций рассматривают только эти ошибки. Даже там, ну неужели важно, чтобы было – одно ребро не провели и вот, ошибка? Там так же важно, сколько ребер мы ошиблись, сколько неправильных связей добавилось, сколько исчезло). Оптимальная процедура имеет очень интересный, неожиданный вид – это так называемые структуры Неймана. Это означает, что в оптимальной процедуре при построении статистики мы должны учитывать значения всех наблюдений (хотя мы проверяли гипотезу для двух). В этой задаче проверка ноль или не ноль, проверяют всего частные корреляции, гипотезу о частных корреляциях двух случайных величин, но тест включает в себя значения всех остальных.
Другое интересное направление, что было замечено для этого отсеченного графа на реальных финансовых рынках: если распределение степеней вершин подчиняется степенному закону – да, при некоторых значениях порога, никто не знает, что это, но наблюдается. На логарифмической шкале какая-то такая связь. Дальше я бы выделил, что есть определенные предпочтения в порядке неопределенности между этими структурами, общее для всех. Еще одно явление было выявлено: что если брать ансамбль Вишера-Лагерра, то по теореме Пастура-Марченко при определенном соотношении между числом наблюдений и размерностью этой матрицы собственные значения попадают в интервал Там есть круговое распределение, закон этих собственных значений. А для этих матриц рынка, ковариационных и вариационных обнаружилось, что явление, которое отличает, как бы они выходят за рамки этой теории, то есть они чем-то отличаются – на всех практически рынках есть одно большое собственное значение, значительно превышающее все остальные. Оно одно выделяется, а дальше как бы все к этому интервалу начинают приближаться. Этому есть объяснение, есть такое понятие как индекс рынка. А что такое собственное значение, оно чему соотвествует – когда вы матрицу на транспонируемую умножаете, то первое собственное значение это будет первый фактор в методе главных компонент. И у вас в чистом виде выделяется так называемый индекс рынка – та характеристика, изменения которой связаны с изменениями всех остальных с достаточно большой точностью.
Мера совпадения знаков очень легко распространяется на 3, 4, 5 случайных величин, и мы уже можем строить гиперграф. Взвешенный гиперграф – когда вы берете вершины, любое подмножество вершин имеет весы. Легко этот вес вот это и будет общность их знаков, вероятность совпадения знаков этих вершин. Как только у вас такой гиперграф есть, известно, что из него можно сделать некоторое распределение Бернулли на этих вершинах. Смысл этого распределения мы пока не понимаем, но кажется, там будет что-то интересное. Это именно то, чем мы сейчас занимаемся.
Несколько публикаций на эту тему.
***
Коллоквиум факультета компьютерных наук ВШЭ – специальные семинары, на которые могут приходить не только студенты или сотрудники ФКН, но и все желающие. Их проводят учёные не только из Вышки, но и из других вузов и научных центров — МГУ, МФТИ, Математического института и института системного анализа РАН, MIT, Microsoft Research, Школы анализа данных Яндекса. Найти все прошедшие коллоквиумы можно здесь. По этой же ссылке можно будет и записаться на будущие занятия, когда начнётся новый учебный год.