Learning picture languages using picture-to-string transformations
| Thesis title in Czech: | Učení obrázkových jazyků využitím převodu obrázků na řetězce |
|---|---|
| Thesis title in English: | Learning picture languages using picture-to-string transformations |
| Key words: | obrázkové jazyky|čtyř-cestný konečný automat|strojové učení|formální jazyky |
| English key words: | picture languages|four-way finite automaton|machine learning|formal langugaes |
| Academic year of topic announcement: | 2021/2022 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Software and Computer Science Education (32-KSVI) |
| Supervisor: | RNDr. František Mráz, CSc. |
| Author: | Mgr. Ivan Rychtera - assigned and confirmed by the Study Dept. |
| Date of registration: | 17.03.2022 |
| Date of assignment: | 18.03.2022 |
| Confirmed by Study dept. on: | 29.03.2022 |
| Date and time of defence: | 01.02.2023 09:00 |
| Date of electronic submission: | 05.01.2023 |
| Date of submission of printed version: | 09.01.2023 |
| Date of proceeded defence: | 01.02.2023 |
| Opponents: | Mgr. Klára Pešková, Ph.D. |
| Guidelines |
| Formal picture languages are sets of rectangular matrices of symbols. Recognition of picture languages is harder than recognition of string languages. One of the possible approaches is rewriting an input picture into a string and then accepting it if and only if the string belongs to a given string language.
The goal of the thesis is to propose and implement a system for learning picture languages based on the above idea, where the picture-to-string transformation consists in collecting contents of a scanning window of small size when it scans the whole picture. Input for the system will be a set of positive and negative examples of pictures for a target picture language. The system should recognize the target picture language as precisely as possible. The system should support various models with different strategies for scanning the input pictures that can be realized by a simple model, like a four-way finite automaton, and multiple methods for learning string languages. Besides proposing the formal model, the thesis should implement a system for benchmarking the accuracy of recognition of picture languages based on the proposed models. |
| References |
| [1] Dora Giammarresi, Antonio Restivo: Two-dimensional languages. In: G. Rozenberg, A. Salomaa (eds.): Handbook of formal languages, Volume 3: Beyond Words. Springer, Berlin, Heidelberg, 1997, 215-267
[2] David Kuboň, Frantisek Mráz: How to learn picture languages. Research in Computing Science 148, no. 11 (2019): 115-126 [3] David Kuboň, Frantisek Mráz: Learning picture languages represented as strings. In: R. Barták, E. Bell (eds.): Proceedings of the Thirty-Third International Florida Artificial Intelligence Research Society Conference, AAAI Press, 2020, 529-532 [4] František Mráz, Friedrich Otto: Recognizing picture languages by reductions to string languages. Journal of Automata, Languages and Combinatorics 26, no. 1-2 (2021): 145-171 |