Если будут вопросы или что-то оч сложно, могу попробовать ответить и на «пальцах» объяснить, пишите в ЛС. В статьях авторы, бывает, немного «усложняют» некоторые вещи.
Перекрывающиеся сообщества (overlapping communities) это отдельная группа алгоритмов, я с ними знаком меньше, но слышал, что рекомендуют использовать BIGCLAM, а еще я читал недавно статью про DAOC и выглядел он интересно
Иерархическая кластеризация это другое направление, но, например, упомянутый в статье Louvain community detection algorithm, а также упомянутый выше DAOC умеют выделять иерархию. Они возвращают иерархию сообществ, начиная от ситуации где каждая вершина это сообщества и заканчивая конечной кластеризацией. Насколько иерархия получится «осмысленно» это конечно другой вопрос, но по логике, в примере с футболом они сами должны найти клуб, лигу и т.д., если мы построим, например, граф, где два игрока связаны, если они были на поле в одном матче, а вес ребра это число таких матчей. Но я не пробовал, это лишь гипотеза
На самом деле есть очень много интересных приложений Organizational Network Analysis. Мы хотим написать про это отдельную статью, но вот несколько вариантов применения.
Есть интересные приложения с точки зрения поиска бизнес конфликтов на основе анализа организационной сети, вот доклад на недавней конференции в ВШЭ про это: https://youtu.be/WjKRbFh9p8s
2. Моя вина — я во введении дал ссылку на статью про Normalized Mutual Information, но не пояснил, что далее буду использовать этот термин как NMI. Спасибо за замечание, сейчас поправлю!
Предельный частный случай кросс-валидации это Leave One Out, когда мы обучаемся на всех примерах, кроме одного и на последнем валидируемся; повторяем для каждого имеющегося примера и оцениваем среднюю ошибку.
«Классический» контр-пример тогда такой. Пусть имеется случайное распределение меток 1 или 0. Пусть у нас есть обучающая выборка. И мы «обучаем» следующий классификатор: классификатор предсказывает 1, если в обучающей выборке четное число примеров с меткой 1 и 0 в противном случае. Понятно, что ошибка на всех данных будет всегда 1/2, а вот оценка Leave One Out будет либо ровно 0, либо ровно 1, это нетрудно показать. Т.е. LOO — кросс-валидация «ломается» на таком примере. Хотя как я писал, пример явно искусственный, он не позволят делать какие-либо интересные выводы о кросс-валидации вообще.
Про то, насколько верны оценки на тестовой выборке: есть теорема (за пруфами в книгу http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/) о том, насколько отличаются разницы оценок на трэйн/тест и трэйн/все_данные _в_мире. Там эта штука быстро сходится, чтобы иметь 99% уверенности, что точность бинарной классификации будет отличаться не более чем на тысячные, хватит порядка 10000 наблюдений в тесте.
Есть контр-пример (очень искусственный, но все же), который показывает, что кросс валидация может "сломаться"). Пруфы в той же книге, там по оглавление легко найти.
Вообще для сравнения моделей в целом есть лучшие показатели — например, VC размерность. Ну и используя размерности такого типа можно, вообще говоря, сравнивать не качество двух моделей на трейне, а обобщающую способность.
В общем случае теория пока умеет доказывать лишь то, что качество модели от данных связано с размерностью VC. Когда данных становится больше, чем VC-размерность, то качество вообще и качество на трэйне начинают сходиться, скорость определяется опять же через VC, но там все оч сложно и за один комментарий такое не распишешь…
Пару лет уже пользуюсь мобильным приложением FastHub (https://github.com/k0shk0sh/FastHub) и это очень удобно, быстро что-то посмотреть, или ответить в переписке и т.д.
Так что кажется, они немного «запоздали» с выпуском «официальных» приложений. Хотя идея хорошая.
У любых альтернатив фантастические проблемы с ноутбуками-трансформерами. Поддерживаемых Linux-ом ноутов с тачем по пальцам пересчитать. А мне, например, нравится мой HP Envy 360 — и книжку почитать в самолете, и фильм на кровати посмотреть
Я слышал, что из всех ОС Windows оказывает самую лучшую поддержку для людей с ограниченными возможностями (проблемы по зрению, например)
Корпоративный софт типа Cisco и прочих заточен под Windows
Ну и еще большая кабальность для тех же Mac-ов (все эти истории с правом на ремонт, еще более короткие циклы поддержки, замедление старых устройств и т.д.) и очень плохая поддержка Linux-ов со стороны производителей устройств. В общем много причин на самом деле может быть.
Моя мысль была в том, что у поисковиков есть отлаженный и относительно работающий механизм удаления страниц из поисковой выдачи. Просто выше комментаторы писали, что это сложно сделать такую фильтрацию, что можно удалить что-то лишнее и т.д., поэтому я привел пример с фильмами, ведь следить за фильмами гораздо сложнее, чем за десятком популярных приложений. То есть механизм, процесс и опыт в решении подобных задач у них точно есть.
Но ведь выпиливать пиратские фильмы пачками и в полу-автоматическом режиме хорошо выходит что у гугла, что у яндекса:
Заголовок спойлера
При этом они не выпиливают обзоры на фильмы, рецензии, описания и т.д., т.е. фильтровать они могут. Что мешает использовать подобные механизмы в случае приложений? Там приложений то, которыми пользуются домохозяйки: мессенжеры да браузеры, список гораздо проще и меньше, чем список тех же фильмов.
Ну у меня оно на HP как раз падало по программе Windows Insider и я отправлял отчет)
Думаю я такой не один, учитывая популярность HP. Так что кажется проблема не в тестировании, а в том, что торопились просто.
Я не до конца понял про резистивные расстояния (точнее кажется там граф получится уж слишком плотным, а подбор порога это дело не тривиальное в этом случае), но мы делали подобные задачи так. Из теории информации мы знаем, что более частые события менее информативны. Если сравнить два мероприятия, на одном было 1000 людей, на другом 100, то кажется совместное посещение двумя участниками первого мероприятия говорит нам меньше, чем совместное посещение второго. Это можно учесть, например так: мы строим не просто граф, а взвешенный граф: сначала мы строим лист ребер для каждой связи участник-мероприятие; затем мы каждую такую связь «нормируем» на количество участников мероприятия (т.е. делим на нее, а еще лучше на логарифм этого количества). Получили таблицу вида: participant_id, event_id, weight. Дальше мы выполняем проекцию биграфа на участников (умножаем матрицу смежности на себя транспонированную), а по простому делаем join таблицы саму на себя с условием event_id_left = event_id_right и participant_id_left > participant_id_right. Операция тяжелая, но необходимая. Дальше получили таблицу вида: participant_1_id, participant_2_id, weight_1, weight_2. Суммируем веса weight_1 и weight_2. Далее объединяем все связи participant_1, participant_2 в одну (группировкой), также суммируя веса. Все, мы получили лист рёбер взвешенного графа участник-участник.
В Gephi, который вы используете есть возможность учесть веса при построении (раздел edge weight в оригинальной статье про их Force Atlas 2).
Обычно еще потом хорошо «проредить» граф по некоторому порогу веса ребер.
Мне трудно четко ответить на этот вопрос. Авторы пишут так: класс функций является EMX-обучаемым тогда и только тогда, когда выполняется континуум-гипотеза:
Our approach is to show that the EMX learnability F is captured by the cardinality of the continuum. In a nutshell, class F is EMX-learnable if and only if there are only finitely distinct cardinalities in the gap between the integers and the continuum.
Ну пример с сайта это пример EMX-обучения. Конечные подмножества это те, на которых мы обучаемся. Дальше они там приводят теорему, что из-за того, что мы в принципе не знаем распределение пользователей, посещающих сайт, то понять, является ли какой-то алгоритм EMX-обучаемым. То есть нет какого то показателя размерности, который отражал бы обучаемость.
На самом деле есть очень много интересных приложений Organizational Network Analysis. Мы хотим написать про это отдельную статью, но вот несколько вариантов применения.
Тема с сообществами имеет применение в т.н. Communities of Practice — есть известный кейс компании Halliburton, вот их публикация: http://www.cs.unibo.it/~ruffino/Letture%20SNA/Assessing%20and%20Improving%20CoPs%20with%20SNA.pdf
Есть интересные приложения с точки зрения поиска бизнес конфликтов на основе анализа организационной сети, вот доклад на недавней конференции в ВШЭ про это: https://youtu.be/WjKRbFh9p8s
«Классический» контр-пример тогда такой. Пусть имеется случайное распределение меток 1 или 0. Пусть у нас есть обучающая выборка. И мы «обучаем» следующий классификатор: классификатор предсказывает 1, если в обучающей выборке четное число примеров с меткой 1 и 0 в противном случае. Понятно, что ошибка на всех данных будет всегда 1/2, а вот оценка Leave One Out будет либо ровно 0, либо ровно 1, это нетрудно показать. Т.е. LOO — кросс-валидация «ломается» на таком примере. Хотя как я писал, пример явно искусственный, он не позволят делать какие-либо интересные выводы о кросс-валидации вообще.
P.S. Вообще тема с перестановками и разбиениями выборок максимально развита в диссертации К.В. Воронцова, но я лично не осилил(( Можете почитать, если интересно: www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%B0%D0%B1%D0%B0%D1%8F_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BA%D1%81%D0%B8%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0. Кажется что это строгое развитие Ваших идей.
Так что кажется, они немного «запоздали» с выпуском «официальных» приложений. Хотя идея хорошая.
Ну и еще большая кабальность для тех же Mac-ов (все эти истории с правом на ремонт, еще более короткие циклы поддержки, замедление старых устройств и т.д.) и очень плохая поддержка Linux-ов со стороны производителей устройств. В общем много причин на самом деле может быть.
При этом они не выпиливают обзоры на фильмы, рецензии, описания и т.д., т.е. фильтровать они могут. Что мешает использовать подобные механизмы в случае приложений? Там приложений то, которыми пользуются домохозяйки: мессенжеры да браузеры, список гораздо проще и меньше, чем список тех же фильмов.
Вот только тот, кто умеет в менеджеры пакетов скорее всего всегда отличит официальный сайт от поделки. В статье речь скорее про домохозяек.
Думаю я такой не один, учитывая популярность HP. Так что кажется проблема не в тестировании, а в том, что торопились просто.
В Gephi, который вы используете есть возможность учесть веса при построении (раздел edge weight в оригинальной статье про их Force Atlas 2).
Обычно еще потом хорошо «проредить» граф по некоторому порогу веса ребер.
Our approach is to show that the EMX learnability F is captured by the cardinality of the continuum. In a nutshell, class F is EMX-learnable if and only if there are only finitely distinct cardinalities in the gap between the integers and the continuum.
Ну пример с сайта это пример EMX-обучения. Конечные подмножества это те, на которых мы обучаемся. Дальше они там приводят теорему, что из-за того, что мы в принципе не знаем распределение пользователей, посещающих сайт, то понять, является ли какой-то алгоритм EMX-обучаемым. То есть нет какого то показателя размерности, который отражал бы обучаемость.
Написал обзор оригинальной работы (насколько я её понял): https://habr.com/ru/company/raiffeisenbank/blog/484306/