В предыдущей заметке автора был описан web-сервер для проведения экспериментов с ВКФ-методом машинного обучения, основанного на теории решеток. Как альтернатива использования web-сервера в настоящей заметке сделана попытка указать путь использования CPython-библиотеки напрямую. Мы воспроизведем рабочие сессии экспериментов с массивами Mushroom и Wine Quality из UCI репозитория данных для тестирования алгоритмов машинного обучения. Потом будут даны объяснения о форматах входных данных.
В статье описывается новая версия программы для машинного обучения, основанного на теории решеток. Главное достоинство этой версии — интерфейс для программистов на Python к эффективным алгоритмам, запрограммированным на языке C++.
Сегодня процедуры машинного обучения (такие как cверточные нейросети, cлучайные леса и машина опорных векторов) достигли очень высокого уровня, превосходя людей в распознавании речи, видео и изображений. Они, однако, не могут обеспечить аргументы, чтобы доказать корректность своих выводов.
С другой стороны, символьные подходы к машинному обучению (индуктивное логическое программирование, обучение покрытию с помощью целочисленного программирования) имеют доказуемо очень высокую сложность вычислений и практически неприменимы к выборками даже сравнительного небольшого объема.
Описанный здесь подход использует вероятностные алгоритмы, чтобы избежать этих проблем. ВКФ-метод машинного обучения использует технику современной алгебраической теории решеток (Анализ формальных понятий) и теории вероятностей (особенно, цепей Маркова). Но теперь Вам не потребуются знания продвинутой математики, чтобы использовать и создавать программы с помощью ВКФ-системы. Автор создал библиотеку (vkf.cp38-win32.pyd под Windows или vkf.cpython-38-x86_64-linux-gnu.so под Linux), чтобы обеспечить доступ к программе через понятный программистам на Python интерфейс.
Имеется родительский по отношению к описываемому подход — придуманный вначале 80-х годов XX века д.т.н. проф. В.К. Финном ДСМ-метод автоматического порождения гипотез. В настоящее время он превратился, как говорит его создатель, в метод автоматизированной поддержки научных исследований. Он позволяет использовать методы логики аргументации, проверять устойчивость найденных гипотез при расширении обучающей выборки, соединять вместе результаты предсказаний с помощью различных стратегий ДСМ-рассуждений.
К сожалению, автор настоящей заметки и его коллеги обнаружили и исследовали некоторые теоретические недостатки ДСМ-метода:
Исследования автора суммированы в главе 2 его диссертационной работы. Последний пункт обнаружен автором недавно, но, по его мнению, ставит крест на подходе с расширяющимися выборками.
Наконец, ДСМ-сообщество не предлагает доступ к исходным кодам своих систем. Более того, используемые языки программирования (Fort и C#) не позволят использовать их широкой публике. Единственный известный автору свободно распространяемый вариант ДСМ-решателя на С++ (авторства Т.А. Волковой robofreak) содержит досадную ошибку, которая иногда приводит к аварийному прекращению вычислений.
Первоначально автор планировал поделиться разработанным для системы «ВКФ-метод» кодировщиком с ДСМ-сообществом. Поэтому он все алгоритмы, одновременно применимые как к ДСМ-, так и к ВКФ-системам, вынес в отдельную библиотеку (vkfencoder.cp38-win32.pyd под Windows или vkfencoder.cpython-38-x86_64-linux-gnu.so под Linux). К сожалению, эти алгоритмы оказались невостребованными ДСМ-сообществом. В библиотеке «ВКФ» реализованы эти алгоритмы (например, класс vkf.FCA), но опираясь на заполнение таблиц не из файлов, а непосредственно через web-интерфейс. Здесь мы будем использовать библиотеку vkfencoder.
Будем предполагать, что у читателя умеется установленные MariaDB server + MariaDB Connector/C (по умолчанию используем IP-address 127.0.0.1:3306 и пользователя 'root' c паролем 'toor'). Начнем с установки библиотек vkfencoder и vkf в виртуальное окружение demo и с создания пустой базы данных под MariaDB под именем 'mushroom'.
По результатам работы возникнет БД 'mushroom', в папке ~/src/demo/lib/python3.8/site-packages/vkfencoder-1.0.3-py3.8-linux-x86_64.egg/
появится файл vkfencoder.cpython-38-x86_64-linux-gnu.soа, а в папке ~/src/demo/lib/python3.8/site-packages/vkf-2.0.1-py3.8-linux-x86_64.egg/
появится файл vkf.cpython-38-x86_64-linux-gnu.so
Запускаем Python3 и проводим ВКФ-эксперимент на массиве Mushrooms. Предполагается, что в папке ~/src/demo/files/ имеются 3 файла (mushrooms.xml, MUSHROOMS.train, MUSHROOMS.rest). Структура этих файлов будет описана в следующем параграфе. Первый файл 'mushrooms.xml' задает структуру нижней полурешетки на значениях каждого признака, описывающего грибы. Второй и третий файлы — поделенный датчиком случайных чисел примерно пополам файл 'agaricus-lepiota.data' — оцифрованная книга «Определитель грибов Северной Америки», изданной в Нью-Йорке в 1981 г. Встречающиеся дальше имена 'encoder', 'lattices', 'trains' и 'tests' являются именами таблиц в БД 'mushroom' для, соответственно, кодировок значений признаков битовыми подстроками, отношениями накрытия для диаграмм полурешеток на этих значениях, обучающих и тестовых примеров.
'e' в двух последних строчках соответствует съедобности гриба (так кодируется целевой признак в этом массиве).
Важно отметить, что имеется класс vkfencoder.XMLExport, который позволяет сохранить информацию из двух таблиц 'encoder' и 'lattices' в xml-файле, который после внесения изменений можно опять обработать классом vkfencoder.XMLImport.
Теперь переходим к собственно ВКФ-эксперименту: подключаем кодировщих, загружаем ранее подсчитанные гипотезы (если есть), вычисляем дополнительное число (100) гипотез в указанное число (4) потоков и сохраняем их в таблице 'vkfhyps'.
Можно получить Python-список всех нетривиальных пар (имя_признака, значение_признака) для ВКФ-гипотезы под номером ndx
Одна из гипотез для принятия решения о съедобности гриба имеет вид
Из-за вероятностного характера алгоритмов ВКФ-метода она может и не породиться, но автор доказал, что при достаточно большом числе порожденных ВКФ-гипотез возникнет очень похожая на нее гипотеза, которая почти также хорошо предскажет целевое свойство у важных тестовых примеров. Подробности — в главе 4 диссертационной работы автора.
Наконец, переходим к предсказанию. Создаем тестовую выборку для оценки качества порожденных гипотез и одновременно предсказываем целевое свойство у ее элементов
Класс vkfencoder.XMLImport анализирует XML-файл, описывающий порядок между значениями признаков, создает и заполняет две таблицы 'encoder' (преобразующую каждое значение в строку битов) и 'lattices' (хранящую соотношения между значениями одного признака).
Структура входного файла должна быть похожей на
Приведенный выше пример представляет упорядочение между значениями третьего признака ‘cap_color’ (цвет шляпки) для массива Mushrooms (Грибы) из Репозитория данных для машинного обучения (Университета Калифорнии в г. Ирвайн). Каждое поле ‘attribute’ представляет структуру решетки на значениях соответствующего признака. В нашем примере группа соответствует дискретному признаку ‘cap_color’. Список всех значений признака образует подгруппу . Мы добавили значение , чтобы обозначить тривиальное (отсутствующее) сходство. Остальные значения соответсвуют описанию в сопроводительном файле ‘agaricus-lepiota.names’.
Упорядоченность между ними представлена содержимым подгруппы . Каждая позиция описывает отношение “более частное/более общее” между парами значений признака. Например,, означает, что розовая шляпка гриба более специфичная, чем красная шляпка.
Автор доказал теорему о корректности представления, порождаемого конструктором класса vkfencoder.XMLImport и хранящегося в таблице 'encoder'. Его алгоритм и доказательство теоремы корректности использует современный раздел теории решеток, известный как Анализ формальных понятий. За подробностями читатель опять отсылается к диссертационной работе автора (глава 1).
Прежде всего следует отметить, что читатель может реализовать свой собственный загрузчик обучающих и тестовых примеров в БД или воспользоваться классом vkfencoder.DataImport, имеющимся в библиотеке. Во втором случае читатель должен учесть, что целевой признак должен находиться на первой позиции и состоять из одного символа (например, '+'/'-', '1'/'0' или 'e'/'p').
Обучающие выборка должна представлять собой CSV-файл (со значениями, разделенными запятыми), описывающий обучающие примеры и контр-примеры (примеры, не обладающие целевым свойством).
Структура входного файла должна быть похожа на
Здесь каждая строчка описывает один обучающий пример. Первая позиция содержит 'e' или 'p' в зависимости от съедобности/ядовитости описываемого гриба. Остальные позиции (разделенные запятыми) содержат буквы (краткие имена) или строки (полные названия значений соответствующего признака). Например, четвертая позиция соответствует признаку ‘cup_color’, где ‘g’, ‘p’, ‘y’, ‘b’ и ‘e’ обозначают “серый”, “розовый”, “желтый”, “песочный” и “красный”, соотвественно. Вопросительный знак в середине приведенной таблицы означает пропущенное значение. Впрочем, значения остальных (нецелевых) признаков могут быть строками. Важно заметить, что при сохранении в БД пробелы в их именах будут заменены на символы '_'.
Файл с тестовыми примерами имеет такой же вид, только системе не говорится о реальном знаке примера, а ее предсказание сравнивается с ним, чтобы вычислить качество порожденных гипотез и их предсказательную силу.
В этом случае опять возможны варианты: читатель может реализовать свой собственный загрузчик обучающих и тестовых примеров в БД или воспользоваться классом vkfencoder.DataLoad, имеющимся в библиотеке. Во втором случае читатель должен учесть, что целевой признак должен находиться на первой позиции и состоять из натурального числа (например, 0, 7, 15).
Обучающие выборка должна представлять собой CSV-файл (со значениями, разделенными каким-то разделителем), описывающий обучающие примеры и контр-примеры (примеры, не обладающие целевым свойством).
Структура входного файла должна быть похожа на
В нашем случае — это несколько первых строк файла 'vv_red.csv', порожденного из файла 'winequality-red.csv' красных португальских вин из массива Wine Quality данных UCI репозитория для тестирования процедкр машинного обучения путем перестановки последнего столбца в самое начало. Важно заметить, что при сохранении в БД пробелы в их именах будут заменены на символы '_'.
Как ранее писалось демонстрировать работу будем на массиве Wine Quality из репозитория UCI. Начнем с создания пустой базы данных под MariaDB под именем 'red_wine'.
По результатам работы возникнет БД 'red_wine'.
Запускаем Python3 и проводим ВКФ-эксперимент на массиве Wine Quality. Предполагается, что в папке ~/src/demo/files/ имеется файл vv_red.csv. Структура этих файлов была описана в предыдущем параграфе. Встречающиеся дальше имена 'verges', 'complex', 'trains' и 'tests' являются именами таблиц в БД 'red_wine' для, соответственно, порогов (как для исходных, так и для вычисляемых по регрессии признаков), коэффициентов значимых логистических регрессий между парами признаков, обучающих и тестовых примеров.
Второй аргумент задает порог (7 в нашем случае), при превышении которого пример объявляется положительным. Аргумент ';' соответствует разделителю (по умолчанию выбрана запятая ',').
Как указывалось в предыдущей заметке автора, порядок действий отличается от случая дискретных признаков. Сначала вычисляем логистические регрессии с помощью класса vkf.Join, коэффициенты которых сохраняются в таблице 'complex'.
Теперь с использованием теории информации вычисляем пороги с помощью класса vkf.Generator, которые вместе с максимумом и минимумом сохраняются в таблице 'verges'.
Пятый аргумент задает число порогов на исходных признаках. По умолчанию (и при значении, равном 0) он вычисляется как логарифм от числа признаков. На регрессиях ищется единственный порог.
Теперь переходим к собственно ВКФ-эксперименту: подключаем кодировщики, загружаем ранее подсчитанные гипотезы (если есть), вычисляем дополнительное число (300) гипотез в указанное число (8) потоков и сохраняем их в таблице 'vkfhyps'.
Можно получить Python-список троек (имя_признака, (нижняя_граница, верхняя_граница)) для ВКФ-гипотезы под номером ndx
Наконец, переходим к предсказанию. Создаем тестовую выборку для оценки качества порожденных гипотез и одновременно предсказываем целевое свойство у ее элементов
Так как у нас есть только один файл, то здесь мы в качестве тестовых примеров использовали обучающую выборку.
Автор использовал библиотеку aiofiles для загрузки файлов (таких как 'mushrooms.xml') на web-сервер. Вот фрагмент кода, могущий оказаться полезным
Библиотека vkf.cpython-38-x86_64-linux-gnu.so содержит много скрытых классов и алгоритмов. Они используют такие продвинутые математические понятия, как операции closed-by-one, ленивые вычисления, спаренные цепи Маркова, невозвратные состояния цепи Маркова, метрика тотальной вариации и др.
На практике эксперименты с массивами Репозитория данных для машинного обучения (Университет Калифорнии в г. Ирвайн) показали реальную применимость С++-программы ‘VKF Method’ к данным среднего размера (массив Adult содержит 32560 обучающих и 16280 тестовых примеров).
Система ‘VKF Method’ превзошла (относительно аккуратности предсказания) систему CLIP3 (Обучение покрытию с помощью целочисленного программитрования v.3) на массиве SPECT, где CLIP3 — программа, созданная авторами массива SPECT. На массиве Mushrooms (случайным образом разделенным на обучающую и тестовую выборки) система ‘VKF Method’ показала 100% аккуратность (как относительно критерия ядовитости грибов, так и относительно критерия съедобности). Программа была также применена к массиву Adult, чтобы породить более миллиона гипотез (без сбоев).
Исходные тексты CPython-библиотеки vkf находятся на премодерации на сайте savannah.nongnu.org. Коды для вспомогательной библиотеки vkfencoder можно забрать с Bitbucket.
Автор хотел бы поблагодарить своих коллег и учеников (Д.А. Анохина, Е.Д. Баранову, И.В. Никулина, Е.Ю. Сидорову, Л.А. Якимову) за поддержку, полезные обсуждения и совместные исследования. Впрочем, как обычно, за все имеющиеся недостатки ответственность несет исключительно автор.
Введение
В статье описывается новая версия программы для машинного обучения, основанного на теории решеток. Главное достоинство этой версии — интерфейс для программистов на Python к эффективным алгоритмам, запрограммированным на языке C++.
Сегодня процедуры машинного обучения (такие как cверточные нейросети, cлучайные леса и машина опорных векторов) достигли очень высокого уровня, превосходя людей в распознавании речи, видео и изображений. Они, однако, не могут обеспечить аргументы, чтобы доказать корректность своих выводов.
С другой стороны, символьные подходы к машинному обучению (индуктивное логическое программирование, обучение покрытию с помощью целочисленного программирования) имеют доказуемо очень высокую сложность вычислений и практически неприменимы к выборками даже сравнительного небольшого объема.
Описанный здесь подход использует вероятностные алгоритмы, чтобы избежать этих проблем. ВКФ-метод машинного обучения использует технику современной алгебраической теории решеток (Анализ формальных понятий) и теории вероятностей (особенно, цепей Маркова). Но теперь Вам не потребуются знания продвинутой математики, чтобы использовать и создавать программы с помощью ВКФ-системы. Автор создал библиотеку (vkf.cp38-win32.pyd под Windows или vkf.cpython-38-x86_64-linux-gnu.so под Linux), чтобы обеспечить доступ к программе через понятный программистам на Python интерфейс.
Имеется родительский по отношению к описываемому подход — придуманный вначале 80-х годов XX века д.т.н. проф. В.К. Финном ДСМ-метод автоматического порождения гипотез. В настоящее время он превратился, как говорит его создатель, в метод автоматизированной поддержки научных исследований. Он позволяет использовать методы логики аргументации, проверять устойчивость найденных гипотез при расширении обучающей выборки, соединять вместе результаты предсказаний с помощью различных стратегий ДСМ-рассуждений.
К сожалению, автор настоящей заметки и его коллеги обнаружили и исследовали некоторые теоретические недостатки ДСМ-метода:
- В худшем случае число порождаемых сходств может оказаться экспоненциально большим по сравнению с размером входных данных (обучающей выборкой).
- Задача обнаружения больших сходств является вычислительно (NP-)трудной.
- Переобучение неизбежно и наблюдается на практике.
- Обнаруживаются «фантомные» сходства обучающих примеров, каждый из которых обладает альтернативным кандидатом в причины целевого свойства.
- Вероятность обнаружения устойчивого сходства стремится к нулю при возрастании числа расширений исходной выборки.
Исследования автора суммированы в главе 2 его диссертационной работы. Последний пункт обнаружен автором недавно, но, по его мнению, ставит крест на подходе с расширяющимися выборками.
Наконец, ДСМ-сообщество не предлагает доступ к исходным кодам своих систем. Более того, используемые языки программирования (Fort и C#) не позволят использовать их широкой публике. Единственный известный автору свободно распространяемый вариант ДСМ-решателя на С++ (авторства Т.А. Волковой robofreak) содержит досадную ошибку, которая иногда приводит к аварийному прекращению вычислений.
Первоначально автор планировал поделиться разработанным для системы «ВКФ-метод» кодировщиком с ДСМ-сообществом. Поэтому он все алгоритмы, одновременно применимые как к ДСМ-, так и к ВКФ-системам, вынес в отдельную библиотеку (vkfencoder.cp38-win32.pyd под Windows или vkfencoder.cpython-38-x86_64-linux-gnu.so под Linux). К сожалению, эти алгоритмы оказались невостребованными ДСМ-сообществом. В библиотеке «ВКФ» реализованы эти алгоритмы (например, класс vkf.FCA), но опираясь на заполнение таблиц не из файлов, а непосредственно через web-интерфейс. Здесь мы будем использовать библиотеку vkfencoder.
1 Процедура работы с библиотекой для дискретных признаков
Будем предполагать, что у читателя умеется установленные MariaDB server + MariaDB Connector/C (по умолчанию используем IP-address 127.0.0.1:3306 и пользователя 'root' c паролем 'toor'). Начнем с установки библиотек vkfencoder и vkf в виртуальное окружение demo и с создания пустой базы данных под MariaDB под именем 'mushroom'.
krrguest@amd2700vii:~/src$ python3 -m venv demo
krrguest@amd2700vii:~/src$ source demo/bin/activate
(demo) krrguest@amd2700vii:~/src$ cd vkfencoder
(demo) krrguest@amd2700vii:~/src/vkfencoder$ python3 ./setup.py build
(demo) krrguest@amd2700vii:~/src/vkfencoder$ python3 ./setup.py install
(demo) krrguest@amd2700vii:~/src/vkfencoder$ cd ../vkf
(demo) krrguest@amd2700vii:~/src/vkf$ python3 ./setup.py build
(demo) krrguest@amd2700vii:~/src/vkf$ python3 ./setup.py install
(demo) krrguest@amd2700vii:~/src/vkf$ cd ../demo
(demo) krrguest@amd2700vii:~/src/demo$ mysql -u root -p
MariaDB [(none)]> CREATE DATABASE IF NOT EXISTS mushroom;
MariaDB [(none)]> exit;
По результатам работы возникнет БД 'mushroom', в папке ~/src/demo/lib/python3.8/site-packages/vkfencoder-1.0.3-py3.8-linux-x86_64.egg/
появится файл vkfencoder.cpython-38-x86_64-linux-gnu.soа, а в папке ~/src/demo/lib/python3.8/site-packages/vkf-2.0.1-py3.8-linux-x86_64.egg/
появится файл vkf.cpython-38-x86_64-linux-gnu.so
Запускаем Python3 и проводим ВКФ-эксперимент на массиве Mushrooms. Предполагается, что в папке ~/src/demo/files/ имеются 3 файла (mushrooms.xml, MUSHROOMS.train, MUSHROOMS.rest). Структура этих файлов будет описана в следующем параграфе. Первый файл 'mushrooms.xml' задает структуру нижней полурешетки на значениях каждого признака, описывающего грибы. Второй и третий файлы — поделенный датчиком случайных чисел примерно пополам файл 'agaricus-lepiota.data' — оцифрованная книга «Определитель грибов Северной Америки», изданной в Нью-Йорке в 1981 г. Встречающиеся дальше имена 'encoder', 'lattices', 'trains' и 'tests' являются именами таблиц в БД 'mushroom' для, соответственно, кодировок значений признаков битовыми подстроками, отношениями накрытия для диаграмм полурешеток на этих значениях, обучающих и тестовых примеров.
(demo) krrguest@amd2700vii:~/src/demo$ Python3
>>> import vkfencoder
>>> xml = vkfencoder.XMLImport('./files/mushrooms.xml', 'encoder', 'lattices', 'mushroom', '127.0.0.1', 'root', 'toor')
>>> trn = vkfencoder.DataImport('./files/MUSHROOMS.train', 'e', 'encoder', 'trains', 'mushroom', '127.0.0.1', 'root', 'toor')
>>> tst = vkfencoder.DataImport('./files/MUSHROOMS.rest', 'e', 'encoder', 'tests', 'mushroom', '127.0.0.1', 'root', 'toor')
'e' в двух последних строчках соответствует съедобности гриба (так кодируется целевой признак в этом массиве).
Важно отметить, что имеется класс vkfencoder.XMLExport, который позволяет сохранить информацию из двух таблиц 'encoder' и 'lattices' в xml-файле, который после внесения изменений можно опять обработать классом vkfencoder.XMLImport.
Теперь переходим к собственно ВКФ-эксперименту: подключаем кодировщих, загружаем ранее подсчитанные гипотезы (если есть), вычисляем дополнительное число (100) гипотез в указанное число (4) потоков и сохраняем их в таблице 'vkfhyps'.
>>> enc = vkf.Encoder('encoder', 'mushroom', '127.0.0.1', 'root', 'toor')
>>> ind = vkf.Induction()
>>> ind.load_discrete_hypotheses(enc, 'trains', 'vkfhyps', 'mushroom', '127.0.0.1', 'root', 'toor')
>>> ind.add_hypotheses(100, 4)
>>> ind.save_discrete_hypotheses(enc, 'vkfhyps', 'mushroom', '127.0.0.1', 'root', 'toor')
Можно получить Python-список всех нетривиальных пар (имя_признака, значение_признака) для ВКФ-гипотезы под номером ndx
>>> ind.show_discrete_hypothesis(enc, ndx)
Одна из гипотез для принятия решения о съедобности гриба имеет вид
[('gill_attachment', 'free'), ('gill_spacing', 'close'), ('gill_size', 'broad'), ('stalk_shape', 'enlarging'), ('stalk_surface_below_ring', 'scaly'), ('veil_type', 'partial'), ('veil_color', 'white'), ('ring_number', 'one'), ('ring_type', 'pendant')]
Из-за вероятностного характера алгоритмов ВКФ-метода она может и не породиться, но автор доказал, что при достаточно большом числе порожденных ВКФ-гипотез возникнет очень похожая на нее гипотеза, которая почти также хорошо предскажет целевое свойство у важных тестовых примеров. Подробности — в главе 4 диссертационной работы автора.
Наконец, переходим к предсказанию. Создаем тестовую выборку для оценки качества порожденных гипотез и одновременно предсказываем целевое свойство у ее элементов
>>> tes = vkf.TestSample(enc, ind, 'tests', 'mushroom', '127.0.0.1', 'root', 'toor')
>>> tes.correct_positive_cases()
>>> tes.correct_negative_cases()
>>> exit()
2 Описание структуры данных
2.1 Структуры решеток на дискретных признаках
Класс vkfencoder.XMLImport анализирует XML-файл, описывающий порядок между значениями признаков, создает и заполняет две таблицы 'encoder' (преобразующую каждое значение в строку битов) и 'lattices' (хранящую соотношения между значениями одного признака).
Структура входного файла должна быть похожей на
<?xml version="1.0"?>
<document name="mushrooms_db">
<attribute name="cap_color">
<vertices>
<node string="null" char='_'></node>
<node string="brown" char='n'></node>
<node string="buff" char='b'></node>
<node string="cinnamon" char='c'></node>
<node string="gray" char='g'></node>
<node string="green" char='r'></node>
<node string="pink" char='p'></node>
<node string="purple" char='u'></node>
<node string="red" char='e'></node>
<node string="white" char='w'></node>
<node string="yellow" char='y'></node>
</vertices>
<edges>
<arc source="brown" target="null"></arc>
<arc source="buff" target="brown"></arc>
<arc source="buff" target="yellow"></arc>
<arc source="cinnamon" target="brown"></arc>
<arc source="cinnamon" target="red"></arc>
<arc source="gray" target="null"></arc>
<arc source="green" target="null"></arc>
<arc source="pink" target="red"></arc>
<arc source="pink" target="white"></arc>
<arc source="purple" target="red"></arc>
<arc source="red" target="null"></arc>
<arc source="white" target="null"></arc>
<arc source="yellow" target="null"></arc>
</edges>
</attribute>
</document>
Приведенный выше пример представляет упорядочение между значениями третьего признака ‘cap_color’ (цвет шляпки) для массива Mushrooms (Грибы) из Репозитория данных для машинного обучения (Университета Калифорнии в г. Ирвайн). Каждое поле ‘attribute’ представляет структуру решетки на значениях соответствующего признака. В нашем примере группа соответствует дискретному признаку ‘cap_color’. Список всех значений признака образует подгруппу . Мы добавили значение , чтобы обозначить тривиальное (отсутствующее) сходство. Остальные значения соответсвуют описанию в сопроводительном файле ‘agaricus-lepiota.names’.
Упорядоченность между ними представлена содержимым подгруппы . Каждая позиция описывает отношение “более частное/более общее” между парами значений признака. Например,, означает, что розовая шляпка гриба более специфичная, чем красная шляпка.
Автор доказал теорему о корректности представления, порождаемого конструктором класса vkfencoder.XMLImport и хранящегося в таблице 'encoder'. Его алгоритм и доказательство теоремы корректности использует современный раздел теории решеток, известный как Анализ формальных понятий. За подробностями читатель опять отсылается к диссертационной работе автора (глава 1).
2.2 Структура выборок для дискретных признаков
Прежде всего следует отметить, что читатель может реализовать свой собственный загрузчик обучающих и тестовых примеров в БД или воспользоваться классом vkfencoder.DataImport, имеющимся в библиотеке. Во втором случае читатель должен учесть, что целевой признак должен находиться на первой позиции и состоять из одного символа (например, '+'/'-', '1'/'0' или 'e'/'p').
Обучающие выборка должна представлять собой CSV-файл (со значениями, разделенными запятыми), описывающий обучающие примеры и контр-примеры (примеры, не обладающие целевым свойством).
Структура входного файла должна быть похожа на
e,f,f,g,t,n,f,c,b,w,t,b,s,s,p,w,p,w,o,p,k,v,d
p,x,s,p,f,c,f,c,n,u,e,b,s,s,w,w,p,w,o,p,n,s,d
p,f,y,g,f,f,f,c,b,p,e,b,k,k,b,n,p,w,o,l,h,v,g
p,x,y,y,f,f,f,c,b,p,e,b,k,k,n,n,p,w,o,l,h,v,p
e,x,y,b,t,n,f,c,b,e,e,?,s,s,e,w,p,w,t,e,w,c,w
p,f,f,g,f,f,f,c,b,g,e,b,k,k,n,p,p,w,o,l,h,y,g
p,x,f,g,f,f,f,c,b,p,e,b,k,k,p,n,p,w,o,l,h,y,g
p,x,f,y,f,f,f,c,b,h,e,b,k,k,n,b,p,w,o,l,h,y,g
p,f,f,y,f,f,f,c,b,h,e,b,k,k,p,p,p,w,o,l,h,y,g
p,x,y,g,f,f,f,c,b,h,e,b,k,k,p,p,p,w,o,l,h,v,d
p,x,f,g,f,c,f,c,n,u,e,b,s,s,w,w,p,w,o,p,n,v,d
p,x,y,g,f,f,f,c,b,h,e,b,k,k,p,b,p,w,o,l,h,v,g
e,f,y,g,t,n,f,c,b,n,t,b,s,s,p,g,p,w,o,p,k,y,d
e,f,f,e,t,n,f,c,b,p,t,b,s,s,p,p,p,w,o,p,k,v,d
p,f,y,g,f,f,f,c,b,p,e,b,k,k,p,b,p,w,o,l,h,y,p
Здесь каждая строчка описывает один обучающий пример. Первая позиция содержит 'e' или 'p' в зависимости от съедобности/ядовитости описываемого гриба. Остальные позиции (разделенные запятыми) содержат буквы (краткие имена) или строки (полные названия значений соответствующего признака). Например, четвертая позиция соответствует признаку ‘cup_color’, где ‘g’, ‘p’, ‘y’, ‘b’ и ‘e’ обозначают “серый”, “розовый”, “желтый”, “песочный” и “красный”, соотвественно. Вопросительный знак в середине приведенной таблицы означает пропущенное значение. Впрочем, значения остальных (нецелевых) признаков могут быть строками. Важно заметить, что при сохранении в БД пробелы в их именах будут заменены на символы '_'.
Файл с тестовыми примерами имеет такой же вид, только системе не говорится о реальном знаке примера, а ее предсказание сравнивается с ним, чтобы вычислить качество порожденных гипотез и их предсказательную силу.
2.3 Структура выборок для непрерывных признаков
В этом случае опять возможны варианты: читатель может реализовать свой собственный загрузчик обучающих и тестовых примеров в БД или воспользоваться классом vkfencoder.DataLoad, имеющимся в библиотеке. Во втором случае читатель должен учесть, что целевой признак должен находиться на первой позиции и состоять из натурального числа (например, 0, 7, 15).
Обучающие выборка должна представлять собой CSV-файл (со значениями, разделенными каким-то разделителем), описывающий обучающие примеры и контр-примеры (примеры, не обладающие целевым свойством).
Структура входного файла должна быть похожа на
"quality";"fixed acidity";"volatile acidity";"citric acid";"residual sugar";"chlorides";"free sulfur dioxide";"total sulfur dioxide";"density";"pH";"sulphates";"alcohol"
5;7.4;0.7;0;1.9;0.076;11;34;0.9978;3.51;0.56;9.4
5;7.8;0.88;0;2.6;0.098;25;67;0.9968;3.2;0.68;9.8
5;7.8;0.76;0.04;2.3;0.092;15;54;0.997;3.26;0.65;9.8
6;11.2;0.28;0.56;1.9;0.075;17;60;0.998;3.16;0.58;9.8
5;7.4;0.7;0;1.9;0.076;11;34;0.9978;3.51;0.56;9.4
5;7.4;0.66;0;1.8;0.075;13;40;0.9978;3.51;0.56;9.4
5;7.9;0.6;0.06;1.6;0.069;15;59;0.9964;3.3;0.46;9.4
7;7.3;0.65;0;1.2;0.065;15;21;0.9946;3.39;0.47;10
7;7.8;0.58;0.02;2;0.073;9;18;0.9968;3.36;0.57;9.5В нашем случае — это несколько первых строк файла 'vv_red.csv', порожденного из файла 'winequality-red.csv' красных португальских вин из массива Wine Quality данных UCI репозитория для тестирования процедкр машинного обучения путем перестановки последнего столбца в самое начало. Важно заметить, что при сохранении в БД пробелы в их именах будут заменены на символы '_'.
3 ВКФ-эксперимент на примерах с непрерывными признаками
Как ранее писалось демонстрировать работу будем на массиве Wine Quality из репозитория UCI. Начнем с создания пустой базы данных под MariaDB под именем 'red_wine'.
(demo) krrguest@amd2700vii:~/src/demo$ mysql -u root -p
MariaDB [(none)]> CREATE DATABASE IF NOT EXISTS red_wine;
MariaDB [(none)]> exit;
По результатам работы возникнет БД 'red_wine'.
Запускаем Python3 и проводим ВКФ-эксперимент на массиве Wine Quality. Предполагается, что в папке ~/src/demo/files/ имеется файл vv_red.csv. Структура этих файлов была описана в предыдущем параграфе. Встречающиеся дальше имена 'verges', 'complex', 'trains' и 'tests' являются именами таблиц в БД 'red_wine' для, соответственно, порогов (как для исходных, так и для вычисляемых по регрессии признаков), коэффициентов значимых логистических регрессий между парами признаков, обучающих и тестовых примеров.
(demo) krrguest@amd2700vii:~/src/demo$ Python3
>>> import vkfencoder
>>> nam = vkfencoder.DataLoad('./files/vv_red.csv', 7, 'verges', 'trains', 'red_wine', ';', '127.0.0.1', 'root', 'toor')
Второй аргумент задает порог (7 в нашем случае), при превышении которого пример объявляется положительным. Аргумент ';' соответствует разделителю (по умолчанию выбрана запятая ',').
Как указывалось в предыдущей заметке автора, порядок действий отличается от случая дискретных признаков. Сначала вычисляем логистические регрессии с помощью класса vkf.Join, коэффициенты которых сохраняются в таблице 'complex'.
>>> join = vkf.Join('trains', 'red_wine', '127.0.0.1', 'root', 'toor')
>>> join.compute_save('complex', 'red_wine', '127.0.0.1', 'root', 'toor')
Теперь с использованием теории информации вычисляем пороги с помощью класса vkf.Generator, которые вместе с максимумом и минимумом сохраняются в таблице 'verges'.
>>> gen = vkf.Generator('complex', 'trains', 'verges', 'red_wine', 7, '127.0.0.1', 'root', 'toor')
Пятый аргумент задает число порогов на исходных признаках. По умолчанию (и при значении, равном 0) он вычисляется как логарифм от числа признаков. На регрессиях ищется единственный порог.
Теперь переходим к собственно ВКФ-эксперименту: подключаем кодировщики, загружаем ранее подсчитанные гипотезы (если есть), вычисляем дополнительное число (300) гипотез в указанное число (8) потоков и сохраняем их в таблице 'vkfhyps'.
>>> qual = vkf.Qualifier('verges', 'red_wine', '127.0.0.1', 'root', 'toor')
>>> beg = vkf.Beget('complex', 'red_wine', '127.0.0.1', 'root', 'toor')
>>> ind = vkf.Induction()
>>> ind.load_continuous_hypotheses(qual, beg, 'trains', 'vkfhyps', 'red_wine', '127.0.0.1', 'root', 'toor')
>>> ind.add_hypotheses(300, 8)
>>> ind.save_continuous_hypotheses(qual, 'vkfhyps', 'red_wine', '127.0.0.1', 'root', 'toor')
Можно получить Python-список троек (имя_признака, (нижняя_граница, верхняя_граница)) для ВКФ-гипотезы под номером ndx
>>> ind.show_continuous_hypothesis(enc, ndx)
Наконец, переходим к предсказанию. Создаем тестовую выборку для оценки качества порожденных гипотез и одновременно предсказываем целевое свойство у ее элементов
>>> tes = vkf.TestSample(qual, ind, beg, 'trains', 'red_wine', '127.0.0.1', 'root', 'toor')
>>> tes.correct_positive_cases()
>>> tes.correct_negative_cases()
>>> exit()
Так как у нас есть только один файл, то здесь мы в качестве тестовых примеров использовали обучающую выборку.
4. Замечание о загрузке файлов
Автор использовал библиотеку aiofiles для загрузки файлов (таких как 'mushrooms.xml') на web-сервер. Вот фрагмент кода, могущий оказаться полезным
import aiofiles
import os
import vkfencoder
async def write_file(path, body):
async with aiofiles.open(path, 'wb') as file_write:
await file_write.write(body)
file_write.close()
async def xml_upload(request):
#determine names of tables
encoder_table_name = request.form.get('encoder_table_name')
lattices_table_name = request.form.get('lattices_table_name')
#Create upload folder if doesn't exist
if not os.path.exists(Settings.UPLOAD_DIR):
os.makedirs(Settings.UPLOAD_DIR)
#Ensure a file was sent
upload_file = request.files.get('file_name')
if not upload_file:
return response.redirect("/?error=no_file")
#write the file to disk and redirect back to main
short_name = upload_file.name.split('/')[-1]
full_path = f"{Settings.UPLOAD_DIR}/{short_name}"
try:
await write_file(full_path, upload_file.body)
except Exception as exc:
return response.redirect('/?error='+ str(exc))
return response.redirect('/ask_data')
Заключение
Библиотека vkf.cpython-38-x86_64-linux-gnu.so содержит много скрытых классов и алгоритмов. Они используют такие продвинутые математические понятия, как операции closed-by-one, ленивые вычисления, спаренные цепи Маркова, невозвратные состояния цепи Маркова, метрика тотальной вариации и др.
На практике эксперименты с массивами Репозитория данных для машинного обучения (Университет Калифорнии в г. Ирвайн) показали реальную применимость С++-программы ‘VKF Method’ к данным среднего размера (массив Adult содержит 32560 обучающих и 16280 тестовых примеров).
Система ‘VKF Method’ превзошла (относительно аккуратности предсказания) систему CLIP3 (Обучение покрытию с помощью целочисленного программитрования v.3) на массиве SPECT, где CLIP3 — программа, созданная авторами массива SPECT. На массиве Mushrooms (случайным образом разделенным на обучающую и тестовую выборки) система ‘VKF Method’ показала 100% аккуратность (как относительно критерия ядовитости грибов, так и относительно критерия съедобности). Программа была также применена к массиву Adult, чтобы породить более миллиона гипотез (без сбоев).
Исходные тексты CPython-библиотеки vkf находятся на премодерации на сайте savannah.nongnu.org. Коды для вспомогательной библиотеки vkfencoder можно забрать с Bitbucket.
Автор хотел бы поблагодарить своих коллег и учеников (Д.А. Анохина, Е.Д. Баранову, И.В. Никулина, Е.Ю. Сидорову, Л.А. Якимову) за поддержку, полезные обсуждения и совместные исследования. Впрочем, как обычно, за все имеющиеся недостатки ответственность несет исключительно автор.
