Посмотрите на работу Lars Lumpe and Stefan Schmidt
"Patterns via Clustering as a Data Mining Tool". Это доклад на семинаре 8th Workshop FCA4AI, сделаннный на конференции ECAI-2020.
Труды семинара можно скачать с https://fca4ai.hse.ru/2020/
В этом докладе рассказывалось о применении кластерного анализа для дробления интервалов. Самое замечательное, что немцы тоже анализировали массив Wine Quality. Их результаты, кстати, хорошо согласованы с итогами применения системы, описанной во втором моем тексте о CPython библиотеке.
Исторически Вы правы, но на современном этапе я смотрю на вопрос о смысле алгебры более широко: есть класс функциональных моделей, задаваемых тождествами и квазитождествами (группа, кольцо, модуль, поле, ассоциативная алгебра, алгебра Ли и т.п.), нужно понять, каким образом построить все эти модели с помощью теоретико-категорных конструкций (прямые и обратные пределы, в частности, декартовы произведения, подмодели и гомоморфизмы) из простейших. Так возникают задача классификации конечных простых групп, структурная теория алгебр Ли и восстановление по алгебре соответствующей группы Ли.
Обратная задача — найти тождества (еще лучше, базис тождеств) для некоторого квазимногообразия функциональных моделей.
Например, системы полиномиальных уравнений после А.Гротендика заменяются на идеалы, для решения обратной задачи — нахождения базиса полиномиального идеала — применяется техника базисов Грёбнера.
Для дистрибутивных решеток можно добавить тождество дистрибутивности, для модулярных — квазитождество модулярности (впрочем, можно написать и некоторое эквивалентное ему тождество). Для дистрибутивных решеток есть теорема представления Биркгофа, как я писал раньше. Но замечательный факт — то, что можно дать конструкцию для любой решетки, причем она снабжает нас идеальным (с точки зрения современных процессоров) способом манипулирования с данными. Это и есть основное открытие проф. Рудольфа Вилле.
Последние Ваши вопросы я несовсем понимаю.
1) Есть специальные классы решеток: модулярные и дистрибутивные. Для них Кронекером и Биркгофом найдены конструктивные критерии (немодулярная решетка должна содержать пентагон N5, а недистрибутивная — или пентагон, или диамант M3).
2) Для многих классов решеток есть теоремы представления:
a) для Булевых алгебр — теорема Стоуна, что любая Б.А. изоморфна подалгебре множества всех подмножеств.
b) для дистрибутивных решеток — теорема Биркгофа, что она изоморна множеству идеалов в упорядоченном множестве.
c) для общих решеток — теорема Вилле, что она изоморфна решетки всех кандидатов.
Я не могу гарантировать, что у меня данные порождают какую-то специальную решетку, поэтому использую теорию Вилле (Анализ формальных понятий).
Существует класс полных решеток, использованный Д.Скоттом для описания денотационной семантики алгоритмов. Там возникает трансфинитная индукция. Но у меня все решетки конечны, так как я работаю с данными. загруженными в память компьютера.
Решетки — фундаментальное понятие в универсальной алгебре (более общее, чем алгебры или кольца). Возникло в трудах Кронекера как средство описания структуры подпространств векторных пространств над полями. Нижние полурешетки возникают как подалгебры некоторой алгебры (подгруппы в группе, подкольца в кольце, подполя в поле) с естественной операцией пересечения. Конструкция пересечения всех надалгебр для 2 подалгебр (описанная в моем предыдущем ответе) задает операцию порождения минимальной подалгебры, порожденной этими двумя слагаемыми. Например, для 2 прямых в многомерном пространстве — это плоскость, натянутая на эти прямые. Как Вы понимаете, простым объединением здесь не обойтись.
Хорошо, давайте я попробую объяснить:
1) Нижняя полурешетка — это множество X с идемпотентной x^x=x, коммутативной x^y=y^x и ассоциативной x^(y^z)=(x^y)^z бинарной операцией ^:XxX->X. Можете думать о ней как об операции пересечения (или даже лучше, о побитовом умножении на битовых строках фиксированной длины). Тогда она задает порядок x<=y <=> x^y=x ("Меньшее, пересечённое с большим, есть меньшее.").
Поэтому наибольший элемент (обычно обозначается 1) таков, что 1^x=x.
2) Решетка — это пара полурешеток на одном множестве, связанных тождествами поглощения (чтобы порядки, задаваемые разными полурешетками, совпадали). Второй порядок задается правилом: "Меньшее, объединенное с большим, есть большее.".
3) Утверждение на странице 16 действительно легкое: чтобы получить объединение (вторую операцию) для элементов a и b, нужно пересечь все элементы x, содержащие каждое из объединяемых элементов (a<=x)&(b<=x). Так как полурешетка конечна, то это пересечение можно вычислить в некотором (на самом деле, безразлично каком) порядке.
Подробности есть на Википедии. К моему сожалению, я не знаю, какую книжку Вам рекомендовать: если читаете по-английски, то найдите Davey&Priestley (там все с картинками). Русские (и переведенные на русский) книги слишком сложны для первоначального обучения. Успехов!
Скорее всего, Вы правы: мне стоило начать с объяснения теории.
Попробуйте перейти по ссылке на статью 4 из серии (там есть ссылки на статьи 1-3). Я полагаю, что правильный порядок для новичков: 3,4,2,1. Если же речь идет о применении программистами, то лучший порядок: 1,2,3,4 (по мере увеличения числа «ненужных математических формул»(с)).
Спасибо за комментарий, Вы все верно сформулировали.
Эту систему нужно рассматривать как интеллектуального помощника исследователя.
Эксперт привносит свое понимание предметной области. Например, у нас был успешный опыт взаимодействия с академиком РАН А.А.Зализняком. Он разработал систему палеографических признаков для письма по бересте в XI-XIII веках в Новгороде. Затем он потратил более 10 лет своей жизни, чтобы на основании берестяных грамот с известными датировками разработать таблицы, какому 20-летию какого века какие комбинации им придуманных признаков соответствуют. Так вот похожая система сделала рутинную переборную задачу вместо него за несколько часов!
Но мы опирались за гений Андрея Анатольевича. Так же с грибами (миколог сможет расширить список существенных признаков и/или значений) и виноделием.
В Америке года 3 назад начались спонсируемые DARPA исследования по XAI (eXplainable Artificial Intelligence). Там развиваются самые разные архитектуры нейросетей, туда привлекли проф. В.Н.Вапника (автора Support Vector Machine). Но эти системы не могут объяснить, почему они решили так (нейросетки, грубо говоря, объясняют это тем, что некоторая сложная функция от признаков преодолела порог, а SMV — что точка оказалась в нужной области пространства).
Западный аналог описываемого подхода — Индуктивное Логическое Программирование — но там все упирается в вычислительную сложность. Пока никто не понимает, как применить вероятностные алгоритмы. Я уверен, что по-другому справиться с комбинаторикой не получится.
Здесь же нам повезло, что проф. Рудольф Вилле придумал представление, на котором вероятностные алгоритмы строятся легко (используют регистровые операции CPU и GPGPU и еще параллелятся совсем без проблем!). При этом и математика оказалась достаточно простой, чтобы в ней можно было много чего доказать. Я написал консольную программу на C++, только ее невозможно было использовать. Теперь возникла идея связать алгоритмы с БД под MariaDB и опитонить систему.
Спасибо, Вы правы. Но Вы должны учитывать, что я един в двух лицах: и математик, разрабатывающий и исследующий алгоритмы, и программист, реализующий их в библиотеке. Надеюсь, что мои студенты присоединятся к программированию, для них Ваше замечание про Pandas будет полезно.
Вы правильно указали на следующий теоретический шаг: нужно одностадийный процесс нахождения причинно-следственных зависимостей уложить в (необязательно древовидную) систему представления знаний. Для Анализа Формальных Понятий этим занимались в Техническом Университете Дрездена (у проф. Бернарда Гантера и проф. Франца Баадера) с помощью логик описания (description logics). Но Бернарда пару лет назад отправили на пенсию. Я сам планирую двигаться в этом направлении.
Что касается сложности — это, к сожалению, неизбежно: мы используем или вероятностные алгоритмы (для которых я кое-что умею доказывать) или жадные алгоритмы (как в обучении деревьям решений, например). Но во втором случае мы получим неоптимальность, неустойчивость относительно расширения выборки и переобучение. Комитетное обучение (как пример, случайный лес) — попытка справиться с этими проблемами, но цена — потеря объяснямости. Более того, тут опять вылезают вероятностные алгоритмы.
Мне кажется, Вы излишне категоричны. Например, лауреат премии Тьюринга Ян ЛеКун учился у знаменитого логика Аврима Блюма. Иначе мы могли бы и не узнать ничего о замечательных сверточных нейросетях.
Я бы посоветовал обратиться к лекторам, которые поощряют у своих студентов соревновательный дух (и сами участвовали в них), при этом снабжают своих студентов достаточными теоретическими знаниями.
Наиболее яркий пример — д.ф.-м.н. проф. А.Г.Дьяконов (ВМК МГУ).
В следующем семестре почти наверняка можно будет смотреть его видеолекции (положительная сторона карантина). А сейчас я предлагаю найти и оценить его блог «Анализ малых данных». Своих студентов я к нему отправляю…
Наконец, затрону совсем частные вопросы:
1) С деревьями решений есть только два сходства: символьное представление гипотез о причинах и использование энтропийных принципов для дискретизании непрерывных признаков. Зато нет проблемы учета порядка появления признаков (во множестве все признаки равноправны!).
2) Я довольно часто сталкивался в своих демонстрациях с ситуацией, когда 50 правил для грибника хватало. Можно ли их уменьшить? Наверняка можно, но я этим не занимался. Так как проверятся включение одного подмножества признаков (фрагмента гипотезы о причине) в другое множество признаков (описание тестового примера), то запрограммировать жадный алгоритм минимизации числа гипотез (накрытие) легко. Но никто не может гарантировать, что будет получен глобальный минимум. А делать экспоненциальный алгоритм остовного дерева ради частной задачи не хочется совершенно.
3) Я использовал наивный подход к описанию грибов. Eсли привлечь знания из микологии, то, скорее всего, результаты будут улучшены. В обсуждаемой статье описано, как построить свое собственное кодирование, которое потом подсовывается универсальной машине обучения. Если есть интерес, вперед!
4) Еще более интересны эксперименты к непрерывными признаками (у меня качество вин). Я только недавно придумал, как с ними работать, но в любом случае машина обучения не изменяется.
Теперь отвечу по конкретным замечаниям:
1) Есть мои видеолекции для студентов (ссылка приведена в первой части работы). Диссертация — скорее знак того, что под этим лежит наука (с доказательтвами теорем и оценками параметров).
2) Сравнение с другими методами предполагает метрики. Если брать количественные (особенно, в областях с внутренними симметриями), боюсь, лучше сверточных сетей никто ничего не придумает. Аппроксиматоры будут лучше всех, они на это и нацелены! Если же ограничиться объясняемым ИИ Matt Turek. Explainable Artificial Intelligence (XAI), то все методы окажутся переборными (или вероятностными). Но, например, по вероятностным методам индуктивного логического программирования (ИЛП) за последние 5 лет нет ни одной работы в arXiv.org! Хотя наблюдается возврат интереса к классическому ИЛП: для JICAI2020 заказан большой обзорный доклад (черновой вариант можно найти на arXiv.org).
3) Метод является вероятностным расширением Анализа формальных понятий
Sébastien Ferré, Marianne Huchard, Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli.
Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing // Marquis
P., Papini O., Prade H. (eds) A Guided Tour of Artificial Intelligence Research. Vol. 2,
Springer, Cham, 2020, p. 411-445
Автор делал доклад на международном семинаре FCA4AI (проходившем в рамках JICAI2019 в Макао).
Спасибо за комментарий. Попробую объяснить. Начну со целей, планов и закончу реализацией.
1) Аудитория — программисты. Грузить их цепями Маркова и продвинутыми разделами комбинаторики не хотелось. Хочется составить план, следуя которому они смогут воспроизвести эксперименты и убедятся, что все работает.
2) План — переход от конкретики к деталям (по мере заинтересованности). Эта статья — вторая в серии. Первая (ссылка имеется в самом начале) — для людей, которые хотят все потрогать руками, но лезть в программирование не хочется. Вторая — для программистов, которые предпочтут приспособить библиотеку для своих нужд (и других массивов). Третья (когда будет готова) расскажет об алгоритмических следствиях математических теорем.
3) Реализация — описание реального запуска библиотеки на двух совсем разноплановых массивах данных.
Предлагается попробовать. Данные берутся из стандартного репозитория UCI. Кодирование описано (а кодирование грибов можно придумать и свое собственное). Исходники выложены на bitbucket (и, надеюсь, будут скоро выложены на savannah.nongnu.org).
Посмотрите на работу Lars Lumpe and Stefan Schmidt
"Patterns via Clustering as a Data Mining Tool". Это доклад на семинаре 8th Workshop FCA4AI, сделаннный на конференции ECAI-2020.
Труды семинара можно скачать с https://fca4ai.hse.ru/2020/
В этом докладе рассказывалось о применении кластерного анализа для дробления интервалов. Самое замечательное, что немцы тоже анализировали массив Wine Quality. Их результаты, кстати, хорошо согласованы с итогами применения системы, описанной во втором моем тексте о CPython библиотеке.
Исторически Вы правы, но на современном этапе я смотрю на вопрос о смысле алгебры более широко: есть класс функциональных моделей, задаваемых тождествами и квазитождествами (группа, кольцо, модуль, поле, ассоциативная алгебра, алгебра Ли и т.п.), нужно понять, каким образом построить все эти модели с помощью теоретико-категорных конструкций (прямые и обратные пределы, в частности, декартовы произведения, подмодели и гомоморфизмы) из простейших. Так возникают задача классификации конечных простых групп, структурная теория алгебр Ли и восстановление по алгебре соответствующей группы Ли.
Обратная задача — найти тождества (еще лучше, базис тождеств) для некоторого квазимногообразия функциональных моделей.
Например, системы полиномиальных уравнений после А.Гротендика заменяются на идеалы, для решения обратной задачи — нахождения базиса полиномиального идеала — применяется техника базисов Грёбнера.
Для дистрибутивных решеток можно добавить тождество дистрибутивности, для модулярных — квазитождество модулярности (впрочем, можно написать и некоторое эквивалентное ему тождество). Для дистрибутивных решеток есть теорема представления Биркгофа, как я писал раньше. Но замечательный факт — то, что можно дать конструкцию для любой решетки, причем она снабжает нас идеальным (с точки зрения современных процессоров) способом манипулирования с данными. Это и есть основное открытие проф. Рудольфа Вилле.
Последние Ваши вопросы я несовсем понимаю.
1) Есть специальные классы решеток: модулярные и дистрибутивные. Для них Кронекером и Биркгофом найдены конструктивные критерии (немодулярная решетка должна содержать пентагон N5, а недистрибутивная — или пентагон, или диамант M3).
2) Для многих классов решеток есть теоремы представления:
a) для Булевых алгебр — теорема Стоуна, что любая Б.А. изоморфна подалгебре множества всех подмножеств.
b) для дистрибутивных решеток — теорема Биркгофа, что она изоморна множеству идеалов в упорядоченном множестве.
c) для общих решеток — теорема Вилле, что она изоморфна решетки всех кандидатов.
Я не могу гарантировать, что у меня данные порождают какую-то специальную решетку, поэтому использую теорию Вилле (Анализ формальных понятий).
Существует класс полных решеток, использованный Д.Скоттом для описания денотационной семантики алгоритмов. Там возникает трансфинитная индукция. Но у меня все решетки конечны, так как я работаю с данными. загруженными в память компьютера.
Решетки — фундаментальное понятие в универсальной алгебре (более общее, чем алгебры или кольца). Возникло в трудах Кронекера как средство описания структуры подпространств векторных пространств над полями. Нижние полурешетки возникают как подалгебры некоторой алгебры (подгруппы в группе, подкольца в кольце, подполя в поле) с естественной операцией пересечения. Конструкция пересечения всех надалгебр для 2 подалгебр (описанная в моем предыдущем ответе) задает операцию порождения минимальной подалгебры, порожденной этими двумя слагаемыми. Например, для 2 прямых в многомерном пространстве — это плоскость, натянутая на эти прямые. Как Вы понимаете, простым объединением здесь не обойтись.
Хорошо, давайте я попробую объяснить:
1) Нижняя полурешетка — это множество X с идемпотентной x^x=x, коммутативной x^y=y^x и ассоциативной x^(y^z)=(x^y)^z бинарной операцией ^:XxX->X. Можете думать о ней как об операции пересечения (или даже лучше, о побитовом умножении на битовых строках фиксированной длины). Тогда она задает порядок x<=y <=> x^y=x ("Меньшее, пересечённое с большим, есть меньшее.").
Поэтому наибольший элемент (обычно обозначается 1) таков, что 1^x=x.
2) Решетка — это пара полурешеток на одном множестве, связанных тождествами поглощения (чтобы порядки, задаваемые разными полурешетками, совпадали). Второй порядок задается правилом: "Меньшее, объединенное с большим, есть большее.".
3) Утверждение на странице 16 действительно легкое: чтобы получить объединение (вторую операцию) для элементов a и b, нужно пересечь все элементы x, содержащие каждое из объединяемых элементов (a<=x)&(b<=x). Так как полурешетка конечна, то это пересечение можно вычислить в некотором (на самом деле, безразлично каком) порядке.
Подробности есть на Википедии. К моему сожалению, я не знаю, какую книжку Вам рекомендовать: если читаете по-английски, то найдите Davey&Priestley (там все с картинками). Русские (и переведенные на русский) книги слишком сложны для первоначального обучения. Успехов!
Попробуйте перейти по ссылке на статью 4 из серии (там есть ссылки на статьи 1-3). Я полагаю, что правильный порядок для новичков: 3,4,2,1. Если же речь идет о применении программистами, то лучший порядок: 1,2,3,4 (по мере увеличения числа «ненужных математических формул»(с)).
Эту систему нужно рассматривать как интеллектуального помощника исследователя.
Эксперт привносит свое понимание предметной области. Например, у нас был успешный опыт взаимодействия с академиком РАН А.А.Зализняком. Он разработал систему палеографических признаков для письма по бересте в XI-XIII веках в Новгороде. Затем он потратил более 10 лет своей жизни, чтобы на основании берестяных грамот с известными датировками разработать таблицы, какому 20-летию какого века какие комбинации им придуманных признаков соответствуют. Так вот похожая система сделала рутинную переборную задачу вместо него за несколько часов!
Но мы опирались за гений Андрея Анатольевича. Так же с грибами (миколог сможет расширить список существенных признаков и/или значений) и виноделием.
В Америке года 3 назад начались спонсируемые DARPA исследования по XAI (eXplainable Artificial Intelligence). Там развиваются самые разные архитектуры нейросетей, туда привлекли проф. В.Н.Вапника (автора Support Vector Machine). Но эти системы не могут объяснить, почему они решили так (нейросетки, грубо говоря, объясняют это тем, что некоторая сложная функция от признаков преодолела порог, а SMV — что точка оказалась в нужной области пространства).
Западный аналог описываемого подхода — Индуктивное Логическое Программирование — но там все упирается в вычислительную сложность. Пока никто не понимает, как применить вероятностные алгоритмы. Я уверен, что по-другому справиться с комбинаторикой не получится.
Здесь же нам повезло, что проф. Рудольф Вилле придумал представление, на котором вероятностные алгоритмы строятся легко (используют регистровые операции CPU и GPGPU и еще параллелятся совсем без проблем!). При этом и математика оказалась достаточно простой, чтобы в ней можно было много чего доказать. Я написал консольную программу на C++, только ее невозможно было использовать. Теперь возникла идея связать алгоритмы с БД под MariaDB и опитонить систему.
Вы правильно указали на следующий теоретический шаг: нужно одностадийный процесс нахождения причинно-следственных зависимостей уложить в (необязательно древовидную) систему представления знаний. Для Анализа Формальных Понятий этим занимались в Техническом Университете Дрездена (у проф. Бернарда Гантера и проф. Франца Баадера) с помощью логик описания (description logics). Но Бернарда пару лет назад отправили на пенсию. Я сам планирую двигаться в этом направлении.
Что касается сложности — это, к сожалению, неизбежно: мы используем или вероятностные алгоритмы (для которых я кое-что умею доказывать) или жадные алгоритмы (как в обучении деревьям решений, например). Но во втором случае мы получим неоптимальность, неустойчивость относительно расширения выборки и переобучение. Комитетное обучение (как пример, случайный лес) — попытка справиться с этими проблемами, но цена — потеря объяснямости. Более того, тут опять вылезают вероятностные алгоритмы.
Я бы посоветовал обратиться к лекторам, которые поощряют у своих студентов соревновательный дух (и сами участвовали в них), при этом снабжают своих студентов достаточными теоретическими знаниями.
Наиболее яркий пример — д.ф.-м.н. проф. А.Г.Дьяконов (ВМК МГУ).
В следующем семестре почти наверняка можно будет смотреть его видеолекции (положительная сторона карантина). А сейчас я предлагаю найти и оценить его блог «Анализ малых данных». Своих студентов я к нему отправляю…
1) С деревьями решений есть только два сходства: символьное представление гипотез о причинах и использование энтропийных принципов для дискретизании непрерывных признаков. Зато нет проблемы учета порядка появления признаков (во множестве все признаки равноправны!).
2) Я довольно часто сталкивался в своих демонстрациях с ситуацией, когда 50 правил для грибника хватало. Можно ли их уменьшить? Наверняка можно, но я этим не занимался. Так как проверятся включение одного подмножества признаков (фрагмента гипотезы о причине) в другое множество признаков (описание тестового примера), то запрограммировать жадный алгоритм минимизации числа гипотез (накрытие) легко. Но никто не может гарантировать, что будет получен глобальный минимум. А делать экспоненциальный алгоритм остовного дерева ради частной задачи не хочется совершенно.
3) Я использовал наивный подход к описанию грибов. Eсли привлечь знания из микологии, то, скорее всего, результаты будут улучшены. В обсуждаемой статье описано, как построить свое собственное кодирование, которое потом подсовывается универсальной машине обучения. Если есть интерес, вперед!
4) Еще более интересны эксперименты к непрерывными признаками (у меня качество вин). Я только недавно придумал, как с ними работать, но в любом случае машина обучения не изменяется.
1) Есть мои видеолекции для студентов (ссылка приведена в первой части работы). Диссертация — скорее знак того, что под этим лежит наука (с доказательтвами теорем и оценками параметров).
2) Сравнение с другими методами предполагает метрики. Если брать количественные (особенно, в областях с внутренними симметриями), боюсь, лучше сверточных сетей никто ничего не придумает. Аппроксиматоры будут лучше всех, они на это и нацелены! Если же ограничиться объясняемым ИИ Matt Turek. Explainable Artificial Intelligence (XAI), то все методы окажутся переборными (или вероятностными). Но, например, по вероятностным методам индуктивного логического программирования (ИЛП) за последние 5 лет нет ни одной работы в arXiv.org! Хотя наблюдается возврат интереса к классическому ИЛП: для JICAI2020 заказан большой обзорный доклад (черновой вариант можно найти на arXiv.org).
3) Метод является вероятностным расширением Анализа формальных понятий
Sébastien Ferré, Marianne Huchard, Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli.
Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing // Marquis
P., Papini O., Prade H. (eds) A Guided Tour of Artificial Intelligence Research. Vol. 2,
Springer, Cham, 2020, p. 411-445
Автор делал доклад на международном семинаре FCA4AI (проходившем в рамках JICAI2019 в Макао).
1) Аудитория — программисты. Грузить их цепями Маркова и продвинутыми разделами комбинаторики не хотелось. Хочется составить план, следуя которому они смогут воспроизвести эксперименты и убедятся, что все работает.
2) План — переход от конкретики к деталям (по мере заинтересованности). Эта статья — вторая в серии. Первая (ссылка имеется в самом начале) — для людей, которые хотят все потрогать руками, но лезть в программирование не хочется. Вторая — для программистов, которые предпочтут приспособить библиотеку для своих нужд (и других массивов). Третья (когда будет готова) расскажет об алгоритмических следствиях математических теорем.
3) Реализация — описание реального запуска библиотеки на двух совсем разноплановых массивах данных.
Предлагается попробовать. Данные берутся из стандартного репозитория UCI. Кодирование описано (а кодирование грибов можно придумать и свое собственное). Исходники выложены на bitbucket (и, надеюсь, будут скоро выложены на savannah.nongnu.org).