Automation of solving planimetry problems written in Ukrainian
The article focuses on developing a software solution for solving planimetry problems that are written in Ukrainian. We discuss tendencies and available abilities in Ukrainian natural language processing. Presenting a comprehensive analysis of different types of describing a problem, which shows reg...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2021
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/440 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-440 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/75/d3a5c25bb58b456d8c24a2439997de75.pdf |
| spelling |
pp_isofts_kiev_ua-article-4402024-04-26T22:46:31Z Automation of solving planimetry problems written in Ukrainian Автоматизація розв’язування задач з планіметрії, записаних природною українською мовою Zhezherun, O.P. Smysh, O.R. tokenization; lemmatization; Part-of-speech tagging; text segmentation; information extraction; annotated corpus UDC 004.04 планіметрія; обробка природньої мови; токенізація; лематизація; розмічування частин мови; сегментація тексту; видобування інформації; розмічений корпус УДК 004.04 The article focuses on developing a software solution for solving planimetry problems that are written in Ukrainian. We discuss tendencies and available abilities in Ukrainian natural language processing. Presenting a comprehensive analysis of different types of describing a problem, which shows regularities in the formulation and structure of the text representation of problems. Also, we demonstrate the similarities of writing a problem not only in Ukrainian but also in Belarusian, English, and Russian languages. The final result of the paper is a system that uses the morphosyntactic analyzer to process a problem’s text and provide the answer to it. Ukrainian natural language processing is growing rapidly and showing impressive results. Huge possibilities appear as the Gold standard annotated corpus for Ukrainian language was recently developed. The created architecture is flexible, which indicates the possibility of adding both new geometry figures and their properties, as well as the additional logic to the program. The developed system with a little reformatting can be used with other natural languages, such as English, Belarusian or Russian, as the algorithm for text processing is universal due to the globally accepted representations for presenting such types of mathematical problems. Therefore, the further development of the system is possible.Problems in programming 2020; 4: 71-80 У роботі досліджено й описано створення системи для розв’язування задач з планіметрії за допомогою сучасних можливостей обробки природної української мови та розробленої сукупності алгоритмів опрацювання тексту задачі. Розробка базується на аналізі текстів планіметричних задач та аналізі доступних засобів обробки живої української мови, що наразі наявні. Результатом роботи є кінцевий програмний продукт, написаний мовою Python, що дає змогу вирішувати прості завдання з планіметрії.Problems in programming 2020; 4: 71-80 Інститут програмних систем НАН України 2021-01-25 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/440 10.15407/pp2020.04.071 PROBLEMS IN PROGRAMMING; No 4 (2020); 71-80 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2020); 71-80 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2020); 71-80 1727-4907 10.15407/pp2020.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/440/444 Copyright (c) 2021 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-26T22:46:31Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
tokenization lemmatization Part-of-speech tagging text segmentation information extraction annotated corpus UDC 004.04 |
| spellingShingle |
tokenization lemmatization Part-of-speech tagging text segmentation information extraction annotated corpus UDC 004.04 Zhezherun, O.P. Smysh, O.R. Automation of solving planimetry problems written in Ukrainian |
| topic_facet |
tokenization lemmatization Part-of-speech tagging text segmentation information extraction annotated corpus UDC 004.04 планіметрія обробка природньої мови токенізація лематизація розмічування частин мови сегментація тексту видобування інформації розмічений корпус УДК 004.04 |
| format |
Article |
| author |
Zhezherun, O.P. Smysh, O.R. |
| author_facet |
Zhezherun, O.P. Smysh, O.R. |
| author_sort |
Zhezherun, O.P. |
| title |
Automation of solving planimetry problems written in Ukrainian |
| title_short |
Automation of solving planimetry problems written in Ukrainian |
| title_full |
Automation of solving planimetry problems written in Ukrainian |
| title_fullStr |
Automation of solving planimetry problems written in Ukrainian |
| title_full_unstemmed |
Automation of solving planimetry problems written in Ukrainian |
| title_sort |
automation of solving planimetry problems written in ukrainian |
| title_alt |
Автоматизація розв’язування задач з планіметрії, записаних природною українською мовою |
| description |
The article focuses on developing a software solution for solving planimetry problems that are written in Ukrainian. We discuss tendencies and available abilities in Ukrainian natural language processing. Presenting a comprehensive analysis of different types of describing a problem, which shows regularities in the formulation and structure of the text representation of problems. Also, we demonstrate the similarities of writing a problem not only in Ukrainian but also in Belarusian, English, and Russian languages. The final result of the paper is a system that uses the morphosyntactic analyzer to process a problem’s text and provide the answer to it. Ukrainian natural language processing is growing rapidly and showing impressive results. Huge possibilities appear as the Gold standard annotated corpus for Ukrainian language was recently developed. The created architecture is flexible, which indicates the possibility of adding both new geometry figures and their properties, as well as the additional logic to the program. The developed system with a little reformatting can be used with other natural languages, such as English, Belarusian or Russian, as the algorithm for text processing is universal due to the globally accepted representations for presenting such types of mathematical problems. Therefore, the further development of the system is possible.Problems in programming 2020; 4: 71-80 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2021 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/440 |
| work_keys_str_mv |
AT zhezherunop automationofsolvingplanimetryproblemswritteninukrainian AT smyshor automationofsolvingplanimetryproblemswritteninukrainian AT zhezherunop avtomatizacíârozvâzuvannâzadačzplanímetríízapisanihprirodnoûukraínsʹkoûmovoû AT smyshor avtomatizacíârozvâzuvannâzadačzplanímetríízapisanihprirodnoûukraínsʹkoûmovoû |
| first_indexed |
2024-09-16T04:08:42Z |
| last_indexed |
2024-09-16T04:08:42Z |
| _version_ |
1818568476141289472 |
| fulltext |
Моделі та методи машинного навчання
© О.П. Жежерун, О.Р. Смиш, 2020
ISSN 1727-4907. Проблеми програмування. 2020. № 4 71
УДК 004.04 https://doi.org/10.15407/pp2020.04.071
О.Р. Жежерун, О.Р. Смиш
АВТОМАТИЗАЦІЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ
З ПЛАНІМЕТРІЇ, ЗАПИСАНИХ ПРИРОДНОЮ
УКРАЇНСЬКОЮ МОВОЮ
У роботі досліджено й описано створення системи для розв’язування задач з планіметрії за допомогою
сучасних можливостей обробки природної української мови та розробленої сукупності алгоритмів
опрацювання тексту задачі. Розробка базується на аналізі текстів планіметричних задач та аналізі дос-
тупних засобів обробки живої української мови, що наразі наявні. Результатом роботи є кінцевий про-
грамний продукт, написаний мовою Python, що дає змогу вирішувати прості завдання з планіметрії.
Ключові слова: обробка природньої мови, токенізація, лематизація, розмічування частин мови, сегмен-
тація тексту, видобування інформації, розмічений корпус.
Вступ
Мова – це той інструмент, за допомо-
гою якого люди спілкуються та розуміють
одне одного. Саме ці мови, які використовує
людство у повсякденному житті між собою є
природною, тобто такою, що виникла при-
роднім шляхом серед людей. Проте, коли
потрібно задати команди комп’ютеру, вико-
ристовують формальну (штучну) мову –
мову програмування. Мова програмування є
тим ключем, що дає змогу командами (на-
борами інструкцій) створити зв’язок між
людьми та комп’ютерами.
Природна мова має вагому, досі не-
вирішену проблему, через що не годиться
для взаємодії з комп’ютером, здебільшого
через свої синтаксичні, смислові, відмін-
кові та референційні неоднозначності.
Обробка природної мови (англ.
Natural language processing або NLP) –
галузь в лінгвістиці, комп’ютерних науках,
інформаційній інженерії та штучному ін-
телекті, яка спрямована на комп’ютерний
аналіз та обробку природної (людської)
мови. Загалом, метою NLP є надати мож-
ливість уніфікувати природну мову для
розуміння її комп’ютером. Звісно, наразі
машини не здатні розуміти українську мо-
ву, так само як розуміють її люди, проте
вже нині вони мають досить великі мож-
ливості. Але, варто зазначити, що найбіль-
ші можливості все ж доступні лише для
англійської мови. У цій роботі розглядає-
ться обробка природної української мови.
Розглянемо деякі ланки, що
передбачає NLP, які будуть використову-
ватися в цій роботі.
Сегментація – це поділ тексту на
певні значущі одиниці, такі як слова,
речення, абзаци. Поділ на слова в україн-
ській мові, як і в інших багатьох мовах
світу, що певною мірою використовують
кирилицю чи латиницю, не є складним
завданням, оскільки такі мови для поділу
на слова застосовують пробіли, тобто пусті
пропуски між словами, або знаки пунктуа-
ції. Дещо складніша ситуація з поділом на
речення. Хоч речення в українській мові
треба починати з великої літери та закін-
чувати крапкою (чи іншим символом пун-
ктуації, що позначає закінчення речення,
як-от знак оклику), все ж є слова, які гра-
матично правильно писати з великої бук-
ви, наприклад імена людей. Також існують
скорочення слів, де потрібно поставити
крапку [1].
Розмічування частин мови (англ.
Part-of-speech tagging) – це встановлення
кожному слову з тексту відповідного теґу,
який вказує, яка це частина мови зважаючи
на визначення слова та на контекст у сло-
восполученні, реченні чи абзаці. Розмічу-
вання частин мови ускладнюється тим, що
в природній українській мові одне й те ж
слово у різних реченнях може відповідати
різним частинам мови, а отже й мати інше
значення.
Стемінг (англ.Stemming) – процес
скорочення слова до основи шляхом від-
кидання допоміжних частин, таких як за-
кінчення чи суфікс.
Моделі та методи машинного навчання
72
Лематизація (англ. Lemmatization)
– це процес отримання базової словникової
форми слова – леми. На відміну від
стемінгу лематизація використовує у про-
цесі словник та морфологічний аналіз для
цього.
Видобування інформації – це про-
цес вилучення з неструктурованого або
малоструктурованого тексту структурова-
ної інформації, такої як сутності, зв’язки
між ними, атрибути [2]. Як галузь в NLP,
видобування інформації набуває все біль-
шої зацікавленості, оскільки гостро постає
необхідність у структуруванні інформації.
Варто також додати, що під кожну задачу,
надбудовується додаткова логіка на гото-
вий інструмент роботи з текстом, оскільки
охопити всі аспекти різних задач наразі не
є можливим.
Різновиди геометричних задач
Геометрія, як наука, поділяється на
певні галузі такі, як планіметрія, стереоме-
трія, тригонометрія та інші. У цій роботі
розглянуто планіметричні задачі, оскільки
їхні умови легше піддаються опису в текс-
товій формі (можливо обійтись без зобра-
ження фігур та без тригонометричних рів-
нянь), також вивчення геометрії розпочи-
нають саме з планіметрії, про що свідчать
програми шкільної освіти. Слід провести
аналіз видів задач та можливостей їхнього
подання.
Існують різні типи задач, які відріз-
няються між собою, як складністю обра-
хунку, так і структурою побудови умови,
питання (невідоме, що потрібно знайти) і
можливостей відповіді на неї.
Наразі планіметричні задачі учні
починають вивчати починаючи з 7 класу
школи в Україні. Зважаючи на це, доціль-
но ознайомитися з підручниками школярів
за 7 клас та з’ясувати структуру задач, які
там використано. Використовуючи термі-
нологію ЗНО [3], у цій роботі будемо розг-
лядати завдання відкритого типу з корот-
кою відповіддю. Далі розглянемо структу-
ру та побудову таких задач, вивівши їхні
закономірності шляхом статистичного
аналізу, для цього взявши задачі потрібно-
го типу зі шкільних підручників. Для де-
монстрації наведено приклад задачі відк-
ритого типу з короткою відповіддю, що
ілюструють більшість задач із підручника:
«У трикутнику ABC відомо, що ∠A = 30°,
∠B = 45°, CM – висота, AC = 10 см. Знай-
діть відрізок BM.». Надалі, саме цю задачу
використано як приклад, на основі якого
простежуватиметься хід обробки та
розв’язку всіх задач.
Отже, з тексту задачі видно, що за-
вдання подається здебільшого двома ре-
ченнями (рідше одним, ще рідше більш як
два), де перше вказує, що дано (умова), а
друге пояснює, що потрібно знайти. Як
можна побачити, в підручниках також ви-
користані спеціальні математичні символи
(знак кута, знак градуса та інші), що ско-
рочують написання обсягу тексту, але, як
буде видно далі в роботі, ускладнює робо-
ту опрацювання такого тексту аналізато-
ром. Усі іменування змінних (сутностей)
подаються латинськими літерами, що оче-
видно та міжнародно прийнято. Спеціаль-
ного слова, яке ідентифікувало би початок
подання інформації умови (дано) немає,
тому речення починаються прямо з подачі
цієї умови. Проте, речення, що пояснює
шукане, зазвичай починається зі слова
«знайдіть», рідше «обчисліть» та «визнач-
те», ще рідше зустрічаються питання, що
починаються на «чому дорівнює».
Розв’язком на такі типи задач зазвичай є
одне число, наприклад, шуканий градус
кута («Знайдіть ∠AMC.») чи довжина сто-
рони («Знайдіть гіпотенузу AB.»), рідше
зустрічається сукупність («Знайдіть бічні
сторони трикутника.»).
Для проведення кількісного аналізу,
яке зможе показати частоту повторень
слів, що так само допоможе у визначенні
на що саме варто сконцентрувати увагу,
насамперед потрібно звести весь список
зібраних задач до певного однакового ви-
ду. Тому для цього варто виконати лемати-
зацію, а символи замінити на прописне
слово. Процес методу реалізації лематиза-
ції є одним із ключових етапів попередньої
обробки тексту, бо дає змогу вилучити
закінчення й повертає основну чи словни-
кову форму слова, яка й називається ле-
мою. Виконавши процес лематизації пода-
ного вище прикладу задачі, отримано таке
речення: «у трикутник ABC відомо, що кут
Моделі та методи машинного навчання
73
A дорівнювати 30 градус, кут B дорівню-
вати 45 градус, CM — висота, AC дорів-
нювати 10 см. знайти відрізок BM.». Оче-
видно, що метод зняв відмінкові форми зі
слів, що допомагає при подальшому
кількісному аналізі задач. Проведено
лематизацію вибраних 76 задач, взятих з
підручника. Фрагмент результату показано
в таблиці.
Таблиця. Фрагмент результату кількісно-
го аналізу частоти повторень слів у 76 за-
дачах з планіметрії
№ Слово Повторюваність
1 дорівнює 137
2 см 119
3 трикутник 95
4 кут 82
5 знайти 80
6 градус 54
7 і 45
8 сторона 44
9 висота 32
10 у 29
11 abc 27
12 основа 26
13 що 22
14 прямокутний 20
З таблиці видно, що на першому міс-
ці за повторюваністю є слово «дорівнює»,
потім одиниця виміру відрізків «см». На
третьому місці розташоване слово «трику-
тник», з чого можна зробити висновок, що
з більшості задач, вибраних випадково зі
шкільних підручників, найбільше завдань,
які стосуються саме трикутника (чотирна-
дцяте місце теж свідчить про трикутник, а
саме на його різновид). Це очікувано,
оскільки трикутник – це найменший за
кількістю кутів багатокутник, а також три-
кутник вивчають більш поглиблено ніж
інші фігури, через те, що саме трикутник
лежить в основі тригонометрії, де вивча-
ють взаємозв’язки між сторонами й кутами
трикутників. Також цікаво, що на п’ятому
місці слово «знайти», що доводить те, що
шукане в завданні маркується цим словом.
Одинадцяте місце, що зайняло «abc», вка-
зує на іменування трикутника, тобто
«ABC» та рідше кут з вершиною «B». За-
звичай, в задачах вказано назву фігури,
оскільки це дозволяє легше описати умову,
як-от з якого кута проведено відрізок.
Різновиди геометричних задач
іншими мовами
Для подальшого створення універ-
сального алгоритму опрацювання тексту,
варто розглянути подання задач з планіме-
трії іншими мовами. Це також дасть змогу
програмі працювати навіть змінюючи при-
родну мову на іншу.
Розглянемо для початку східно-
слов’янські мови, оскільки українська мо-
ва входить до їхнього складу. До східно-
слов’янських мов ще входять білоруська та
російська мови. Почнемо з білоруської.
Варто зазначити, що оригінального підруч-
ника, написаного білоруською мовою не
вдалось знайти. Знайдені два підручники,
що використані для аналізу, є перекладом
підручників з російської мови.
Оглянемо одну стандартну планіме-
тричну задачу білоруською мовою з підру-
чника з геометрії за 7 клас. Дано задачу:
«У раўнабедраным трохвугольніку адна
старана роўна 5 см, другая – 10 см. Знай-
дзіце перыметр трохвугольніка.» [4].
Можна помітити, що задача має таку ж
структуру, як і задачі українською мовою.
Оскільки, спершу йде опис того, що дано,
а потім, у наступному реченні, зі словом
«Знайдзіце», йде пояснення того, що пот-
рібно знайти. Більшість задач подають
опис одним складним реченням та одним
простим реченням іде пояснення шуканого.
Отже, всі подібності, що існують
між українською та білоруською мовами
дають змогу у майбутньому переформату-
вати й використовувати створену програму
з білоруською природною мовою.
Російська мова, входячи спільно з
українською та білоруською до східно-
слов'янської підгрупи слов'янських груп
мов, має багато однакових ознак, як грама-
тичних, так і пунктуаційних, через що мо-
Моделі та методи машинного навчання
74
жна припустити можливість для викорис-
тання створеного алгоритму роботи з текс-
том. Розглянемо типову планіметричну
задачу, взяту з підручника з геометрії за 8
клас. Задача: «В равнобедренном треуго-
льнике ABC c основанием AC проведена
биссектриса AD. Найдите углы этого треу-
гольника, если ∠ADB = 110°.» [5]. Очеви-
дно, що структура тексту задачі подібна до
тексту українських задач. Ідентично, пер-
ше речення пояснює умову задачі, друге ж
речення описує, що потрібно знайти. Мо-
жна зробити висновок, що для алгоритму
програми не буде важно перейти на росій-
ську мову, змінивши лише лексику.
Для повноти дослідження, варто та-
кож оглянути й задачі англійською мовою.
Англійська є частиною германської групи,
що входить в індоєвропейську сім'ю мов.
Англійська та українська побудова тексту
задач значно відрізняється, що є очевид-
ним. Все ж розглянемо кілька задач для
розуміння побудови, що хоч трохи подібні
до структури тексту задач українською
мовою. «Triangle ABC has side lengths of
AB = 10, BC = 24, and AC = 26. Find the
three angles of the triangle.». Такий тип за-
дачі не розповсюджений, хоча й досить
наближений до українського варіанту,
оскільки є два речення, де в першому вка-
зано умову задачі, а в другому те, що пот-
рібно знайти, яке починається словом
«Find» (можна перекласти як «Знайдіть»).
Варто зазначити, що все ж більшість задач
англійською мовою використовують різ-
ний опис для пояснення шуканого. Знай-
дено такі варіанти у книжці для тих, хто
вчиться у коледжі: «find the measures of ∠B
and ∠C», «How long is each leg?», «find the
lengths of the two legs» [6]. Вищенаведені
приклади опису шуканого цілком можуть
бути вирішені в розробленому алгоритмі
програми цієї роботи.
Аналіз готових рішень для
розв’язку поставленої задачі
Розглядаючи проблему створення
системи для розв’язування задач з геомет-
рії, критичним аспектом у вирішенні за-
лишається першочергово вибір готового
рішення, яке змогло б задовольнити всім
потребам в обробці природної української
мови. Наразі список таких рішень досить
малий, порівняно, до прикладу, з англійсь-
кою мовою.
Це пояснюється й тим, що робота з
NLP часто залежить від спеціального текс-
тового корпусу. Текстовий корпус – це
структурована та ретельно підібрана коле-
кція текстів певною мовою. Найбільш ва-
гомими й інформативними корпусами
вважаються розмічені, оскільки вони не-
суть у собі морфологічну прописану до
слів інформацію, як рід, число, відмінок та
інше. Очевидно, що таких корпусів досить
мало для будь-якої мови, тим більше для
української, враховуючи те, що розмічення
зазвичай відбувається в ручну командою
людей-науковців.
Далі розглянемо наявні програмні
рішення, що працюють з обробкою саме
української живої мови.
Великий електронний словник укра-
їнської мови (ВЕСУМ) – це електронний
зведений словник, що містить слова украї-
нської мови з парадигмами відмінювання.
Також, окрім граматичної інформації, сло-
вник пропонує заміни слів-покручів, надає
розрізнення омонімів з відмінними пара-
дигмами, позначки для рідковживаних слів
тощо [7].
Морфологічний аналізатор та гене-
ратор для української та російської мов
Pymorphy2. Аналізатор може переводити
слово до нормальної форми, тобто надава-
ти лему слова, переводити слово до потрі-
бної форми та надавати граматичну інфо-
рмацію про слово. Підтримка української
мови у цьому аналізаторі є не основною, а
експериментальною [8]. Можливості
Pymorphy2 досить обмежені функціональ-
но, що не є достатнім для цієї роботи. Цей
створений аналізатор базується на словни-
ку ВЕСУМ.
Розглянемо модель UDPipe, що на-
вчена на золотому стандарті. «Золотий
морфосинтаксовий стандарт» – це тексто-
вий корпус, спеціально розроблений для
універсальних залежностей, що розмічено
повністю вручну у кілька шарів [9]. УЗ
(UD) скорочення від «універсальні залеж-
ності» (Universal Dependencies). Це міжна-
родний проект, випущений у 2014 році
спеціально для того, щоб описати синтак-
Моделі та методи машинного навчання
75
сичні зв'язки у природних мовах однією
спільною метамовою, спільним набором
понять. Основним поняттям синтаксичної
теорії, на якій базується проект, є залеж-
ність, яка прописується для кожного слова
(і не тільки) у реченні. Залежність – це
зв’язок між двома словами у реченні, де
одне з них є підрядним (залежник), а друге
(голова) – керує залежником. Цю залеж-
ність можна проілюструвати графічно,
поєднавши голову та залежник за допомо-
гою стрілки, яка йде з голови до залежни-
ка. UDPipe – це здатний до навчання пайп-
лайн для токенізації, маркування, лемати-
зації та парсингу залежностей CoNLL-U
файлів [10]. CoNLL-U формат – це переві-
рена та надійна версія формату CoNLL-X,
анотації в якому кодуються у простий тек-
стовий файл. Так, в їхні можливості вхо-
дить: повернення леми слова; визначення
частини мови; морфологічний розбір сло-
ва; номер до голови слова, що буде або
номером голови, або ж нулем; зв’язок у
реченні, який пов’язує слово з головою
(якщо слово є головою, то його іменовано
коренем у реченні).
Зрозуміло, що найбільше переваг і
можливостей присутні в моделі UDPipe,
що працює з розміченим корпусом. З боку
швидкості, зручності й якості роботи він є
найкращим інструментом. Звісно, у ньому
є свої недоліки, як некоректне тегування
чи розподіл на слова або речення, проте
наразі це найоптимальніше рішення для
роботи з обробкою української. Тому ви-
рішено використовувати саме цей засіб.
Побудова класів та методів для
опису планіметрії
Обираючи мову програмування, як
інструмент для створення застосунку,
вибір зроблений на користь Python. Оскі-
льки це мова загального призначення,
швидко набирає популярність останніми
роками, одна з найвикористовуваніших
мов для машинного навчання, існує бага-
то готових математичних бібліотек та
пакетів. А також через те, що UDPipe під-
тримує Python.
Визначивши у другому розділі ро-
боти, що трикутник найчастіше зустріча-
ється в задачах з планіметрії, вирішено
приділити увагу саме цій фігурі.
Доцільно створити ієрархію класів,
де головним буде клас «Багатокутник»
(«Polygon»), від якого унаслідуватимуться
всі інші багатокутні опуклі фігури. Хоча
зосередженість цієї роботи є на трикутни-
ку, але опис вищого класу дасть змогу у
майбутньому з легкістю додавати нові
фігури, не змінюючи та не перероблюючи
створену архітектуру. У цьому класі опи-
сано функцію для знаходження перимет-
ра, додаючи в циклі значення сторін бага-
токутника. Для подальшого створення
класів, ще варто описати функції, що по-
вертатимуть кількість відомих значень:
так, для сторін, функція повертатиме зна-
чення, яке вказує на кількість відомих
сторін, а для кутів, функція повертатиме
значення, яке вказує на кількість відомих
кутів. Відомі кути чи сторони, це ті, що
вже вказані в умові чи знайдені у процесі
розв’язання задачі. Це знадобиться у ви-
падку, коли, наприклад, у трикутнику
відомі два його кути, тоді знаючи цю ін-
формацію, можна буде з легкістю знайти
третій невідомий кут.
Клас «Трикутник» («Triangle») на-
слідуватиме клас «Багатокутник». Спи-
раючись на таксономію онтології плані-
метрії, різновиди трикутника описувати-
муться в окремих призначених класах,
проте деякі властивості, притаманні для
всіх трикутників, можливо запрограмува-
ти й у цьому класі. Наприклад, власти-
вість — змінну, що зберігатиме суму гра-
дусів кутів трикутника, що дорівнює 180.
Існують задачі, в яких не вказано назви
трикутника, тоді, для подальшого
розв’язання задачі, варто самостійно на-
дати фігурі назву, наприклад «ABC».
Далі, розглянемо функції, що ство-
рені для класу «Трикутник». Функція об-
рахунку площі трикутника, в основі якої
закладена формула Герона, що дає змогу
визначити площу трикутника за довжина-
ми його сторін. Функція обрахунку сто-
рони, яка шукає довжину сторони: за
трьома кутами та однією відомою сторо-
ною; за периметром та двома відомими
сторонами; за відомою площею та висо-
Моделі та методи машинного навчання
76
тою, що проведена до цієї сторони; за
властивістю медіани, що проведена до
цієї сторони. Функція обрахунку кутів, що
шукає значення кута: за трьома сторона-
ми, через арккосинус; за двома відомими
кутами, через їхнє віднімання від суми
кутів трикутника; за допомогою відно-
шення сторони до синуса протилежного
кута; за властивістю бісектриси, що про-
ведена з цього кута; за властивістю медіа-
ни, що проведена до сторони.
Коли в задачі є висота, медіана чи
бісектриса, тобто відрізки, що ділять ос-
новний трикутник, варто розуміти, що
подальше розв’язання задачі має відбува-
тися з оглядом на утворені фігури, як на
окремі трикутники. Очевидно, що для
розв’язування таких типів задач потрібно
весь час переходити з однієї фігури до
іншої, а в деяких випадках це може бути
потрібно й кілька разів. Отже, виникає
проблема, яка полягає у тому, щоб синх-
ронізувати отримувану інформацію з од-
ного трикутника в інший і навпаки, поки
не буде знайдено шукане. Для цього ство-
рено функцію у класі «Трикутник», що
відповідає за синхронізацію даних між
утвореними меншими трикутниками. За-
дача цієї функції у тому, щоб спершу при-
своїти утвореним фігурам уже відомі зна-
чення та передавати нові значення під час
знаходження кутів чи сторін у малих три-
кутниках основному трикутнику. Виклик
функції здійснюється під час того, як про-
ходить встановлення медіани, бісектриси
чи висоти. Синхронізація відбувається
кілька разів за все розв’язування задачі.
Встановлення медіани, бісектриси
та висоти відбувається трьома окремими
функціями, в яких є свої унікальні особ-
ливості, зважаючи на властивості цих
відрізків у трикутнику. Виклик таких фу-
нкцій здійснюється тоді, коли встановле-
на їхня наявність після опрацювання текс-
ту.
Клас «Прямокутний Трикутник»
наслідує вищий клас «Трикутник». У
цьому класі створена змінна, що вказує на
різновид трикутника, тобто зберігає зна-
чення «прямокутний». Також у класі про-
писано назви сторін трикутника, тобто
перша сторона має назву «гіпотенуза», а
інші дві – «катет». Одному з кутів трику-
тника присвоєно значення «90», цьому ж
куту присвоєно назву «прямий». Іншим
двом кутам присвоєно назву «гострий».
Додатково додано функцію, що обчислює
площу трикутника. Обрахунок здійсню-
ється за формулою половини добутку
катетів трикутника.
Клас «Рівнобедрений Трикутник»
наслідує вищий клас «Трикутник». У кла-
сі створено змінну, що вказує на різновид
трикутника, тобто зберігає значення «рів-
нобедрений». Також в цьому класі пропи-
сано назви сторін трикутника, тобто пер-
ша та третя сторона має назву «бічний», а
друга сторона має назву «основа».
Клас «Рівносторонній Трикутник»
наслідує вищий клас «Трикутник». У кла-
сі додано змінну, що вказує на різновид
трикутника, тобто зберігає значення «рів-
носторонній». Усім кутам трикутника
присвоєно значення «60».
Клас «Знайти» поєднує у собі кіль-
ка функцій. Функції для виводу інформа-
ції, в які входять: вивід кута за його іме-
нем; пошук кута, де відбувається пошук
шуканого кута за його іменем з усіх наяв-
них кутів; вивід всіх кутів фігури; вивід
сторони за його іменем; вивід сторони за
його назвою; пошук сторони, де відбува-
ється пошук шуканої сторони за іменем з
усіх наявних сторін; перевірка числа шу-
каного (однина чи множина).
Проте, основний алгоритм роботи
відбувається в конструкторі об’єкта кла-
су. Він пов’язаний з синтаксовим аналіза-
тором та буде розглянуто в наступному
розділі.
Використання морфосинтаксового
аналізатора в задачах планіметрії
Перед опрацюванням «сирого» те-
ксту задачі потрібно спершу підготувати
цей текст. Оскільки аналізатор, що вико-
ристано в цій роботі, не здатен боротися з
багатьма помилками. Тому першим кро-
ком має бути очищення тексту від цих
помилок. Помилки можуть бути синтак-
сичні, орфографічні, лексичні, тавтологі-
чні тощо.
Моделі та методи машинного навчання
77
Наступним кроком є заміна мате-
матичних символів на прописний аналог.
Аналізатор навчено на розмічених текс-
тах, переважно художнього стилю. Це
спричиняє не завжди коректне опрацю-
вання текстів математичних задач. Тому
варто автоматично замінювати такі сим-
воли: «°» на « градусів», «=» на «дорів-
нює», «∠» на «кут », «||» на «паралельна»
та інші. На прикладі вибраної задачі
отримано такий проміжний результат: «У
трикутнику ABC відомо, що кут A дорів-
нює 30 градусів, кут B дорівнює 45 граду-
сів, CM — висота, AC дорівнює 10 см.
Знайдіть відрізок BM.»
Останнім кроком є заміна різнома-
нітного формулювання для шуканого
одним уніфікованим аналогом, оскільки
визначення шуканого спиратиметься нада-
лі на це слово. Відбувається автоматична
заміна таких варіантів, як: «Обчисліть»,
«Визначте» та «Чому дорівнюють» на
«Знайдіть». У випадку вибраної демон-
страційної задачі такої заміни не потрібно.
Як можна помітити, майже всі за-
міни не є лемою цього ж слова. Це зроб-
лено для того, щоб подальший аналіз тек-
сту коректніше проставив залежності між
словами, а на це впливає форма слова.
Налаштування аналізатора
Для використання UDPipe можна
скористатись уже готовим прикладним
програмним інтерфейсом. Формат тексту
повинен бути UTF-8, а розмір одного запи-
ту не повинен перевищувати одного мега-
байта. Обробка тексту відбувається через
файл.
Одна з проблем, яка виникає, коли в
задачі задані числові значення з комою (не
цілі числа), є досить суттєвою. Аналізатор
створений так, щоб числа було поділено.
Бо, саме синтаксично, це є окремими токе-
нами. Оскільки, до прикладу, рахунок мат-
чу 10:0 та позначення часу 15:30 (ще мо-
жуть записувати як 15.30) є різними токе-
нами. Таке розбиття з одного числа, ство-
рить три окремі токени, де першим токе-
ном є ціла частина, другим є знак коми, а
третім дробовою частиною числа. Це при-
зведе до некоректного створення залежно-
стей між словами, що унеможливить пода-
льшу обробку тексту. Для виправлення
цього створено попередню перевірку ще не
проаналізованого тексту на наявність чи-
сел з комою. За допомогою можливостей
Python та розробленого регулярного вира-
зу відбувається пошук усіх чисел з комою,
подальший їхній запис у масив, а потім
заміна в тексті цих чисел на «00». Після
виконання своєї роботи аналізатором, чис-
ла вписуються назад на своє місце з маси-
ву. Оскільки аналізатор розпізнає число
«00» як один числовий токен, то подальше
повернення справжнього числа з масиву
аж ніяк не впливає на результат, а прове-
дений аналіз відповідає очікуваному.
Варто додати, що майже всі задачі
містять у тексті або знак «=», або ж слово
«дорівнює» (можлива й інша форма цього
слова). Проте знак під час обробки буде
замінено на слово, а надалі після лемати-
зації отримано всюди одне уніфіковане
слово «дорівнювати». Оскільки, більшість
задач подають дані в умові за допомогою
цього слова, доречно на основі нього ство-
рити пошук, який зможе відшукати в текс-
ті всі значення.
Пошук базується на двох умовах.
Спершу, перевірка чи токен перед словом
«дорівнювати» є кутом, тобто одна велика
або три великі латинські букви. Здійсню-
ється за допомогою регулярного виразу:
«^[A-Z]{1}$|^[A-Z]{3}$». Якщо умова ви-
конана, то значення кута з його назвою
заносяться у відповідні змінні. Наступна
умова перевіряє чи перед словом «дорів-
нювати» є сторона і здійснюється за допо-
могою регулярного виразу: «^[A-Z]{2}$».
Додано й третє розгалуження, в ра-
зі, якщо перші дві умови не виконуються.
Часто трапляється, що дані подано не до
конкретної змінної, або ж в задачі не нада-
но фігурі назви чи вказані дані описують
не кут чи сторону. Прикладом можуть бу-
ти такі варіанти: «основа рівнобедреного
трикутника дорівнює 12», «площа квадра-
та дорівнює 8», «більша сторона прямоку-
тного трикутника дорівнює 5» тощо. Тоді
пошук відбувається так: іде пошук слова
вліво, доки не знайдеться слово, яке аналі-
затором визначено як підмет, це й буде
змінною. Також ще відбувається пошук
Моделі та методи машинного навчання
78
означення до цього підмета, який зазвичай
може стояти зразу перед ним.
Цей пошук здійснюється за допомо-
гою обробленого тексту після синтаксово-
го аналізатора, коли слова поділені на
токени, проведена лематизація і визначені
зв’язки між ними. Підмет у стовпці, що
описує зв’язок, позначено як «nsubj»,
означення через стовпець частин мови
як «ADJ».
Коли під час пошуку знайдено під-
мет, далі йде порівняння цього токена з
переліком визначених слів. Якщо слово
збігається із заготовленим можливим
підметом, значення присвоюється від-
повідній змінній.
Пошук в умові задачі того, що
потрібно знайти, відбувається в конструк-
торі об’єкта класу «Find». Обробка здійс-
нюється за допомогою аналізатора. Орієн-
тиром, на який спирається пошук, є слово
«знайти».
Алгоритм роботи такий: відбуваєть-
ся проходження всього тексту після слова
«знайти», оминаючи токени, у яких визна-
чено частину мови, як «PUNCT» (знаки
пунктуації), «CCONJ» (різновиди сполуч-
ників), «VERB» (дієслова), «NUM» (чис-
ла), «SCONJ» (різновиди сполучників),
«ADP» (прийменники), «DET» (детер-
мінант), «ADV» (прислівниково-числівни-
кові займенники). Це потрібно для відки-
дання інформації, яка не несе в собі зна-
чущі, важливі для обробки, значення.
Проходження припиняється, якщо
на шляху трапляються такі токени, як: «.»,
«?», «якщо».
Після відбирання токенів, потрібно
порівняти їх із тими, які заздалегідь визна-
чені як важливі. Створено чотири масиви,
які поділені за своїм смислом: масив різ-
новиду шуканого (прикметники, як «най-
більший»); масив, що означає сторону
(іменники, як «відрізок» чи «відстань»);
масив, що означає кут. Ще один масив, де
зберігаються назви фігур. Також, може
бути знайдено ім’я шуканого за допомо-
гою регулярного виразу: «^[A-Z]{1,3}$».
Іще перевірка, якщо токен дорівнює сло-
вам «площа» чи «периметр».
Насамперед потрібно для обробки
задачі пройтися по лемах токенів, щоб
знайти назву фігури. Для цієї перевірки
створено масив, з назвами усіх багатокут-
них плоских фігур, а також масив з варіан-
тами написання їхнього виду. Після знахо-
дження токена назви фігури, перед ним
завжди стоятиме токен з його видом.
Після збігу назви фігури з токеном,
створюється екземпляр класу відповідної
фігури чи класу відповідного виду цієї
фігури.
Механізм розв’язування
планіметричної задачі на прикладі
Увівши задачу: «У трикутнику
ABC відомо, що ∠A = 30°, ∠B = 45°,
CM – висота, AC = 10 см. Знайдіть від-
різок BM.» у програму, спершу від-
будеться заміна символів на їхні прописні
слова-аналоги. Після цього кроку відбува-
ється перевірка програмою на числа з
комою. Наступний крок є одним з найос-
новніших, бо саме тут відбувається пере-
вірка тексту задачі аналізатором. Саме тут
текст аналізується, поділяється на токени,
відбувається лематизація, проставляння
залежностей між словами. Далі робота
виконується лиш з цим підготовленим
текстом.
Спершу визначається фігура, її вид
(може бути відсутнє), її іменування (може
бути відсутнє). Визначивши фігуру, від-
бувається виклик відповідного класу, що
їй належить. Варто зазначити, якщо в за-
дачі вказано вид фігури, до прикладу
«прямокутний трикутник», відповідний і
більш конкретний клас буде викликано.
Отже, в задачі з прикладу, буде визначено
фігуру «трикутник» та іменування фігури
«ABC».
Далі відбувається пошук в тексті
слів, таких як «бісектриса», «медіана» і
«висота». Знайшовши таке слово, викли-
кається відповідний метод в основному
класі «Triangle». У прикладі є висота, то-
му цьому відрізку присвоюється ім’я
«CM» з умови. У методі визначається:
кут, з якого проведено висоту; сторони,
що утворюють кут; до якої сторони про-
ведена висота; відрізки, на які ділить висо-
та, трикутники на які ділить висота.
За допомогою створених методів,
які опрацьовують дані навколо слова «до-
Моделі та методи машинного навчання
79
рівнювати», у задачі визначено спершу
значення кутів: куту «A» присвоєно зна-
чення «30», куту «B» присвоєно значення
«45»; потім визначено значення відрізків:
стороні «AC» присвоєно значення «10».
Тепер відбувається виклик класу
«Знайти». Результатом пошуку шуканого є
два масиви, де перший масив [«side»,
«name»] вказує на проставлені мітки знай-
деним токенам, а другий масив показує
самі ж токени [«відрізок», «BM»]. Порядок
елементів у першому та другому масивах
відповідає один одному.
За допомогою методу для знахо-
дження кутів, визначається невідомий
кут «C».
Враховуючи, що в задачі є висота,
яка ділить основний трикутник, утворені
менші трикутники досліджуються окремо
й розглядаються як повноцінні. Зважаючи
на властивості висоти, менші трикутники
належать до класу «Прямокутний Трикут-
ник». Далі у трикутнику «CAM» знахо-
диться довжина відрізка «CM» за допомо-
гою відомих значень сторони та синуса
кута. Відбувається виклик методу, що від-
повідальний за синхронізацію нових отри-
маних даних з трикутників. І в результаті у
трикутнику «BCM» за допомогою значень
сторони та тангенса кута отримано шука-
ний відрізок «BM».
Висновки
Отже, в роботі проведено аналіз
наявних на сьогодні можливостей з оброб-
ки живої української мови.
Проведено аналіз задач з геометрії,
який показує закономірності у форму-
люванні й структурі текстового подання
задач.
Створена архітектура є гнучкою й
це вказує на можливість додавання як
опису нових фігур та їхніх властивостей,
так і на створення додаткової логіки в
застосунку.
Варто вказати на можливість пере-
форматування програми для використання
її з іншою природною мовою, до прикладу
англійською, білоруською чи російською.
Література
1. Reynar J. C. A Maximum Entropy Approach
to Identifying Sentence Boundaries. Reynar
Jeffrey – Philadelphia, Pennsylvania, USA.
2. Sarawagi S. Information Extraction / Sara-
wagi Sunita – Mumbai. 2008.
3. ЗНО з математики: особливості тесту 2020
року [ЗНО з математики: особливості тес-
ту 2020 року [Електронний ресурс]. 2019.
Режим доступу до ресурсу:
https://osvita.ua/test/training/5017/.
4. Казакоў В.У. ГЕАМЕТРЫЯ. Мінск:
Народная асвета. 2017.
5. Геометрия. 7–9 классы [Л. С. Атанасян,
В. Ф. Бутузов, С. Б. Кадомцев та ін.]. Мо-
сква: Просвещение. 2010. 384 с. (20).
6. Alexander D.C., Koeberlein G.M. Elemen-
tary Geometry for College Students. Bel-
mont. (5).
7. Великий електронний словник української
мови (ВЕСУМ) [Електронний ресурс].
2017. Режим доступу до ресурсу:
https://github.com/brown-uk/dict_uk/blob/
master/doc/announcement.md.
8. Korobov M. Morphological Analyzer and
Generator for Russian and Ukrainian Lan-
guages. Ekaterinburg. 2015.
9. Золотий морфосинтаксовий стандарт
[Електронний ресурс]. Режим доступу до
ресурсу:
https://mova.institute/золотий_стандарт.
10. Straka M. Tokenizing, POS Tagging, Lem-
matizing and Parsing UD 2.0 with UDPipe /
Straka Milan Vancouver, 2017.
References
1. Reynar J. C. A Maximum Entropy Ap-
proach to Identifying Sentence Boundaries.
Reynar Jeffrey – Philadelphia, Pennsylva-
nia, USA.
2. Sarawagi S. Information Extraction / Sara-
wagi Sunita – Mumbai. 2008.
3. ZNO z matematyky: osoblyvosti testu 2020
roku. (2019). Retrieved June 12, 2020, from
https://osvita.ua/test/training/5017/
4. Kazakow V.U. Geometryja. Minsk: Narodna-
ja asveta. 2017.
5. Geometriya: 7–9-e klassy: uchebnik dlya
obshcheobrazovatelnykh uchrezhdeniy.
2010.
Моделі та методи машинного навчання
80
6. Alexander D.C., Koeberlein G.M. Elementary
Geometry for College Students. Belmont. (5).
7. Velykyi elektronnyi slovnyk ukrainskoi movy
(VESUM). (2017, November 30). GitHub Re-
trieved June 12, 2020,
from https://github.com/brown-
uk/dict_uk/blob/master/doc/announcement.md
8. Korobov M. Morphological analyzer and
generator for Russian and Ukrainian lan-
guages. Communications in Computer and
Information Science. 2015. Р. 320–332.
https://doi.org/10.1007/978-3-319-26123-
2_31
9. Zolotyi morfosyntaksovyi standart. Labo-
ratoriia ukrainskoi. Retrieved June 12.
2020, from https://mova.institute/золотий
_стандарт.
10. Straka M. Tokenizing, POS Tagging, Lemma-
tizing and Parsing UD 2.0 with UDPipe /
Straka Milan Vancouver. 2017.
https://doi.org/10.18653/v1/k17-3009
Одержано 23.10.2020
Про авторів:
Жежерун Олександр Петрович,
кандидат фізико-математичних наук, ста-
рший науковий співробітник.
Кількість наукових публікацій в
українських виданнях – 80.
Індекс Гірша – 4.
http://orcid.org/ 0000-0002-4034-6730,
Смиш Олег Русланович,
аспірант.
https://orcid.org/0000-0002-8074-9745.
Місце роботи авторів:
Національний університет «Києво-
Могилянська академія», завідувач кафедри
мультимедійних систем.
04655, Київ,
вул. Г. Сковороди 2.
Тел.: (044) 425-77-53
E-mail: zhezherun@ukma.edu.ua
Інститут програмних систем НАН України,
03187, Київ,
проспект Академіка Глушкова, 40.
Тел.: (044) 526-33-19
E-mail: o.smysh@ukma.edu.ua
|