Horizontal and Vertical Scalability of Machine Learning Methods
The main stages of Machine Learning Pipelines are considered in the paper, such as: train data collection and storage, training and scoring. The effect of the Big Data phenomenon on each of the stages is discussed. Different approaches to efficient organization of computation are on each of the stag...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/361 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-361 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/b3/cbbf5943f0d93849438582247de9f6b3.pdf |
| spelling |
pp_isofts_kiev_ua-article-3612024-04-28T11:02:47Z Horizontal and Vertical Scalability of Machine Learning Methods Горизонтальное и вертикальное масштабирование методов машинного обучения Горизонтальне та вертикальне масштабування методів машинного навчання Biletskyy, B.O. machine learning; pattern recognition; horizontal scalability; vertical scalability; relational databases; ACID; NoSQL; CAP-theorem UDC 004.62 машинное обучение; распознавание образов; горизонтальное масштабирование; вертикальное масштабирование; реляционные базы данных; ACID; NoSQL; CAP-теорема УДК 004.62 методи машинного навчання; розпізнавання образів; горизонтальне масштабування; вертикальне масштабування; реляційні бази даних; ACID; NoSQL; CAP-теорема УДК 004.62 The main stages of Machine Learning Pipelines are considered in the paper, such as: train data collection and storage, training and scoring. The effect of the Big Data phenomenon on each of the stages is discussed. Different approaches to efficient organization of computation are on each of the stage are evaluated. In the first part of the paper we introduce the notion of horizontal and vertical scalability together with corresponding cons and pros. We consider some limitations of scaling, such as Amdahl's law. In the second part of the paper we consider scalability of data storage routines. First we discuss relational databases and scalability limitations related to ACID guarantees, which such database satisfy. Then we consider horizontally scalable non-relational databases, so called NoSQL databases. We formulate CAP-theorem as a fundamental limitation of horizontally scalable databases. The third part of the paper is dedicated to scalability of computation based on the MapReduce programming model. We discuss some implementations of this programming model, such as Hadoop and Spark together with some basic principles which they are based on. In the fourth part of the article we consider various approaches towards scaling of Machine Learning methods. We give the general statement of Machine Learning problem. Then we show how MapReduce programming model can be applied for horizontal scaling of Machine Learning methods on the example of Bayessian pattern recognition procedure. On the example of Deep Neural Networks we discuss Machine Learning methods which are not horizontally scalable. Then we consider some approaches towards vertical scaling of such methods based on GPU’s and the TensorFlow programming model. В работе рассматриваются основные этапы решения задачи обучения распознаванию образов, а именно: обработка и хранение обучающих данных, обучение распознаванию и распознавание. Обговаривается влияние феномена больших данных на каждый из этих этапов. Сравниваются различные подходы к эффективной организации вычислений на различных этапах. Первый раздел статьи посвящен определению понятия масштабирования, вводятся понятия горизонтального и вертикального масштабирования, обсуждаются их преимущества и недостатки. Рассматриваются некоторые ограничения при масштабировании на примере закона Амдала. Второй раздел статьи посвящен масштабированию хранилищ обучающих данных. Обговаривается подходы к масштабированию реляционных баз данных, и ограничения связанные с гарантиями ACID, которым удовлетворяют такие базы данных. Отдельно рассматриваются горизонтально масштабируемые нереляционные т. н. NoSQL базы данных. Приводится формулировка CAP-теоремы, как одного из фундаментальных ограничений при горизонтальном масштабировании таких баз данных. Третий раздел работы посвящен горизонтальному масштабированию вычислений на основе модели программирования MapReduce. Рассматриваются различные реализации этой модели программирования, такие как Hadoop и Spark, их строение и основные принципы работы. В четвертом разделе рассматриваются различные подходы к масштабированию методов машинного обучения. Приводится общая постановка задачи машинного обучения. На примере Байесовской процедуры обучения показывается, как модель программирования MapReduce применима для горизонтального масштабирования методов машинного обучения. Далее на основе глубоких нейронных сетей обговариваются методы обучения, не подлежащие горизонтальному масштабированию. Рассматриваются подходы к масштабированию таких методов при помощи графических процессоров (GPU) и модели программирования Tensor Flow. В роботі розглядаються основні етапи розв’язку задач машинного навчання (з учителем) розпізнаванню образів, а саме: управління навчальними виборками, навчання, розпізнавання. Обговорюється вплив феномену великих даних (BigData) на кожен з етапів, а також методи ефективної організації обчислень на кожному з етапів при розв’язанні зазначених задач. Інститут програмних систем НАН України 2019-06-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/361 10.15407/pp2019.02.069 PROBLEMS IN PROGRAMMING; No 2 (2019); 69-80 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2019); 69-80 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2019); 69-80 1727-4907 10.15407/pp2019.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/361/363 Copyright (c) 2019 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:02:47Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
machine learning pattern recognition horizontal scalability vertical scalability relational databases ACID NoSQL CAP-theorem UDC 004.62 |
| spellingShingle |
machine learning pattern recognition horizontal scalability vertical scalability relational databases ACID NoSQL CAP-theorem UDC 004.62 Biletskyy, B.O. Horizontal and Vertical Scalability of Machine Learning Methods |
| topic_facet |
machine learning pattern recognition horizontal scalability vertical scalability relational databases ACID NoSQL CAP-theorem UDC 004.62 машинное обучение распознавание образов горизонтальное масштабирование вертикальное масштабирование реляционные базы данных ACID NoSQL CAP-теорема УДК 004.62 методи машинного навчання розпізнавання образів горизонтальне масштабування вертикальне масштабування реляційні бази даних ACID NoSQL CAP-теорема УДК 004.62 |
| format |
Article |
| author |
Biletskyy, B.O. |
| author_facet |
Biletskyy, B.O. |
| author_sort |
Biletskyy, B.O. |
| title |
Horizontal and Vertical Scalability of Machine Learning Methods |
| title_short |
Horizontal and Vertical Scalability of Machine Learning Methods |
| title_full |
Horizontal and Vertical Scalability of Machine Learning Methods |
| title_fullStr |
Horizontal and Vertical Scalability of Machine Learning Methods |
| title_full_unstemmed |
Horizontal and Vertical Scalability of Machine Learning Methods |
| title_sort |
horizontal and vertical scalability of machine learning methods |
| title_alt |
Горизонтальное и вертикальное масштабирование методов машинного обучения Горизонтальне та вертикальне масштабування методів машинного навчання |
| description |
The main stages of Machine Learning Pipelines are considered in the paper, such as: train data collection and storage, training and scoring. The effect of the Big Data phenomenon on each of the stages is discussed. Different approaches to efficient organization of computation are on each of the stage are evaluated. In the first part of the paper we introduce the notion of horizontal and vertical scalability together with corresponding cons and pros. We consider some limitations of scaling, such as Amdahl's law. In the second part of the paper we consider scalability of data storage routines. First we discuss relational databases and scalability limitations related to ACID guarantees, which such database satisfy. Then we consider horizontally scalable non-relational databases, so called NoSQL databases. We formulate CAP-theorem as a fundamental limitation of horizontally scalable databases. The third part of the paper is dedicated to scalability of computation based on the MapReduce programming model. We discuss some implementations of this programming model, such as Hadoop and Spark together with some basic principles which they are based on. In the fourth part of the article we consider various approaches towards scaling of Machine Learning methods. We give the general statement of Machine Learning problem. Then we show how MapReduce programming model can be applied for horizontal scaling of Machine Learning methods on the example of Bayessian pattern recognition procedure. On the example of Deep Neural Networks we discuss Machine Learning methods which are not horizontally scalable. Then we consider some approaches towards vertical scaling of such methods based on GPU’s and the TensorFlow programming model. |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2019 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/361 |
| work_keys_str_mv |
AT biletskyybo horizontalandverticalscalabilityofmachinelearningmethods AT biletskyybo gorizontalʹnoeivertikalʹnoemasštabirovaniemetodovmašinnogoobučeniâ AT biletskyybo gorizontalʹnetavertikalʹnemasštabuvannâmetodívmašinnogonavčannâ |
| first_indexed |
2024-09-16T04:07:53Z |
| last_indexed |
2024-09-16T04:07:53Z |
| _version_ |
1818568273537531904 |
| fulltext |
Експертні та інтелектуальні інформаційні системи
© Б.О. Білецький, 2019
ISSN 1727-4907. Проблеми програмування. 2019. № 2 69
УДК 004.62 https://doi.org/10.15407/pp2019.02.069
Б.О. Білецький
ГОРИЗОНТАЛЬНЕ ТА ВЕРТИКАЛЬНЕ
МАСШТАБУВАННЯ МЕТОДІВ МАШИННОГО НАВЧАННЯ
В роботі розглядаються основні етапи розв’язку задач машинного навчання (з учителем) розпізнаванню
образів, а саме: управління навчальними виборками, навчання, розпізнавання. Обговорюється вплив
феномену великих даних (BigData) на кожен з етапів, а також методи ефективної організації обчислень
на кожному з етапів при розв’язанні зазначених задач.
Ключові слова: методи машинного навчання, розпізнавання образів, горизонтальне масштабування,
вертикальне масштабування, реляційні бази даних, ACID, NoSQL, CAP-теорема.
Вступ
Методи машинного навчання розпі-
знаванню образів останнім часом набули
значної популярності. З одного боку цьому
сприяє наявність предметних областей, що
не підлягають ефективному описанню кла-
сичними алгоритмами та методами про-
грамування. Це такі задачі як розпізнаван-
ня тону текстових повідомлень, виявлення
аномалій у потоках даних, розпізнавання
автомобільних номерних знаків, надання
рекомендацій або відновлення складних
функціональних залежностей. З іншого
боку популярності методів машинного
навчання сприяв феномен великих даних
(Big Data), що тягнув за собою накопичен-
ня об’ємних навчаючих вибірок та викори-
стання їх у машинному навчанні. Адже
складні задачі розпізнавання вимагають
застосування більш складних моделей
для розпізнавання (тобто таких моделей,
що мають більше незалежних параметрів),
а навчання таких моделей вимагає обробки
більшої кількості прикладів у процесі
навчання.
Відомо, що світові обсяги накопи-
чених даних зростають експоненціально
та, згідно оцінок, подвоюється кожні 20
місяців [1]. Натомість обчислювальна по-
тужність комп’ютерів також зростає екс-
поненціально згідно закону Мура [2], що
був сформульований засновником компа-
нії Intel у 1965 році, та зафіксував подво-
єння швидкодії процесорів кожні 18 міся-
ців. Такий баланс зростання обсягів даних
та зростання обчислювальної потужності
комп’ютерів дозволяв ефективно оброб-
ляти накопичені дані. Однак близько 2010
року стало зрозуміло, що закон Мура пе-
рестав виконуватися. Це сталося, зокрема,
і через досягнення технологічних обме-
жень для поточної технології виробництва
процесорів. У роботі [2] представлено
дані щодо експоненціального зростання
тактової частоти процесорів найбільших
виробників, таких як: Intel, IBM, AMD,
DEC, Sun з 1985 по 2010. З наведених да-
них видно, що близько 2010 року зрос-
тання досягло точки насичення та припи-
нилося.
Для багатьох існуючих програмних
систем, що були розраховані на обробку
неперервно зростаючих масивів даних з
новою актуальністю постало питання ма-
сштабування обчислень. До таких систем
належать і системи машинного навчання
розпізнаванню образів. Методи машинно-
го навчання та розпізнавання складаються
з кількох стадій, на які феномен великих
даних (Big Data) впливає по різному. Се-
ред важливих стадій машинного навчання
розпізнаванню образів є: накопичення та
зберігання навчаючих даних, навчання
розпізнаванню та розпізнавання.
1. Масштабування
Після того, як перестав виконувати-
ся закон Мура, постала необхідність у ма-
сштабуванні систем ефективного накопи-
чення, зберігання та обробки даних. Мас-
штабування надалі будемо розуміти як
можливість системи виконувати більше
обчислень паралельно без втрати швидко-
дії. На прикладі баз даних масштабування
https://doi.org/10.15407/pp2019.02.069
Експертні та інтелектуальні інформаційні системи
70
можна проінтерпретувати як здатність об-
робляти кілька запитів одночасно, тоді як
швидкодію системи пов’язуватимемо з
середнім часом обробки запиту.
Для поточної технології виробницт-
ва процесорів масового споживання за-
пропоновано два підходи масштабування:
горизонтальне та вертикальне.
Вертикальне масштабування до-
сягається за рахунок підвищення потужно-
сті окремого обчислювального пристрою.
Після припинення дії закону Мура верти-
кальне масштабування зводиться до збі-
льшення кількості обчислювальних ядер у
комп’ютері. Такий підхід має свої обме-
ження, адже кількість процесорів не може
зростати необмежено хоча б в силу обме-
женості фізичних розмірів комп’ютерів.
Крім того вартість багатопроцесорних
комп’ютерів непропорційно зростає з кі-
лькістю обчислювальних ядер, що може
підтримувати система. Крім того існують і
принципові обмеження для розпаралелю-
вання обчислень, що пов’язані з послідов-
ною структурою традиційних методів про-
грамування.
Горизонтальне масштабування
полягає у використанні великої кількості
достатньо простих комп’ютерів. До цієї
моделі масштабування звернулась компа-
нія Google, що одна з перших зіткнулася з
феноменом великих даних. Компанія
Google вирішила, відмовитися від верти-
кально масштабованих серверів та вико-
ристовувати комп’ютери масового вжитку
у власних дата-центрах через невисоку
вартість останніх. Горизонтальний підхід
до масштабування значно менш обмеже-
ний у сенсі простоти додавання нових
вузлів та їхньої вартості, якщо порівнюва-
ти з вертикальним підходом.
Програми побудовані на основі
класичних методів програмування не
починають працювати швидше за наявні-
стю додаткових процесорів або обчислю-
вальних вузлів. Аби скористатися перева-
гами масштабування необхідно належним
чином розпаралелити програми. Розпара-
лелювання призводить до втрати детермі-
нованості програм, які стають значно
складнішими для проектування та аналізу,
оскільки традиційні методи (такі як опе-
раційна семантика) розраховані на послі-
довне виконання операцій. Розпаралелю-
вання алгоритмів є непростою задачею,
тому все більшою популярністю корис-
туються різні парадигми (набори рекоме-
ндацій) організації паралельних обчис-
лень, які дозволяють описувати паралель-
ні обчислення та надають відповідний
програмний інструментарій, реалізований
на різних мовах програмування.
Наприклад, такий підхід як SOA
(Service Oriented Architecture) дозволяє
розпаралелювати досить широкий клас
обчислень на основі сервісів без станів
(детермінованих функцій). Цей підхід
реалізовано чи не на всіх популярних мо-
вах програмування. Іншим прикладом
може бути бібліотеки Akka, що ґрунту-
ється на алгебрі взаємодіючих процесів та
похідних формалізмах, таких як 𝜋-
числення, та дозволяє описувати значно
ширший клас паралельних обчислень.
Реалізація цієї моделі програмування дос-
тупна на мовах програмування Scala, C#
та Java.
Обмеження масштабування. Ідеа-
льним при масштабуванні є випадок, коли
продуктивність обчислювальної системи
лінійно залежить від кількості обчислюва-
льних вузлів у системі. Така ситуація на-
зивається лінійною масштабованістю, та є
практично недосяжною.
Закон Амдала описує приріст шви-
дкодії системи залежно від кількості ная-
вних обчислювальних ядер. Приріст швид-
кодії )(nS обчислювальної системи за ра-
хунок використання 𝑛 обчислювальних
ядер визначається відношенням
n
T
T
TT
nS
p
s
ps
)( ,
де sT – час обробки послідовної складової
обчислення одним обчислювачем, pT – час
обробки паралельної складової обчислення
одним обчислювачем.
Експертні та інтелектуальні інформаційні системи
71
2. Масштабування сховищ даних
Масштабування сховищ даних є
важливою проблемою при побудові сис-
тем машинного навчання, адже ефективне
зберігання навчаючих даних є ключовим
чинником, що впливає на ефективність
роботи таких систем. Окремої уваги вима-
гає необхідність постійно поповнювати
навчаючі дані щоб покращувати якість
моделей за рахунок навчання на більш
актуальних даних.
Масштабування реляційних баз
даних. Традиційно для ефективного збері-
гання великих обсягів навчаючих даних
використовуються реляційні бази даних та
системи управлінні ними (СУБД). Це сис-
теми що надають користувачеві механізм
зберігання та отримання даних у вигляді
реляцій або таблиць. Фізично реляційні
СУБД являє собою потужний вертикально
масштабований сервер, що виконує запити
клієнтів, рис. 1. Запити до реляційної
СУБД, як правило, надходять у вигляді
виразів мовою SQL, а результати поверта-
ються у вигляді реляцій. СУБД може об-
робляти запити багатьох клієнтів одночас-
но. Серед відомих реляційних СУБД є
Oracle, Microsoft SQL Server, MySQL,
PostgreSQL та інші.
Для реляційних баз даних характе-
рне зберігання даних у нормалізованому
вигляді, з метою мінімізації надлишково-
сті даних. Існує ціла градація нормальних
форм, кожна з яких визначає сукупність
вимог до реляцій, які дозволяють уникну-
ти певного виду надлишковості даних.
Нормалізація дозволяє ефективно зберіга-
ти реляційні дані, та водночас ускладнює
їхню обробку. Адже для агрегації даних,
розбитих між багатьма таблицями, необ-
хідно виконувати додаткові операції.
Окрім нормалізації даних для ре-
ляційних баз даних характерне гарантова-
не виконання так званих вимог ACID:
● Атомарність (Atomicity) озна-
чає, що транзакція (послідовність операцій
у запиті користувача) ніколи не буде вико-
нана частково. Або всі операції викону-
ються успішно, або жодна з них не вико-
нається у разі помилки хоча б однієї із
операцій у транзакції.
● Узгодженість (Consistency)
означає, що в результаті успішного вико-
нання транзакції узгодженість даних не
порушується. Однак під час виконання
транзакції узгодженість даних може тим-
часово порушуватися.
Рис. 1. Масштабування реляційних баз даних
Експертні та інтелектуальні інформаційні системи
72
● Ізоляція (Isolation) означає, що
паралельні транзакції(обробка запитів різ-
них користувачів) повинні бути незалеж-
ними. Ізоляція є досить складною для за-
безпечення вимогою, оскільки вимагає
організувати ефективний доступ та моди-
фікацію спільних ресурсів. Для забезпе-
чення ізоляції в реляційних СУБД викори-
стовуються 2 стратегії блокування доступу
до спільних ресурсів:
○ песимістичне блокування –
припускає наявність колізій при паралель-
ній роботі з ресурсом, тому доступ до ньо-
го надається тільки одній транзакції, а всі
конкуруючі за доступ до ресурсу транзак-
ції вишикуються в чергу;
○ оптимістичне блокування ґрун-
тується на припущенні, що колізії трапля-
ються рідко, тому перед завершенням тра-
нзакції робиться перевірка чи не змінилася
версія спільного ресурсу під час виконання
транзакції. Якщо версія ресурсу не зміни-
лася, то нова версія ресурсу зберігається в
базі даних, інакше транзакція відповідаль-
на за усунення колізій.
● Стійкість (Durability) – означає
що результати успішних транзакцій будуть
збережені навіть після відновлення роботи
СУБД в результаті збою (такого як знест-
румлення системи).
Нормалізація даних разом з вимо-
гами ACID ускладнюють масштабування
СУРБД, в результаті чого такі системи, як
правило, традиційно масштабуються вер-
тикально.
Горизонтальне масштабування
нереляційних (NoSQL) баз даних. Існує
ціла низка горизонтально масштабованих
систем управління базами даних, що на-
дають користувачеві механізм зберігання
та отримання даних, які моделюються ін-
шими засобами ніж табулярні реляції, які
притаманні для СУБД. Такі СУБД назива-
ються NoSQL СУБД, або NoACID СУБД,
оскільки функціонують за рахунок послаб-
лення вимог ACID. NoSQL СУБД з'явили-
ся у 1960 роках однак набули популярності
на фоні феномену великих даних. Фізично
NoSQL СУБД представляють собою сис-
тему пов’язаних обчислювальних вузлів,
на яких зберігаються дані, та поміж якими
розподіляється обробка запитів користува-
чів, (рис. 2).
На сьогодні виділяють наступні ти-
пи NoSQL СУБД:
● Стовпчикові NoSQL СУБД, де
дані зберігаються у вигляді стовпчиків, що
характеризуються унікальним ім’ям, зна-
ченням та часом останньої модифікації).
Прикладом стовпчикових NoSQL СУБД є
Cassandra.
● Документо-орієнтовані NoSQL
СУБД – орієнтовані на роботу з неструк-
турованими даними, або документами. Як
документи, наприклад, можуть виступати
звичайні текстові файли, або документи у
Рис. 2. Масштабування нереляційних (NoSQL) баз даних
Експертні та інтелектуальні інформаційні системи
73
форматі XML чи JSON. До стовпчикових
відноситься така NoSQL СУБД як
MongoDB.
● Ключ-значення NoSQL СУБД –
дані представляються у вигляді хеш-
таблиці пар ключ-значення. Ключ одноз-
начно визначає значення, яке в свою чергу
може мати внутрішню структуру та скла-
датися з кількох елементів різних типів. До
NoSQL СУБД типу ключ-значення відно-
ситься Dynamo.
● Графові NoSQL СУБД – дані
представляються у вигляді графів, тобто
набору вершин та дуг, з якими пов'язані
властивості різних типів. Популярною
графовою NoSQL СУБД є Neo4j.
Характерними властивостями
NoSQL СУБД є надлишковість при збері-
ганні даних, та зберігання їх у денормалі-
зованому вигляді, а також відсутність під-
тримки розподілених транзакцій. Серед
переваг – з’являється можливість горизон-
тального масштабування таких СУБД.
Обмеження горизонтального ма-
сштабування. Окрім закону Амдала існує
ряд інших принципових обмежень для го-
ризонтального масштабування.
Універсальний закон масштабу-
вання стверджує, що при збільшенні кіль-
кості обчислювальних вузлів продуктив-
ність системи не тільки перестане зростати
(згідно закону Амдала), але й взагалі зни-
зиться. Це відбуватиметься за рахунок ни-
зки чинників, одним з яких є необхідність
мережевої комунікації між вузлами в об-
числювальній системі при досягнені кон-
сенсусу. Передача даних по мережі нале-
жить до операцій вводу/виводу, що є знач-
но повільнішими за інші операції, такі як
операції з оперативною пам’яттю.
CAP-теорема. Розглянемо важливі
властивості розподіленої системи.
● Узгодженість (Consistency): всі
користувачі отримують однаковий найак-
туальніший стан системи (або помилку),
незалежно від вузла системи, що обробляє
запит.
● Доступність (Availability): на
кожен запит користувачів отримується
успішна відповідь, без гарантії актуально-
сті отриманих результатів.
● Стійкість до втрати зв’язку
(Partition tolerance): система не втрачає
працездатності та функціонує у нормаль-
ному режимі навіть за умов втрати (або
затримки передачі) довільної кількості
повідомлень при передачі даних між вуз-
лами системи.
CAP-теорема стверджує, що з трьох
вищенаведених властивостей в розподіле-
ній системі одночасно досяжні не більше
двох [4].
Оскільки передача даних у сучасній
комп’ютерній мережі є ненадійною за сво-
єю природою, тому у випадку розподіле-
них СУБД неможливо знехтувати вимогою
стійкості щодо втрати зв’язку (Partition
tolerance), адже такі втрати завжди мати-
муть місце. При побудові розподілених
СУБД вимога стійкості до втрати зв’язку
реалізується за замовчуванням, а вибір
робиться між системами, що є узгоджени-
ми (PC) або доступними (PA), рис. 3.
Популярні (PA) NoSQL СУБД гара-
нтують послаблений варіант узгодженості
системи, так звана узгодженість згодом
(Eventual Consistency), що гарантує збіж-
ність системи до узгодженого стану.
Досягнення узгодженого стану, або
консенсусу, в розподілених системах стій-
ких до обривів зв’язку є складною зада-
чею, оскільки в таких системах не може
бути фіксованої топології і, відповідно,
центрального сервера, який виконував би
функцію єдиного джерела актуальних ста-
ну системи. У системах, де постійно відбу-
ваються обриви зв’язку, роль центрального
сервера призначається динамічно, за до-
помогою алгоритмів досягнення консенсу-
су. Найпопулярнішими алгоритмами дося-
гнення консенсусу, збіжність яких доведе-
но, є Paxos та RAFT.
Окрім алгоритмів досягнення кон-
сенсусу значну роль при побудові (PA)
NoSQL СУБД відіграють спеціальні струк-
тури даних CRDT (Conflict-free replicated
data types), що дозволяються завжди
розв’язувати неузгодженості при парале-
льній модифікації спільних ресурсів.
Експертні та інтелектуальні інформаційні системи
74
3. Горизонтальне масштабування
обчислень
Існує низка підходів до горизонта-
льного масштабування обчислень. Тобто
розпаралелювання обчислень за рахунок
їх виконання на множині пов'язаних між
собою обчислювальних пристроїв. При
цьому масштабування відбувається за ра-
хунок збільшення кількості обчислюваль-
них вузлів системи. Горизонтальне масш-
табування підтримують такі методи як
SOA або модель акторів, що вже згадува-
лися вище.
Одним з популярних підходів до
масової обробки великих даних є модель
програмування MapReduce що також
використовує принцип горизонтального
масштабування. Цей підхід надає досить
простий інструментарій для описання ши-
роко класу обчислень на великих даних
[5]. Простота досягається за рахунок пред-
ставлення обчислень у вигляді базових
операцій двох типів (Map та Reduce), що
визначаються своїми алгебраїчними влас-
тивостями. Достатньо представити обчис-
лення у вигляді композиції операцій двох
зазначених типів, і реалізація моделі
MapReduce бере на себе розпаралелювання
відповідного обчислення, рис. 4.
При цьому дані, що обробляються,
повинні зберігатися на вузлах розподіленої
обчислювальної системи. При обчислен-
нях дані не рухаються між вузлами обчис-
лювальної системи, а, навпаки, обчислення
надсилаються до вузлів, на яких зберіга-
ються дані для проведення обрахунків. Це
Рис. 3. CAP-теорема
Рис. 4. MapReduce кластер з чотирьох вузлів
Експертні та інтелектуальні інформаційні системи
75
докорінно відрізняється від традиційного
підходу Data Warehouse, за якого дані
надсилаються для обробки до потужного
вертикально масштабованого центрально-
го сервера, де і проводяться обчислення.
Розглянемо основні засади, на яких
ґрунтується модель програмування
MapReduce. Нехай 𝑎 = (𝑎1, … , 𝑎𝑙 ), 𝑎 ∈ 𝐴𝑙
– масив даних деякого типу 𝐴, розподіле-
них між вузлами MapReduce кластера. І
нехай 𝑞: 𝐴𝑙 → 𝐵 – складна процедура обро-
бки розподіленої колекції 𝑎, що повертає
результат деякого типу 𝐵. Обчислення
𝑞(𝑎1, … , 𝑎𝑙) можна розпаралелити, якщо
існує представлення
𝑞(𝑎1, … , 𝑎𝑙) = 𝑚(𝑎1)⨁ … ⨁𝑚(𝑎𝑙),
де 𝑚: 𝐴 → 𝐵 операція обробки окремих
елементів розподіленої колекції, що є де-
термінованою функцією, а ⨁ : 𝐵 × 𝐵 →
→ 𝐵 це бінарна операція, що застосову-
ється для агрегації часткових результатів
обробки масиву даних.
Операція агрегації ⨁ задовольняє
властивостям комутативності, асоціатив-
ності та існування нейтрального елемента
у множині 𝐵.
Обчислення 𝑞(𝑎1, … , 𝑎𝑙) представ-
лене у вигляді Map і Reduce можна зоб-
разити у вигляді дерева, листки якого
відповідають частковим результатам
𝑚(𝑎1) ∈ 𝐵, а вершини – операціям агре-
гації часткових результатів. Алгебраїчні
властивості операцій Map і Reduce дозво-
ляють перебудувати дерево обчислень зі
збереженням остаточного результату об-
числення таким чином, щоб мінімізувати
обмін інформацією між вузлами обчислю-
вальної системи, рис. 5.
Серед переваг підходу MapReduce
є те, що у багатьох випадках він дозволяє
наблизитися до лінійної масштабованості.
Це досягається за рахунок мінімізації
частки послідовних обчислень, що змен-
шує ефект закону Амдала, а також за ра-
хунок мінімізації пересилки даних по ме-
режі, що, в свою чергу, зменшує негативні
наслідки Універсального закону масшта-
бування.
Реалізації MapReduce. Модель
програмування MapReduce є технічною
специфікацією розробленою компанією
Google, що обґрунтовує та надає рекомен-
дації щодо ефективної організації масової
обробки даних. Існує велика кількість реа-
лізацій моделі MapReduce у вигляді біблі-
отек, або IaaS сервісів. Провайдери хмар-
них обчислень, такі як Google Cloud,
Amazon Web Services, та Microsoft Azure
дозволяють купувати кластери на основі
MapReduce для масової обробки даних.
Також існують провайдери спеціалізова-
них послуг, що фокусуються на MapRedu-
ce обчисленнях, наприклад, MapR, Data-
brix та Cloudera.
Рис. 5. Дерево обчислень MapReduce
Експертні та інтелектуальні інформаційні системи
76
Популярною реалізацією моделі
MapReduce є бібліотека з відкритим кодом
Apache Hadoop. Вона складається з двох
модулів:
● з розподіленої файлової систе-
ми HDFS, що відповідає за ефективне збе-
рігання розподілених даних;
● координатора розподілених об-
числень YARN, що відповідає за коорди-
націю обчислювального навантаження між
вузлами системи.
За допомогою цих двох модулів ре-
алізується модель програмування
MapReduce. Apache Hadoop є бібліотекою з
відкритим кодом, тому її можна заванта-
жити та встановити у приватній мережі
комп’ютерів масового вжитку, або купити
Hadoop кластер у вигляді IaaS.
Бібліотека Apache Hadoop набула
значної популярності, не дивлячись на те,
що базові операції Map і Reduce носять
досить низькорівневий характер. Реальні
обчислення складаються з композиції ве-
ликої кількості таких операцій. Відповід-
дю на цей виклик стали більш високорів-
неві обчислювальні системи та бібліотеки
побудовані на основі Apache Hadoop. Такі
системи надають користувачеві більш ви-
сокорівневі і, відповідно, більш зручні ме-
тоди описання певних видів розподілених
обчислень. Наприклад, існує ціла низка
систем, що надають можливість виконува-
ти SQL запити на Apache Hadoop класте-
рах. До таких систем належать Hive, Pig,
Drill, та багато інших. Такі системи авто-
матично перекладають запити побудовані
на мові SQL у операції Map і Reduce, та
виконують їх, користуючись перевагами
розподілених обчислень.
Інша відома високорівнева бібліо-
тека, що використовує Apache Hadoop як
обчислювальна модель є Apache Spark. Ця
бібліотека надає зручний високорівневий
інтерфейс для роботи з даними, та дозво-
ляє зберігати проміжні дані та проводити
обчислення над ними в оперативній
пам’яті вузлів обчислювальної системи. Це
дозволяє значно прискорити процес обчи-
слень за рахунок уникнення чисельних
звернень до накопичувачів даних, і відпо-
відного зменшення повільних операцій
вводу/виводу. Apache Spark складається з
декількох модулів.
● Базового модуля Apache Spark,
що реалізує базову структуру представ-
лення даних, RDD – стійкий розподілений
набір даних (Resilient Distributed Dataset),
та надає високорівневі операції роботи з
такими даними. Робота з розподіленими
масивами даних при використанні RDD не
відрізняється від роботи зі звичайними
колекціями, з використанням функцій ви-
щого порядку (тобто таких функцій, що
приймають на вхід інші функції, які засто-
совуються до елементів колекції). Ці фун-
кції автоматично перекладаються на опе-
рації Map та Reduce та виконуються за до-
помогою Apache Hadoop.
● Spark Streaming – модуль, що
дозволяє здійснювати розподілену обробку
масивних потоків даних в реальному часі.
Дані обробляються у по мірі їх надхо-
дження до обчислювальної системи. Це
досягається за рахунок розбиття потоків
даних у послідовність відносно невеликих
RDD. Тому при роботі з потоками даних
використовуються майже ті самі інтерфей-
си, що й при роботі з розподіленими дани-
ми.
● Spark SQL – модуль, що надає
реалізацію мови запитів SQL використо-
вуючи модель обчислень на основі RDD та
Apache Hadoop. SQL – запити перетворю-
ються на операції з RDD, які в свою чергу
перетворюються на операції Map та Reduce
та виконуються на Apache Hadoop.
● Spark ML – модуль, що дозво-
ляє будувати горизонтально масштабовані
розподілені методи машинного навчання,
та надає цілу низку готових реалізацій різ-
номанітних методів, серед яких: методи
обробки навчаючих вибірок, методи виді-
лення характеристик об’єктів, методи зме-
ншення розмірності, методи навчання без
учителя, методів класифікації та регресії,
методи оцінки якості навчання, та багато
інших.
4. Розподілені методи машинного
навчання
Для з'ясування впливу феномену
великих даних на методи машинного на-
вчання розпізнаванню образів розглянемо
Експертні та інтелектуальні інформаційні системи
77
постановку такої задачі машинного на-
вчання, як класифікація. Задача класифіка-
ції полягає у тому, щоб за допомогою на-
вчаючої вибірки 𝜏 = (𝑥𝑖 , 𝑦𝑖)𝑖=1
𝑙 з пар
(𝑥𝑖, 𝑦𝑖) ∈ 𝑋 × 𝑌 (характеристики об’єкта –
клас), де 𝑋 – множина можливих характе-
ристик об’єкта, та 𝑌– скінченна множина
класів. Вимагається побудувати ефективну
в деякому сенсі функцію класифікації
𝑓: 𝑋 → 𝑌. Процедура 𝑞(𝜏) побудови функ-
ції класифікації 𝑓(∙) за навчаючою вибір-
кою 𝜏 називається процедурою навчання.
Сама задача класифікації окремих
об’єктів за наявністю побудованої в про-
цесі навчання функції класифікації 𝑓(∙), є,
як правило, простою відносно нескладно в
сенсі обчислень. Задача масової класифі-
кації об’єктів досить просто розпарале-
люється, оскільки розпізнавання окремих
об’єктів відбувається незалежно, а сама
функція розпізнавання є детермінованою.
Горизонтальне масштабування таких об-
числень є простою задачею. Обчислення
такого виду можна розпаралелити за до-
помогою SOA, або за допомогою лише
функції Map моделі програмування
MapReduce.
Значно складнішою є процедура
побудови функції класифікації 𝑓(∙) = 𝑞(𝜏)
в процесі навчання. Навчання вимагає об-
робки масивних об’ємів навчаючих даних
𝜏. Для ефективного виконання обробки
навчаючих даних можна застосовувати
модель програмування MapReduce. Для
цього необхідно представити процедуру
навчання 𝑞(𝜏) у вигляді операцій Map і
Reduce, або описати її за допомогою більш
високорівневих бібліотек. Наприклад біб-
ліотека Apache Spark надає розподілені
реалізації цілої низки методів навчання
класифікації, таких як Байєсівські методи,
випадковий ліс, дерево рішень, метод опо-
рних векторів та інші.
Розподілена Байєсівська проце-
дура розпізнавання. Розглянемо стадії
навчання та класифікації на прикладі байє-
сівської класифікації. Байєсівський класи-
фікатор будується на основі відомої фор-
мули Байєса у вигляді функції 𝑓: 𝑋 → 𝑌
𝑓𝜋,𝜃(𝑥) = 𝑎𝑟𝑔𝑚𝑎𝑥𝑦∈𝑌𝑙𝑔 (𝜋𝑥)𝑙𝑔 (𝜃𝑥,𝑦),
що параметризована вектором оцінок ап-
ріорних ймовірностей класів 𝜋, а також
матрицею умовних ймовірностей 𝜃. Етап
навчання 𝑞(𝜏) полягає у побудові вектора
𝜋 та матриці 𝜃 за допомогою навчаючих
даних 𝜏. Процедуру навчання 𝑞(𝜏) можна
розпаралелити, якщо представити її у ви-
гляді операцій Map і Reduce.
Продемонструємо на прикладі об-
числення вектора апріорних ймовірностей
𝜋 ∈ 𝑅|𝑌| як виконується обробка розподі-
леного масиву даних під час навчання.
Підрахунок елементів вектору в процесі
навчання відбувається у вигляді
l
ni
i
)(
,
де )(in кількість навчаючих прикладів,
що потрапляють до і-го класу 𝑖 ∈ 𝑌, а 𝑙 –
загальна кількість навчаючих прикладів,
𝑙 = ∑𝑛
𝑖=1 𝑛𝑖(𝜏).
Нехай Map це функція 𝑚: 𝑋 × 𝑌 →
→ {0,1}|𝑌|, що ставить у відповідність на-
вчаючому прикладу (𝑥, 𝑦) ∈ 𝑋 × 𝑌 буле-
вий вектор розмірності |𝑌| з одиницею на
тій позиції, що відповідає порядковому
номеру класу 𝑦 ∈ 𝑌, до якого потрапляє
навчаючий приклад (𝑥, 𝑦), решта елемен-
тів вектора є нульовими. Тоді операція
Reduce є операцією ⨁ поелементної суми
двох векторів розмірності |𝑌|, для таким
чином визначеної операції агрегації ви-
конуються необхідні умови асоціативнос-
ті, комутативності та існування нейтраль-
ного елемента (нульовий вектор), в силу
виконання всіх цих умов для операції
звичайної суми цілих чисел. Після агрега-
ції всіх часткових результатів, кожна по-
зиція отриманого в результаті вектора
відповідатиме кількості навчаючих прик-
ладів певного класу.
Аналогічним чином підраховують-
ся і елементи матриці 𝜃 оцінок умовних
ймовірностей.
Штучні нейронні мережі та гли-
боке навчання. Останнім часом значної
популярності набули методи глибокого
навчання (Deep Learning), що використо-
вують багатошарові штучні нейронні ме-
Експертні та інтелектуальні інформаційні системи
78
режі. Ці методи демонструють приголом-
шливі результати, особливо у розпізнаван-
ні на неструктурованих даних. До таких
задач відносяться автоматичний переклад
текстів, виділення об’єктів на відео, виді-
лення тексту зі звукових повідомлень та
інші. Однією з важливих переваг таких
методів є можливість автоматичного виді-
лення характеристик об’єктів, за якими
відбувається розпізнавання, з неструкту-
рованих навчаючих даних.
Функція розпізнавання 𝑓(𝑥) у випа-
дку штучних нейронних мереж будується
у вигляді
𝑓(𝑥) = 𝑎𝑟𝑔𝑚𝑎𝑥𝑖∈𝑌𝑎𝑙,
де 𝜎 – вектор-функція активації, 𝑎𝑖 – збу-
дженість нейронів і-го шару, 𝑏𝑖 – вектор
порогів активації нейронів 𝑖-го шару, а 𝑤𝑖
матриця зв'язків нейронів 𝑖-го шару з ней-
ронами попереднього шару.
Процедура навчання 𝑞(𝜏) зводить-
ся до побудови матриць 𝑤𝑖 та векторів 𝑏𝑖,
що мінімізують похибку розпізнавання.
Популярним методом навчання нейрон-
них мереж є метод стохастичного градієн-
тного спуску, що використовує метод
зворотного розповсюдження для підраху-
нку часткових помилок розпізнавання та
для зміни відповідних коефіцієнтів мат-
риць 𝑤𝑖 та векторів 𝑏𝑖. Процедура на-
вчання 𝑞(𝜏) штучних нейронних мереж
заснована на зазначених методах має
компактне представлення у матричній
формі.
Метод градієнтного спуску є послі-
довною ітеративною процедурою, кожний
крок якої залежить від результатів попере-
дніх ітерацій. Навчання ускладняється
глобальним характером оптимізації коефі-
цієнтів нейронної мережі, адже відсутність
єдиності розв'язку унеможливлює агрега-
цію часткових результатів паралельних
процесів оптимізації.
Наразі значні зусилля дослідників
покладаються для розв'язання проблеми
горизонтального масштабування процедур
навчання штучних нейронних мереж. Од-
ним з підходів є використання генетичних
алгоритмів, за якого операція схрещування
використовується для поєднання результа-
тів, отриманих паралельними процесами
оптимізації на основі стохастичного граді-
єнтного спуску.
Масштабування штучних нейрон-
них мереж. Слабка горизонтальна масшта-
бованість змушує шукати альтернативні
методи ефективної організації процедур
навчання розпізнаванню штучних нейрон-
них мереж. Останнім часом значної попу-
лярності набуло вертикальне масштабу-
вання за допомогою спеціалізованих гра-
фічних процесорів.
Архітектура графічних процесорів
(GPU) відрізняється від архітектури тра-
диційних процесорів (CPU).
Для традиційних CPU процесорів
характерні: відносно мала кількість обчис-
лювальних ядер (сучасні персональні
комп’ютери масового вжитку мають 4 яд-
ра), обчислювальні ядра можуть незалежно
виконувати широкий спектр складних ло-
гічних операцій, відносно висока тактова
частота, наявність розвиненої логіки опти-
мізації операцій.
Для графічних GPU процесорів на-
впаки, характерні: значно більша кількість
обчислювальних ядер (кількість яких може
сягати кількох тисяч), значно менша так-
това частота, здатність виконувати парале-
льно лише однотипні та відносно прості
операції, рис. 6.
Графічні процесори стають у нагоді
для розпаралелювання масових однотип-
них операцій над масивами однорідних
даних. До таких задач належать операції
над матрицями, на яких ґрунтуються мето-
ди навчання розпізнаванню нейронних
мереж. Горизонтальне масштабування за
допомогою графічних процесорів реалізо-
ване в популярній бібліотеці TensorFlow,
запропонованою компанією Google [6].
Модель паралельних обчислень Tensor-
Flow представляє обчислення у вигляді
дерева, листки якого відповідають тензо-
рам, а вузли відповідають операціям над
тензорами.
Бібліотека TensorFlow є низькорів-
невим інструментом, тому існує низка
більш високорівневих бібліотек, що спро-
щують розпаралелювання обчислень пев-
ного виду, використовуючи TensorFlow як
Експертні та інтелектуальні інформаційні системи
79
обчислювальну модель. До таких бібліо-
тек, належить Keras, що надає високорів-
неві методи роботи з штучними нейрон-
ними мережами.
Висновки
В роботі проаналізовано різні скла-
дові задачі машинного навчання розпізна-
ванню образів, а саме: 1) накопичення,
збереження та обробка навчаючих даних;
2) машинне навчання; 3) розпізнавання.
Було проаналізовано вплив феномену ве-
ликих даних на кожну складову, а також
методи масштабування та їхні обмеження.
Показано, що більшість систем навчання
розпізнаванню з учителем підлягають, як
правило, горизонтальному масштабуван-
ню, за виключенням методів навчання на
основі нейронних мереж. Останні вимага-
ють вертикального масштабування, оскі-
льки використовують ітеративні алгорит-
ми у процесі навчання.
Література
1. Hilbert M., López P. The World's Technolo-
gical Capacity to Store, Communicate,
and Compute Information. Science. 2011.
Vol. 332. P. 60−65.
2. Andrew Danowitz, Kyle Kelley, James Mao,
John P. Stevenson, Mark Horowitz Com-
munications of the ACM. Vol. 55, N 4.
P. 55–63.
3. Moore G. Cramming more components onto
integrated circuits. Electronics. 1965. Vol. 38.
P. 114−117
4. Seth Gilbert and Nancy Lynch, "Brewer's
conjecture and the feasibility of consistent,
available, partition-tolerant web services",
ACM SIGACT News. 2002. Vol. 33, Issue 2.
P. 51–59.
5. MapReduce: Simplified Data Processing on
Large Clusters by Jeffrey Dean and Sanjay
Ghemawat https://static.googleusercontent.
com/media/research.google.com/en//archive/
mapreduce-osdi04.pdf
6. A computational model for TensorFlow: an
introduction by Martín Abadi, Michael Isard,
Derek G. Murray https://dl.acm.org/citation.
cfm?doid=3088525.3088527
References
1. Hilbert M., López P. The World's Technolo-
gical Capacity to Store, Communicate,
and Compute Information. Science. 2011.
Vol. 332. P. 60−65.
2. Andrew Danowitz, Kyle Kelley, James Mao,
John P. Stevenson, Mark Horowitz Commu-
nications of the ACM. Vol. 55, N 4. P. 55–63.
Рис. 6. Архітектура традиційного (CPU) та графічного (GPU) процесорів
Експертні та інтелектуальні інформаційні системи
80
3. Moore G. Cramming more components onto
integrated circuits. Electronics. 1965. Vol. 38.
P. 114−117
4. Seth Gilbert and Nancy Lynch, "Brewer's
conjecture and the feasibility of consistent,
available, partition-tolerant web services",
ACM SIGACT News. 2002. Vol. 33, Issue 2.
P. 51–59.
5. MapReduce: Simplified Data Processing on
Large Clusters by Jeffrey Dean and Sanjay
Ghemawat https://static.googleusercontent.
com/media/research.google.com/en//archive/
mapreduce-osdi04.pdf
6. A computational model for TensorFlow: an
introduction by Martín Abadi, Michael Isard,
Derek G. Murray https://dl.acm.org/citation.
cfm?doid=3088525.3088527
Одержано 18.04.2019
Про автора:
Білецький Борис Олександрович,
кандидат фізико-математичних наук,
старший науковий співробітник
Інституту кібернетики
імені В.М. Глушкова НАН України.
Кількість наукових публікацій в
українських виданнях – 13.
Кількість наукових публікацій в
зарубіжних виданнях – 2.
http://orcid.org/0000-0002-0667-8571
Місце роботи автора:
Інститут кібернетики
імені В.М. Глушкова НАН України.
03680, м. Київ,
Проспект Академіка Глушкова, 40.
Тел.: +38(044)526 2008.
E-mail: borys.biletskyy@gmail.com
mailto:borys.biletskyy@gmail.com
|