Software & Systems

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

В свою очередь, при анализе данных, находящихся на распределенных узлах, приходится сталкиваться с такими проблемами, как приватность данных, ограничение пропускной способности каналов связи, обработка больших объемов информации и др. Для их решения была предложена концепция федеративного обучения (Federated Learning – FL) [1–3], которая предусматривает обучение без передачи данных от источников. Выделяют центра- лизованные и децентрализованные топологии FL, в которых возможны разные стратегии обучения: циклическое, федеративное и роевое.

Для реализации такого обучения хорошо подходят MAC. Состав агентов, их размеще- ние и взаимодействие могут зависеть от топологии и стратегии FL. МАС предоставляют возможность адаптации агентов с учетом этих условий.

Концепции МАС и FL имеют определенные формальные модели, каждая из которых описывает ее элементы, ресурсы и то, как она связана с окружающей средой. В данной статье описываются формальная модель МАС для FL и ее адаптация для реализации разных стратегий.

Формальная модель МАС

Формальное определение MAC можно представить в виде выражения, описывающего каждый из составляющих его элементов [4, 5]: MAS = {At, Et}, где At = {a1t, a2t, …, ant} – мно- жество всех агентов в MAC на момент времени t; Et = {Nt, Rt, ORGt, ACTt, COMt} – отношение агентов с окружающей средой на момент времени t; Nt = {n1t, n2t, …, njt} – множество всех узлов в MAC на момент времени t; RANt =  = At × Nt – отношение, описывающее размещение агентов множества А на узлах множества N, в момент времени t; ORGt – множество типов агентов в момент времени t (cостав зависит от прикладной задачи); ACTt = {ACT1t, ACT2t, …, ACTxt} – конечное множество действий, выполняемых различными типами агентов в MAC, в момент времени t (cостав зависит от прикладной задачи); COMt – коммуникативные действия, выполняемые между агентами, узлами и средой через ACL или протокол связи (cостав зависит от прикладной задачи).

Формальная модель FL

В случае размещения данных D = {d1, ..., dz} на разных узлах множества N для их анализа применяют два подхода [6, 7]:

-     распределенный анализ, предполагающий сбор всех наборов данных d = d1 È ... È dz вместе и использование объединенного набора d для обучения модели mDL алгоритмом α:  mDL = α(d);

-     FL, предполагающее построение модели mFL алгоритмом агрегации agg из моделей  m1, ..., mz, обученных алгоритмом α на данных d1, ..., dz, хранящихся на узлах без передачи их куда-либо (рис. 1): mFL = agg(m1, m2, …, mz), где m1 = α(d1), m2 = α(d2), …, mz = α(dz).

Так, FL эффективно, если точность mFL, обозначенная как A(mFL), очень близка к точности mDL, обозначенной как A(mDL): |A (mFL) –  A(mDL)| < d, где d – неотрицательное действительное число, обозначающее приемлемую потерю точности.

Таким образом, формально систему FL можно описать с помощью двух множеств:

-     множества клиентов, выполняющих алгоритм α на данных di и строящих модель  mi = α(di): C = {c1, ..., cz};

-     множества серверов, выполняющих агрегацию agg моделей agg(m1, m2, …, mz):

S = {s1, ..., sy}.

В зависимости от состава серверов, используемых для решения конкретной задачи, выделяют две топологии FL: централизованная (включает только один сервер: S = {s}) и децентрализованная (предполагает серверы на каждом узле с данными: S = {s1, ..., sz}, |S|=|D|).

Стратегия FL – это план обучения, который определяет, как модель обучается на клиентах и как организована связь между ними и/или сервером. В работе [8] выделены три типа стратегий: циклическая, федеративная, роевая (рис. 1). Циклическая модель обучается на каждом клиенте последовательно и передается следующему клиенту (в этом случае агрегирование модели не требуется). Федеративная модель обучается локально на каждом клиенте параллельно и агрегируется на сервере. Роевая модель обучается локально на каждом клиенте и распространяется по остальным клиентам, на каждом из которых выполняется агрегирование.

При выполнении FL выделяют 5 этапов [9].

Этап 1. Сбор информации о среде (опционально) – для пользователя собирается информация о данных, узлах, на которых они размещены, и т.п.

Этап 2. Постановка задачи – пользователь указывает, какие данные должны быть проанализированы, каким алгоритмом, с какими параметрами и т.п.

Этап 3. Рассылка модели (опционально, если обучение осуществляется параллельно на разных узлах) – передается модель на каждый из узлов с данными.

Этап 4. Обучение – на каждом из узлов выполняется обучение на локальных данных, на которых они размещаются.

Этап 5. Агрегация (опционально, если обучение осуществляется параллельно на разных узлах) – объединяются модели, обученные на каждом узле.

Формальная модель МАС для FL

Традиционно рассматривают два варианта применения МАС к машинному обучению [10]:

-     параллельная работа нескольких агентов, когда агенты обучают локальные модели на данных и передают их агенту-мастеру для объединения;

-     последовательная работа одного агента, когда он перемещается от источника к источнику, дообучая модель на каждом из узлов.

Стратегии обучения иллюстрирует рисунок 2.

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

Поведение каждого агента определяется выполнением различных задач в соответствии с определенной ролью. Среди основных задач FL можно выделить сбор информации о среде выполнения, обучение модели алгоритмом α(d), объединение моделей функцией агрегации agg(m1, m2, …, mz).

Уточним некоторые сущности в формальной модели МАС для FL [11].

Множество ролей:

ORG = {UA, FA, TA, DMA, DA, AA}, где

-     агент пользователя (UA – User Agent) взаимодействует с пользователем и принимает от него задачу на обучение: UA = {ua};

-     агент-посредник (FA – Facilitator Agent) собирает информацию о среде выполнения: FA = {fa};

-     агент задачи (TA – Task Agent) координирует работу всех агентов для выполнения задачи пользователя: TA = {ta};

-     агенты интеллектуального анализа данных (DMA – Data Mining Agent) выполняют алгоритм обучения на данных: DMA = {dma1, dma2, …, dmaz};

-     агент данных (DA – Data Agent) взаимодействует с данными: DA = {da1, da2, …, daz};

-     агент агрегации (AA – Aggregate Agent) объединяет модели: AA = {aa}.

·     Конечное множество действий, выполняемых каждым типом агента, в момент времени t:

ACTt = {ACTUAt, ACTFAt, ACTTAt, ACTDMAt, ACTDAt, ACTAAt}, где

ACTUAt = {r_query, c_task, s_task} – действия агента UA, где r_query – получить запрос пользователя; c_task – интерпретировать запрос пользователя в задачу для агента; s_task – передать задачу агентам;

ACTFAt = {a_agent, req_info, r_info, s_info} – действия агента FA, где a_agent – зарегистрировать агентов; req_info – запросить информацию о данных на каждом клиенте; r_info – получить информацию о данных с каждого клиента; s_info – передать информацию о данных на клиентах среды;

ACTTAt = {r_task, r_info, c_plan, s_plan} – действия агента ТА, где r_task – получить  задачу пользователя; r_info – получить информацию о данных с каждого из узлов; c_plan – запланировать работу по выполнению обучения; s_plan – отправить план обучения;

ACTDMAt = {r_plan, req_data, c_ α, s_models} – действие агента DMA, где r_plan – получить план выполнения; req_data – запросить данные; с_α – выполнить алгоритм интеллектуального анализа данных, используя значения, содержащиеся в запросе; s_models – отправить обученную модель для агрегирования;

ACTDAt = {r_info, r_data, s_info, s_data} – действия агента DA, где r_info – получить запрос на информацию о данных; r_data – получить запрос на доступ к данным; s_info – поддерживать информацию метаданных об источнике данных; s_data – передать доступ к данным;

ACTAAt = {r_model, a_models, s_models} – действия, выполняемые агентами AA, где r_model – получить модель; a_models – агрегировать полученные модели; s_models – отправить агрегированные модели.

·     Сообщения, которые перемещаются между агентами по протоколу ACL [11]:

COMt = {task, qinfo, info, plan, qdata, data, model}, где task – задача пользователя; qinfo – запрос информации о клиенте; info – информация о данных на клиенте; plan – план выполнения задачи; qdata – запрос на доступ к данным; data – доступ к данным; model – обученная модель.

Конфигурации МАС для стратегий FL

Выполнение FL начинается, когда UA получает задачу от пользователя, интерпретирует ее и передает (task) TA. Параллельно FA запрашивает информацию от DA о данных, доступных на узлах, и тоже передает эту информацию (info) TA. Таким образом, ТА получает всю информацию, необходимую для выполнения FL: задачу пользователя и информацию о среде, в которой выполняется анализ. На основе этой информации TA генерирует план (plan) выполнения FL.

После этого в зависимости от используемой стратегии будут выполнены разные действия.

В циклической стратегии (рис. 3) сгенерированный план (plan) передается для выполнения DMA. Он, получив план, обращается к DA (qdata) и с его помощью получает доступ к данным (data). Используя эти данные, DMA обучает модель (model). На следующем узле эта модель дообучается.

Таким образом, не требуется агрегация моделей и, следовательно, множество типов агентов не будут включать в себя AA [11]:

ORGtseq = {UA, FA, TA, DMA, DA}.

Возможны два варианта циклической стратегии:

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

DMAtseq_mob = {dma},

RtANseq_mob = {< (ua, fa, ta), n1>, , , …, } Ì At × Nt,

COMtseq_mob = COMt / {model},

ACT tseq_mob = ACT t / {ACTAAt},

ACTDMAt = {r_plan, req_data, c_α} – действие агента DMA, где r_plan – получить план выполнения; req_data – запросить данные; с_α – выполнить алгоритм интеллектуального анализа данных, используя значения, содержащиеся в запросе;

-     использование стационарных агентов DMA на каждом из узлов, которые по очереди будут передавать модель друг другу:

DMAtseq_st = {dma1, dma2, …, dman},

RtANseq_st = {< (ua, fa, ta), ns>, , …, , , …, } Ì At × Nt,

COMtseq_st = COMt, ACT tseq_st =  = ACT t / {ACTAAt}.

В случае с федеративной стратегией сгенерированный план (plan) передается для исполнения AA и DMA. Каждый DMA, получив план, обращается к DA за данными (qdata) и с его помощью получает доступ к данным (data). На этих данных DMA обучает модель (model) и передает ее AA. После получения от DMA всех моделей AA объединяет их и возвращает DMA. Обмен между AA и DMA осуществляется до завершения обучения (рис. 4). Таким образом, элементы среды имеют следующий вид:

ORGtfed = {UA, FA, TA, DMA, AA, DA},

DMAtfed = {dma1, dma2, …, dman},

RtANfed = {<(ua, fa, ta, aa), ns>, , …, , , …, } Ì At × Nt,

COMtfed = COMt, ACT tfed = ACT t.

В случае роевой стратегии на главном сервере (с которым взаимодействует пользователь) размещаются все типы агентов. Сгенерированный план (plan) передается для исполнения в AA и DMA, которые размещаются на каждом из узлов. Каждый DMA, получив план, обращается (qdata) к DA и с его помощью получает доступ к данным (data). На этих данных DMA обучает модель (model) и передает ее всем AA. После получения моделей от всех DMA каждый AA объединяет их и возвращает локальному DMA. Обмен между AA и DMA осуществляется до завершения обучения (рис. 5).

ORGtswarm = {UA, FA, TA, DMA, AA, DA},

DMAtswarm = {dma1, dma2, …, dman},

AAtswarm = {aa1, aa2, …, aan},

RtANswarm = {< (ua, fa, ta), ns>,

, …, , , …, , , …, } ⸦ At × Nt,

COMtswarm  = COMt, ACT tswarm = ACT t.

Заключение

Исследование позволило определить формальную модель MAC для FL. В модели выделены основные типы агентов, их действия и сообщения, которыми они обмениваются. Определение предложенных агентов позволило понять, как будут осуществляться коммуникация и координация в MAC для разных стратегий FL.

Анализ, проведенный на основе построенной формальной модели МАС_FL для разных стратегий FL, показал, что в зависимости от выбранной топологии и стратегии FL состав множеств модели МАС меняется несущественно. Для федеративной и роевой стратегий добавляется тип агента AA, выполняющий  агрегацию моделей. При этом протокол взаимодействия для всех стратегий остается неизменным, за исключением последовательного обучения, при котором не требуется передача модели (model).

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

Литература

1.    McMahan H.B., Moore E., Ramage D., Hampson S., Arcas B.A. Communication-efficient learning of deep networks from decentralized data. AISTATS, 2017, pp. 1273–1282.

2.    Li L., Fan Y., Tse M., Lin K.Y. A review of applications in federated learning. Computers & Industrial Engineering, 2020, vol. 149, art. 106854. DOI: 10.1016/j.cie.2020.106854.

3.    Li Q., Wen Z., Wu Z., Hu S., Wang N., Li Y., Liu X. et al. A Survey on federated learning systems: Vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021, p. 1. DOI: 10.1109/TKDE.2021.3124599.

4.    Яровой С.В. Имитационное моделирование распределенных динамических процессов на поверхности земли на основе агентного подхода: автореф. дис. Красноярск: СибГУ им. М.Ф. Решетнева, 2019. 23 с.

5.    Душутина Е., Столяренко Ю.А. Формальная модель временного обязательства в многоагентных системах реального времени // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2013. № 2. С. 9–16.

6.    Yang Q., Liu Y., Chen T., Tong Y. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 2019, vol. 10, no. 2, pp. 1–19. DOI: 10.1145/3298981.

7.    Kholod I., Yanaki E., Fomichev D., Shalugin E., Novikova E., Filippov E., Nordlund M. Open-source federated learning frameworks for IoT: A comparative review and analysis. Sensors, 2021, vol. 21, no. 1,  art. 167. DOI: 10.3390/s21010167.

8.    Rieke N., Hancox J., Li W., Milletari F., Roth H., Albarqouni Sh. et al. The future of digital health with federated learning. npj Digit. Med., 2020, vol. 3, art. 119. DOI: 10.1038/s41746-020-00323-1.

9.    Kairouz P., Mcmahan B.H., Avent B. et al. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 2021, vol. 14, no. 1-2, pp. 1–210. DOI: 10.1561/2200000083.

10. Юлейси П.Г., Холод И.И. Анализ многоагентных систем для анализа данных // XXIII Междунар. конф. по мягким вычислениям и измерениям. 2020. Т. 1. С. 273–276.

11. Yuleisy P.G., Kholod I.I. Protocol for the interaction of agents solving the problem of distributed data analysis. Proc. 2021 II Int. Conf. NeuroNT, 2021, pp. 47–50. DOI: 10.1109/NeuroNT53022.2021.9472793.

References

1. McMahan H.B., Moore E., Ramage D., Hampson S., Arcas B.A. Communication-efficient learning of deep networks from decentralized data. AISTATS, 2017, pp. 1273–1282.
2. Li L., Fan Y., Tse M., Lin K.Y. A review of applications in federated learning. Computers & Industrial Engineering, 2020, vol. 149, art. 106854. DOI: 10.1016/j.cie.2020.106854.
3. Li Q., Wen Z., Wu Z., Hu S., Wang N., Li Y., Liu X. et al. A Survey on federated learning systems: Vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021, p. 1. DOI: 10.1109/TKDE.2021.3124599.
4. Yarovoy S.V. Simulation Modeling of Distributed Dynamic Processes on the Earth's Surface Based on the Agent-Based Approach. Ph.D. Thes., Krasnoyarsk, Reshetnev Siberian State University of Science and Technology, 2019, 23 p. (in Russ.).
5. Dushutina E., Stolyarenko Yu.A. Formal model of time commitment in multi-agent real-time systems. St. Petersburg Polytech. Univ. J. Computer Science. Telecommunication and Control Systems, 2013, vol. 2, pp. 9–16 (in Russ.).
6. Yang Q., Liu Y., Chen T., Tong Y. Federated machine learning: Concept and applications. ACM Trans. on Intelligent Systems and Technology, 2019, vol. 10, no. 2, pp. 1–19. DOI: 10.1145/3298981.
7. Kholod I., Yanaki E., Fomichev D., Shalugin E., Novikova E., Filippov E., Nordlund M. Open-source federated learning frameworks for IoT: A comparative review and analysis. Sensors, 2021, vol. 21, no. 1, art. 167. DOI: 10.3390/s21010167.
8. Rieke N., Hancox J., Li W., Milletari F., Roth H., Albarqouni Sh. et al. The future of digital health with federated learning. npj Digit. Med., 2020, vol. 3, art. 119. DOI: 10.1038/s41746-020-00323-1.
9. Kairouz P., Mcmahan B.H., Avent B. et al. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 2021, vol. 14, no. 1-2, pp. 1–210. DOI: 10.1561/2200000083.
10. Yuleisy P.G., Kholod I.I. Analysis of multiagent system for data analysis. Proc. XXIII Int. Conf. SCM, 2020, vol. 1, pp. 273–276 (in Russ.).
11. Yuleisy P.G., Kholod I.I. Protocol for the interaction of agents solving the problem of distributed data analysis. Proc. 2021 2nd Int. Conf. NeuroNT, 2021, pp. 47–50. DOI: 10.1109/NeuroNT53022.2021.9472793.