Algebraic Models for Data and Knowledge Representation in Modern Database Management Systems

Full Text

ВВЕДЕНИЕ

В условиях стремительного роста объемов данных и развития методов анализа на основе искусственного интеллекта все более актуальной становится задача создания высокопроизводительных интеллектуальных систем хранения, обработки и извлечения знаний из больших массивов информации. Эффективное решение данной задачи требует новых подходов как в области архитектур баз данных, так и совершенствования математических моделей представления информации.

Согласно исследованиям Artificial Intelligence Index², в 2024 г. перспективными направлениями развития систем управления базами данных (СУБД) станут решения на базе облачных вычислений, интегрированные аналитические платформы, мультизначные и графовые модели данных. При этом особое внимание уделяется использованию технологий искусственного интеллекта в СУБД. Уже сегодня появляются гибридные когнитивно-реляционные и когнитивно-графовые СУБД, поддерживающие интеграцию моделей машинного обучения для расширенной аналитики данных.

Дальнейшее повышение производительности таких систем требует исследований в области формальных алгебраических моделей представления данных, оптимальных с точки зрения выражения алгоритмов интеллектуальной обработки в среде СУБД.

В частности, несмотря на то, что реляционная модель, являющаяся основой большинства существующих СУБД, обеспечивает эффективное хранение структурированных данных практически неограниченных объемов и высокую производительность операций по манипулированию этими данными, ее возможности по представлению знаний для целей интеллектуального анализа и машинного обучения ограничены. В связи с этим остро встает вопрос о разработке новых подходов для выражения алгоритмов искусственного интеллекта в среде СУБД на базе алгебраических моделей представления данных и знаний.

Таким образом, проблемой, на решение которой направлено данное исследование, является ограниченность существующих в СУБД реляционных и объектно-ориентированных моделей с точки зрения эффективной реализации алгоритмов машинного обучения на основе операторов языка SQL.

Исследование опирается на комплекс научных методов, включающий:

• анализ и систематизацию научной литературы по проблеме формального представления данных и знаний в интеллектуальных системах;
• алгебраический метод для разработки новых расширенных моделей в виде систем уравнений и операторов;
• имитационное моделирование для экспериментальной верификации разработанных методов в среде СУБД;
• сравнительный анализ для оценки эффективности предлагаемых решений и формулировки рекомендаций по их применению.

Практическая значимость результатов исследования определяется возможностью их использования в перспективных высокопроизводительных СУБД с поддержкой технологий искусственного интеллекта для решения задач интеллектуальной аналитики больших данных. Предложенный методологический аппарат позволяет расширить возможности таких систем в области машинного обучения на базе SQL.

ОСНОВНАЯ ЧАСТЬ

В настоящее время все большее распространение в прикладных областях получают методы анализа данных и искусственного интеллекта, основанные на аппарате машинного и глубокого обучения. Для эффективного применения таких методов требуются качественные массивы структурированных данных большого объема. В связи с этим возникает необходимость в высокопроизводительных системах хранения и обработки данных, способных решать задачи подготовки, трансформации, интеграции разнородной информации из многочисленных источников, а также организовывать эффективное взаимодействие с внешними библиотеками и фреймворками машинного обучения.

Алгебраические модели данных представляют собой математический аппарат для формализованного описания структур данных и операций над ними в системах управления базами данных (СУБД). Данные алгебраические модели базируются на теоретико-множественных конструкциях, позволяя представить данные в виде множеств различных математических объектов, таких как кортежи, сущности, объекты и отношения между ними.

Рассмотрим подробнее наиболее фундаментальные алгебраические модели представления данных.

1. Реляционная модель данных

Данная модель опирается на представление данных в виде множества кортежей, объединенных в отношения (таблицы). Формальное определение отношения имеет следующий вид:

R = {t₁, t₂, … , t_m} (1)

где t_i = (v₁, v₂, … , v_n) – кортеж отношения R состоящий из элементов v заранее определенных множеств значений D₁, D₂, … , D_n, соответствующих атрибутам отношения.

Таким образом, отношение представляет собой подмножество декартова произведения D₁ × D₂ × … × D_n.

Над множествами кортежей определены операции реляционной алгебры: объединение, пересечение, разность отношений, проекция, селекция, соединение. Данные операции позволяют формализовано манипулировать отношениями и получать из них необходимую информацию.

2. Модель «сущность–связь»

Данная модель представляет предметную область в виде совокупности взаимосвязанных сущностей и отношений. Формально модель «сущность–связь» можно представить следующим образом:

M = (E, R, A) (2)

где E = {e₁, e₂, … , e_k} – множество сущностей;

R = {r₁, r₂, … , r_m} – множество отношений;

A = {a₁, a₂, … , a_n} – множество атрибутов.

Каждая сущность e_i характеризуется набором атрибутов из множества A. Отношения r_j связывают между собой сущности E.

Также для формального описания модели «сущность–связь» широко используется алгебра Кодда, включающая базовые операции над множествами сущностей и отношений.

3. Объектно-ориентированная модель данных

В данной модели информация представляется в виде множества объектов O, являющихся экземплярами некоторого класса сущностей:

O = {o₁, o₂, … , o_l},

где каждый объект описывается кортежем вида:

o_i = (o_id_i, {a₁, … , a_m}, {M₁, … , M_n}), (3)

где o_id_i – идентификатор объекта;

{a₁, … , a_m} – значения атрибутов объекта;

{M₁, … , M_n} – методы, определенные для объекта данного класса.

Для формализации операций над объектами в объектно-ориентированной модели обычно используется алгебра объектов, например, алгебра COCOA, включающая такие операции как создание объекта, получение и изменение значений атрибутов, вызов методов объекта и др.

В академической литературе активно исследуются вопросы качества данных, оптимизации вычислений и интеграции моделей машинного обучения в системы управления данными.

В работе Y. Liu с соавт. [8] анализируется проблема несоответствия большого числа признаков и относительно небольшого количества примеров в данных, используемых для машинного обучения моделей в задачах разработки новых материалов.

Авторы рассматривают методы преодоления данной проблемы, такие как снижение размерности признаков, увеличение выборки и специальные алгоритмы обучения. Показано, что баланс между количеством данных и размерностью модели имеет большое значение. Предложен синергетический подход к управлению количеством данных с использованием предметных знаний о материалах.

W. Sun с соавт. [10] исследуют подходы к объединению этапов обработки данных и предсказания моделей в едином вычислительном процессе на GPU, что позволяет значительно ускорить конвейер машинного обучения за счет совместной оптимизации. Проведен анализ сложности и экспериментальная оценка на реальных данных и запросах.

S. Kläbe с соавт. [5] сравнивают производительность различных способов интеграции моделей машинного обучения в СУБД – с помощью реляционной алгебры, пользовательских функций и нативных операторов. Оценка на различных архитектурах моделей и данных показывает наилучшую масштабируемость при использовании нативного оператора ModelJoin, особенно на GPU.

В научной работе M.E. Schüle с соавт. [5] анализируется проблематика применения языка SQL и аппарата реляционной алгебры для выражения алгоритмов машинного обучения. Несмотря на эффективность современных систем управления базами данных в решении задач доступа и манипулирования данными, отмечается, что их реляционная модель представления данных создает определенные трудности для исследователей в области искусственного интеллекта при формулировке методов обучения нейронных сетей с использованием SQL.

Вместе с тем, авторы на основе проведенного в работе анализа делают вывод о том, что современные СУБД вполне эффективны для реализации алгоритмов машинного обучения, выраженных с использованием аппарата реляционной алгебры. Для преодоления ограничений, накладываемых реляционной моделью данных, в исследовании предлагается оригинальный подход к трансформации исходных данных в реляционное представление, пригодное для последующего обучения нейронных сетей непосредственно в среде СУБД с использованием SQL.

В исследовании описывается система базовых операций для трансформации данных, реализации процесса обучения и логического вывода компьютерных моделей на алгебре SQL-92, а также их аналоги с применением специализированных типов массивов данных. Кроме того, приводятся результаты сравнительного анализа производительности разработанных методов обучения и вывода моделей на основе типа данных «массив» и методов чисто реляционной обработки в SQL.

Проведенные в ходе исследования вычислительные эксперименты подтверждают обоснованность использования современных СУБД для эффективной реализации операций линейной алгебры, применяемых в алгоритмах глубокого обучения. При этом показано, что применение специализированных типов массивов данных обеспечивает более высокую производительность по сравнению с представлением матриц в виде отношений.

Dragos Constantin Popescu, Ioan Dumitrache [1] рассматривают представление знаний и логический вывод для киберфизических систем (далее – КФС). Важна интуитивная концептуализация поведения КФС и формализация рассматриваемых знаний. Среди задач отмечают: интеграцию распределенных данных КФС; масштабируемость языков; мультирезольютивность; согласование локальных и глобальных решений; поддержку гибридных подходов. Из-за неопределенности в КФС нужны нечеткие и нейросимвольные модели в дополнение к логическим.

Russ Harmer, Eugenia Oshurko и соавторы предлагают формализм SqPO для иерархий графов на основе графовых преобразований. Определяются понятия вытягивания и факторизации.

Рассматривается иерархия графов G и T, отображение f: G → T и правило переписывания r, которое задает расширение экземпляра L в G и ограничение экземпляра K в T с обновлением f.

Обсуждается реализация в ReGraph на Python, поддерживающей эффективное обновление иерархий графов.

В своей научной работе Iolo Jones, Jerry Swan, Jeffrey Giansiracus [3] констатируют наличие значимых достижений в области развития методов машинного обучения. Однако отмечается, что традиционно используемые в данной предметной области подходы зачастую носят характер «черного ящика», не позволяя однозначно объяснить и гарантировать корректность функционирования построенных на их основе интеллектуальных систем.

Данное обстоятельство послужило предпосылкой для усиления в последние годы внимания исследовательского сообщества к разработке моделей с заданными структурными ограничениями, призванными гарантировать обладание системами определенными свойствами и характеристиками, а также существенно облегчить интерпретацию и анализ их функционирования на базе имеющихся эмпирических данных.

Как отмечается в работе, использование структурных ограничений при построении компьютерных моделей обеспечивает следующие ключевые преимущества:

• наложение ограничений предметной области, повышающих общую интерпретируемость модели;
• повышение эффективности обучения за счет более корректной математической постановки решаемой задачи;
• увеличение робастности – устойчивости к возможным шумам и аномалиям в исходных данных;
• преодоление проблемы «проклятия размерности».

Авторами подчеркивается наличие устойчивой тенденции в сторону использования в современных исследованиях более строго ограниченных структурно моделей. Поскольку такие модели, как правило, конструируются путем композиции относительно простых базовых элементов, их структурные свойства могут быть описаны формально с использованием аппарата алгебраических соотношений.

Основой большинства современных СУБД является реляционная модель, представляющая данные в виде набора таблиц с кортежами, множественными связями и дополнительными условиями целостности, объектом манипулирования в которой служит отношение R, заданное как множество атрибутов A₁, … , A_n и множество строк-кортежей D, каждый из которых представляет запись фактов об определенном объекте предметной области, а значения атрибутов соответствуют различным характеристикам объекта, с помощью операторов реляционной алгебры, таких как объединение R ∪ S, пересечение R ∩ S, разность R − S, декартово произведение R × S, проекция πA₁, … , A_n(R), выборка σcondition(R) и соединение R ⋈ S, выполняется манипулирование данными для решения аналитических задач, однако возможности реляционной модели ограничены, что создает сложности при реализации алгоритмов машинного обучения.

Для преодоления данных ограничений Maximilian E. Schüle и др. предложили подход трансформации данных в реляционную модель, пригодную для обучения нейронных сетей в SQL с использованием базовых операций.

Представление моделей и данных в виде алгебраических структур позволяет формально описывать задачи машинного обучения и оптимизировать их решение за счет манипуляций этими структурами, например Iolo Jones и др. отмечают перспективность структурно ограниченных моделей, гарантирующих заданные свойства и повышающих интерпретируемость, поскольку их архитектура строится композицией простых модулей, что дает возможность алгебраически выразить структурные ограничения, как для конволюционной нейросети:

y = f(W₃σ(W₂φ(W₁x + b₁) + b₂) + b₃), (4)

где W_x – матрицы весов;

b_x – смещения;

φ и σ – функции активации.

Для ускорения конвейеров машинного обучения Wenbo Sun и др. [8] предложили объединение этапов обработки данных и предсказания модели на основе линейно-алгебраических преобразований реляционных запросов с использованием GPU: эксперименты показали выигрыш в производительности до 317× по сравнению с традиционным подходом.

Другое перспективное направление – использование нативных операторов для интеграции моделей в СУБД, в работе Steffen Kläbe с соавт. [7] обоснована оптимальность оператора ModelJoin:

Сравнение на CPU и GPU показало наилучшую производительность ModelJoin по сравнению с другими способами вызова моделей.

Таким образом, алгебраические модели данных и знаний открывают новые возможности для интеграции СУБД и машинного обучения, формальное представление архитектуры нейросетей, объединение этапов обработки и анализа данных путем алгебраических преобразований, использование специализированных операторов демонстрируют высокий потенциал, а дальнейшие исследования в области алгебраических моделей и оптимизации машинного обучения в СУБД открывают путь к созданию высокопроизводительных интеллектуальных систем аналитики.

Несмотря на то, что реляционная модель, являющаяся основой большинства существующих СУБД, обеспечивает эффективное хранение структурированных данных практически неограниченных объемов и высокую производительность операций по манипулированию этими данными, ее возможности по представлению знаний для целей интеллектуального анализа и машинного обучения ограничены.

В частности, отношения реляционной модели не позволяют непосредственно отобразить иерархические структуры данных, характерные для представления знаний, структуры графов и сетей, широко используемых в моделях искусственного интеллекта.

Кроме того, стандартные операторы SQL не ориентированы на выполнение сложных матричных вычислений, являющихся ключевыми в большинстве алгоритмов машинного обучения.

Обозначенные ограничения обуславливают необходимость разработки новых подходов для выражения алгоритмов и архитектур машинного обучения непосредственно в среде СУБД. Поскольку эволюционное развитие этих систем происходит в направлении все большей формализации и алгебраизации, перспективным представляется использование различных специализированных расширений реляционной, объектно-ориентированной и других моделей, позволяющих аналитически выразить ключевые структуры нейронных сетей и операции над ними.

Iolo Jones с соавторами [3] предлагают использовать аппарат алгебраических ограничений для описания архитектуры искусственных нейронных сетей, конструируемых на базе композиции простых модулей – отдельных математических преобразований над векторами входных данных. Действительно, основой большинства современных глубоких нейросетевых архитектур является конвейер последовательно применяемых линейных и нелинейных отображений, которые могут быть представлены в виде системы матричных уравнений:

y = f(W₃σ(W₂φ(W₁x + b₁) + b₂) + b₃), (5)

где x – входной вектор данных размерности n;

W₁ ∈ Rm × n, W₂ ∈ R_l × m, W₃ ∈ R_k × l – матрицы весовых коэффициентов;

b₁ ∈ Rm, b₂ ∈ R_l, b₃ ∈ R_k – векторы смещений;

φ: Rm → Rm, σ: R_l → R_l – функции нелинейных преобразований;

f: R_k → R_k – функция активации выходного слоя;

y ∈ R_k – выход нейронной сети.

Данное выражение формально определяет преобразование, осуществляемое многослойным персептроном при классификации входного вектора x. Алгебраическая запись позволяет выделить ключевые структурные элементы модели – линейные отображения на каждом слое в виде матричных произведений и последующие нелинейные преобразования для введения необходимой сложности.

Более того, накладывая дополнительные ограничения на матрицы W и функции φ, σ можно получать различные специальные архитектуры с заранее известными свойствами.

Например, для конволюционных нейронных сетей, широко используемых в компьютерном зрении, определяются сверточные матрицы специальной блочной структуры, позволяющие выделять из изображений признаки заданной формы. Рекуррентные нейронные сети для анализа временных рядов используют общие веса на различных временных шагах, что формализуется с помощью дополнительных индексов для матриц W.

Очевидно, что представление архитектур и алгоритмов машинного обучения в строгой математической форме открывает широкие возможности для их анализа и оптимизации непосредственно в среде СУБД на языке SQL с использованием аппарата реляционной алгебры.

Использование алгебраических моделей данных является важным направлением развития современных интеллектуальных систем на базе СУБД. Рассмотрим применение таких моделей на примере систем электронной коммерции, в табл. 1 далее представлены различные способы алгебраического представления данных и бизнес-логики в интернет-магазинах и на маркетплейсах с соответствующими формальными описаниями и примерами операций.

Таблица 1

Алгебраические модели в СУБД [Algebraic models in e-commerce systems]

Таким образом алгебраический подход позволяет гибко моделировать данные и логику в электронной коммерции с использованием формального математического аппарата теории множеств, отношений, графов, матриц и пр. Перспективы дальнейшего применения алгебраических моделей в интеллектуальных СУБД для бизнес-аналитики очень широки.

ВЫВОДЫ

Подводя итоги следует констатировать, что алгебраические модели данных и знаний имеют высокий потенциал в плане дальнейшей эволюции интеллектуальных систем управления базами данных, функционирующих на основе математического аппарата теории множеств, отношений, групп, полугрупп, гомоморфизмов и изоморфизмов.

Несмотря на то, что традиционная реляционная модель данных, базирующаяся на использовании декартовых произведений отношений, конъюнкций, дизъюнкций, импликаций и эквивалентностей, продемонстрировала свою эффективность в плане хранения и обработки значительных объемов структурированной информации, ее применимость для решения современных задач интеллектуального анализа данных и машинного обучения с использованием аппарата искусственных нейронных сетей может быть ограниченной.

ЗАКЛЮЧЕНИЕ

В этой связи алгебраический подход, активно разрабатываемый в последних научных исследованиях, может открыть возможности не только формализованного описания архитектур и алгоритмов глубокого обучения моделей посредством систем линейных и нелинейных матричных уравнений, но и их эффективной реализации, верификации и оптимизации непосредственно в среде СУБД на базе специализированных типов и структур данных в сочетании с соответствующими операторами их алгебраических преобразований.

About the authors

Ilia V. Kuchumov

Author for correspondence.
Email: Kuchumov.ilya@gmail.com

Head, Development Department

References

Supplementary files