SeLeCt - struktury, učení a kognice

Publikace

Autori Název
M. Bresler, D. Průša, V. Hlaváč Online recognition of sketched arrow-connected diagrams
International Journal on Document Analysis and Recognition, Vol. 19 (3), 2016, pp. 253-267.
Abstrakt: We introduce a new, online, stroke-based recognition system for hand-drawn diagrams which belong to a group of documents with an explicit structure obvious to humans but only loosely defined from the machine point of view. We propose a model for recognition by selection of symbol candidates, based on evaluation of relations between candidates using a set of predicates. It is suitable for simpler structures where the relations are explicitly given by symbols, arrows in the case of diagrams. Knowledge of a specific diagram domain is used—the two domains are flowcharts and finite automata. Although the individual pipeline steps are tailored for these, the system can readily be adapted for other domains. Our entire diagram recognition pipeline is outlined. Its core parts are text/non-text separation, symbol segmentation, their classification and structural analysis. Individual parts have been published by the authors previously and so are described briefly and referenced. Thorough evaluation on benchmark databases shows the accuracy of the system reaches the state of the art and is ready for practical use. The paper brings several contributions: (a) the entire system and its state-of-the-art performance; (b) the methodology exploring document structure when it is loosely defined; (c) the thorough experimental evaluation; (d) the new annotated database for online sketched flowcharts and finite automata diagrams.
Odkazy: BibTeX, DOI
M. Bresler, D. Průša, V. Hlaváč Recognizing Off-line Flowcharts by Reconstructing Strokes and Using On-line Recognition Techniques
In: Proceedings of the International Conference on Frontiers in Handwriting Recognition (ICFHR 2016), Shentzen, China, October 23-26, 2016, pp. 48-53.
Abstrakt: We experiment with off-line recognition of handwritten flowcharts based on strokes reconstruction and our state-of-the-art on-line diagram recognizer. A simple baseline algorithm for strokes reconstruction is presented and necessary modifications of the original recognizer are identified. We achieve very promising results on a flowcharts database created as an extension of our previously published on-line database.
Odkazy: BibTeX, DOI
L. Krtek, F. Mráz Two-Dimensional Limited Context Restarting Automata
In: Fundamenta Informaticae, Vol. 148 (3-4), 2016, pp. 309-340.
Abstrakt: Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.
Odkazy: BibTeX, DOI
F. Mráz, F. Otto, D. Průša Two-Dimensional Limited Context Restarting Automata
RAIRO - Theoretical Informatics and Applications, 2016, Cambridge University Press, publication ahead of print, preprint published online on December 7, 2016
Abstrakt: With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail.
Odkazy: BibTeX, DOI
I. Mrázová, P. Zvirinský Extraction and Interpretation of Textual Data from Czech Insolvency Proceedings (Technical Report)
TR No. 2016/1/KTIML, December 2016, 11 p.
Abstrakt: Recently, the Czech Insolvency Register covers about 200 000 insolvency proceedings commenced since 2008. In order to better assess the real impact of indebtedness across the Czech society, the data about the creditors or the reasons for the debt might be of great value. Unfortunately, the vast majority of such information is contained only in scanned document copies attached to the insolvency proceedings. Our goal is thus to extract textual data from the scanned pdf-files and to find the wanted information in the obtained texts.
Odkazy: Address requests for download to: I. Mrázová
F. Otto, F. Mráz Cyclically extended variants of Sgraffito and restarting automata for picture languages
In: H. Bordihn, R. Freund, B. Nagy, G. Vaszil (Eds.): Proceedings of the Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016), šsterreichische Computer Gesellschaft, vol. 321 of books@ocg.at, 2016, pp. 259-273.
Abstrakt: Here we introduce and study cyclic extensions of deterministic Sgraffito automata and of deterministic two-dimensional two-way ordered restarting automata for picture languages. Such a cyclically extended automaton can move in a single step from the last column (or row) of a picture to the first column (or row). For deterministic Sgraffito automata, we show that this cyclic extension does not increase the expressive power of the model, while for deterministic two-dimensional two-way restarting automata, the expressive power is strictly increased by allowing cyclic moves. In fact, for the latter automata, we take the number of allowed cyclic moves in any column or row as a parameter, and we show that already with a single cyclic move per column (or row) the deterministic two-dimensional extended two-way restarting automaton can be simulated. On the other hand, we show that two cyclic moves per column or row already give the same expressive power as any finite number of cyclic moves. Finally, we show that for one-row pictures (that is, strings), already one cyclic move suffices.
Odkazy: BibTeX
F. Otto, F. Mráz Regulated variants of limited context restarting automata
Theoretical Compute Science, vol. 682, pp. 190-207, 2016.
Abstrakt: In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the tape contents is reduced to a particular word within a finite number of applications of these contextual rewritings. Here we extend the limited context restarting automata by using additional global means to structure the reductions they execute. In fact, we study regulated lc-R-automata, for which a regular control language is used to restrict the set of admissible reduction sequences, and we propose random context conditions to restrict the place at which a transition of an lc-R-automaton can be applied.
Odkazy: BibTeX, DOI
M. Plátek, K. Oliva Redukční analýza A-stromů s minimalistickými omezeními
In: Proceedings of the 16th ITAT Conference on Information Technologies - Applications and Theory, Tatranské Matliare, Slovakia, September 15-19, 2016, pp. 26-33.
Abstrakt: Tento příspěvek navazuje na náš lonský příspěvek na ITATu. Zpracovává novým způsobem redukční analýzu na A-stromech, které jsou formalizací stromů, zpracovaných metodikou pro analytickou rovinu Pražského závislostního korpusu (PDT). Redukční analýza A-stromů sestává z minimálních korektních redukcí, které používají pouze elementární operace delete a shift. Hlavním cílem je vyvinout formální prostředky, které by exaktně zachycovaly lingvisticky pozorované minimalistické vlastnosti jednotlivých parametrů stromové redukční analýzy stromů ve formátu PDT a dovolily následně realizovat podobná pozorování na různých přirozených, či umělých jazycích. Pomocí pozorování lingvistického typu upřesnujeme strukturálně-složitostní vlastnosti A-stromů se závislostmi a koordinacemi. Zvýraznujeme vlastnosti, kterými se závislosti a koordinace liší.
Odkazy: BibTeX, Publication
D. Průša Complexity of Sets of Two-Dimensional Patterns
In: Y.-S. Han, K. Salomaa (Eds.): Proceedings of the 21st International Conference on Implementation and Application of Automata (CIAA 2016), LNCS, Vol. 9705, 2016, pp. 236-247.
Abstrakt: We study the two-dimensional pattern matching implemented using the two-dimensional on-line tessellation automaton, which is a restricted type of the cellular automaton able to simulate the Baker- Bird algorithm, proposed as the first algorithm for the two-dimensional pattern matching. We further explore capabilities of this automaton to carry out the matching task against an arbitrary set of equally sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity spreads in a wide range. It is demonstrated by giving examples, deriving general techniques and proving some lower bounds.
Odkazy: BibTeX, DOI
D. Průša, K. Reinhardt Undecidability of the emptiness problem for context-free picture languages
Theoretical Computer Science, 2016, in print.
Abstrakt:
Odkazy: BibTeX, DOI
J. van Leeuwen, J. Wiedermann Knowledge, Representation, and the Dynamics of Computation
In: G. Dodig-Crnkovic, R. Giovagnoli (Eds.): Representation and Reality: Humans, Animals and Machines. Studies in Applied Philosophy, Epistemology and Rational Ethics, Vol. 28, Springer, 2017.
Abstrakt: Cognitive processes are often modelled in computational terms. Can this still be done if only minimal assumptions are made about any sort of representation of reality? Is there a purely knowledge-based theory of computation that explains the key phenomena which are deemed to be computational in both living and artificial systems as understood today? We argue that this can be done by means of techniques inspired by the modelling of dynamical systems. In this setting, computations are defined as curves in suitable metaspaces and knowledge is generated by virtue of the operation of the underlying mechanism, whatever it is. Desirable properties like compositionality will be shown to fit naturally. The framework also enables one to formally characterize the computational behaviour of both knowledge generation and knowledge recognition. The approach may be used in identifying when processes or systems can be viewed as computational in general. Several further questions pertaining to the philosophy of computing are considered.
Odkazy: BibTeX
J. Vojt Deep neural networks and their implementation
Diploma thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2016, 96 p.
Abstrakt: Deep neural networks represent an effective and universal model capable of solving a wide variety of tasks. This thesis is focused on three different types of deep neural networks – the multilayer perceptron, the convolutional neural network, and the deep belief network. All of the discussed network models are implemented on parallel hardware, and thoroughly tested for various choices of the network architecture and its parameters. The implemented system is accompanied by a detailed documentation of the architectural decisions and proposed optimizations. The efficiency of the implemented framework is confirmed by the results of the performed tests. A significant part of this thesis represents also additional testing of other existing frameworks which support deep neural networks. This comparison indicates superior performance to the tested rival frameworks of multilayer perceptrons and convolutional neural networks. The deep belief network implementation performs slightly better for RBM layers with up to 1000 hidden neurons, but has a noticeably inferior performance for more robust RBM layers when compared to the tested rival framework.
Odkazy: BibTeX, Thesis
D. Průša Non-Recursive Trade-offs between Two-Dimensional Automata and Grammars
Theoretical Computer Science, Vol. 610/A, January 2016, pp. 121–132.
Abstrakt: We study succinctness of descriptional systems for picture languages. Basic models of two-dimensional finite automata and generalizations of context-free grammars are considered. They include the four-way automaton of Blum and Hewitt, the two-dimensional online tessellation automaton of Inoue and Nakamura and the context-free Kolam grammar of Siromoney et al. We show that non-recursive trade-offs between the systems are very common. Basically, each separation result proving that one system describes a picture language which cannot be described by another system can usually be turned into a non-recursive trade-off result between the systems. These findings are strongly based on the ability of the systems to simulate Turing machines.
Odkazy: BibTeX, DOI
J. Wiedermann, J. van Leeuwen Understanding and Controlling Artificial General Intelligent Systems
Submitted to The 10th AISB Symposium on Computing and Philosophy: Language, cognition, and computation, AISB Convention, University of Bath, UK, 19-21 April 2017 (in review).
Abstrakt: Artificial general intelligence (AGI) systems are advancing in all parts of our society. The potential of autonomous systems that surpass the capabilities of human intelligence has stirred debates everywhere. How should ‘super-intelligent’ AGI systems be viewed so they can be feasibly controlled? We approach this question based on the viewpoints of the epistemic philosophy of computation, which treats AGI systems as computational systems processing knowledge over some domain. Rather than considering their autonomous development based on ‘self-improving software’, as is customary in the literature about super-intelligence, we consider AGI systems as operating with ‘self-improving epistemic theories’ that automatically increase their understanding of the world around them. We outline a number of algorithmic principles by which the self-improving theories can be constructed. Then we concentrate on the problem of aligning the behavior of AGI systems with human values in order to make such systems safe. This issue arises concretely when one studies the social and ethical aspects of human-robot interaction in advanced AGI systems as they exist already today. Necessarily, the behavior of any such system will depend on its own world-view. We argue that there is no ‘universal’ AGI system whose values will always agree with the values of any other system. Finally, based on the principles of interactive proof systems, we design an architecture of AGI systems and an interactive scenario that will enable one to detect in their behavior deviations from the prescribed goals. The conclusions from our analysis of super-intelligent systems temper the over-optimistic expectations and over-pessimistic fears of singularity believers, by grounding the ideas on super-intelligent AGI systems in more realistic foundations.
Odkazy: BibTeX
F. Mráz, F. Otto, and D. Průša Some classes of rational functions for pictures
RAIRO - Theoretical Informatics and Applications, vol. 50, no. 4, pp. 351-369, 2016.
Abstrakt: With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions ofpictures, and we study the resulting classes of transductions in detail.
Odkazy: BibTeX, DOI

Poslední úprava: Neděle, 18.2.2018