SeLeCt - Structures, Learning and Cognition

Publications

Authors Title
P. Černo Restricted Restarting Automata
Doctoral Thesis (supervised by F. Mráz), Faculty of Mathematics and Physics, Charles University in Prague, Prague, 2015, 150 p.
Abstract: Restarting automata were introduced as a model for analysis by reduction which is a linguistically motivated method for checking correctness of a sentence. The thesis studies locally restricted models of restarting automata which (to the contrary of general restarting automata) can modify the input tape based only on a limited context. The investigation of such restricted models is easier than in the case of general restarting automata. Moreover, these models are effectively learnable from positive samples of reductions and their instructions are human readable.
Links: BibTeX, Thesis
F. Mráz, F. Otto, D. Průša On a class of rational functions for pictures
In: R. Freund, M. Holzer, N. Moreira, R. Reis (Eds.): Proceedings of the NCMA 2015 Seventh Workshop on Non-Classical Models of Automata and Applications, books@ocg.at, Vol. 318, Österreichische Computer Gesellschaft, Wien, 2015, pp. 159-176. ISBN 978-3-903035-07-2.
Abstract: With the aid of homogeneous morphisms, we extend the deterministic two-dimensional two-way ordered restarting automaton into a device that computes transductions of pictures, and we study the resulting class of transductions in detail.
Links: BibTeX, Presentation
I. Mrázová Deep Neural Networks and Their Role in the Quest for Human-Like Brain Power (Technical Report)
Plenary Talk, Complex Adaptive Systems Conference CAS 2015, November 2-4 2015, San José, CA, TR No. 2015/1/KTIML, Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague, Prague, November 2015, 33 p.
Abstract: The long-term interest in cognitive sciences has been enhanced by several strong impulses to contemporary computer science - in particular by large government initiated brain research projects. Other developments shift the area even more from the traditional von Neumann computing paradigm towards true connectionism implemented in silicon, too. New imaging technologies allow to follow the brain activity even at the individual neuron´s level. Inexpensive graphics processing units are becoming a common option for learning large-scale deep neural networks and currently unveiled brain-inspired chip architectures let us think of constructing complex cognitive algorithms mimicking the function of biological brains.

Perhaps the first deep artificial neural network incorporating some neurophysiological insights was the Neocognitron. Recent brain-inspired models of artificial neural networks include especially the so- called Deep Belief Networks and Convolutional Neural Networks. Both types of networks comprise several layers of functional neurons and both of them proved to be able to beat human performance in various areas of 2D image recognition. These models are, however, expected to yield superior results also for many other tasks ranging from language understanding and translation to multimedia data processing, among others.

While the majority of classical image processing techniques is based on carefully preselected image features, deep neural networks are designed to learn local features autonomously with minimum or no advanced pre-processing. The representations formed in their hidden layers resemble a hierarchy combining simpler features found at lower layers into more complex features detected at higher layers. Deep networks can be moreover trained by means of unlabeled data collected, e.g., from the internet. The found features can then be used as common building blocks for new images if labeled data is scarce.

Links: Presentation
I. Mrázová, P. Zvirinský Czech Insolvency Proceedings Data: Social Network Analysis
Procedia Computer Science, Vol. 61, 2015, pp. 52-59.
Abstract: In 2008, the Czech government launched an information system called Insolvency Register of the Czech Republic. Already within the first year of its operation, about 5200 insolvencies were commenced. This number rose, however, immensely in the following years as the impact of the Global Financial Crisis became evident also in the Czech Republic - industrial production fell by 13.4% and many areas witnessed massive layoffs. Meanwhile, the Czech Insolvency Register contains publicly available data concerning approximately 160 000 insolvency proceedings. The subjects participating in insolvency proceedings include debtors, creditors, senates deciding in the respective insolvency matter and insolvency administrators who handle debtor's assets during the proceedings. Often, the involved subjects participate in several insolvency proceedings thus forming a complex social network that evolves over time. In order to better understand emerging trends in such a type of networks, we orient our research towards the identification of influential individuals. Association rules used to predict future behavior of the network reveal several interesting patterns present across the entire country as well as locally in specific regions only.
Links: BibTeX, DOI, Presentation
F. Otto, F. Mráz Deterministic ordered restarting automata for picture languages
Acta Informatica, Vol. 52(7-8), 2015, pp. 593-623.
Abstract: The ordered restarting automaton (processing strings) is introduced, and it is shown that its nondeterministic variant is very expressive, as it accepts some languages that are not even context- free, while the deterministic ordered restarting automata just accept the regular languages. Then three different extensions of the deterministic ordered restarting automaton to two-dimensional inputs are defined that differ in the way in which they can move their read/write windows. We compare the classes of picture languages that these types of automata accept to each other and to some well studied classes of picture languages from the literature, and we present some closure and non-closure properties for them.
Links: BibTeX, DOI
Z. Petříčková Artificial Neural Networks and Their Usage for Knowledge Extraction
Doctoral Thesis (supervised by I. Mrázová), Faculty of Mathematics and Physics, Charles University in Prague, Prague, 2015, 191 p.
Abstract: The model of multi/layered feed/forward neural networks is well known for its ability to generalize well and to find complex non/linear dependencies in the data. On the other hand, it tends to create complex internal structures, especially for large data sets. Efficient solutions to demanding tasks currently dealt with require fast training, adequate generalization and a transparent and simple network structure.

In this thesis, we propose a general framework for training of BP/networks. It is based on the fast and robust scaled conjugate gradient technique. This classical training algorithm is enhanced with analytical or approximative sensitivity inhibition during training and enforcement of a transparent internal knowledge representation. Redundant hidden and input neurons are pruned based on internal representation and sensitivity analysis.

The performance of the developed framework has been tested on various types of data with promising results. The framework provides a fast training algorithm, robust to tunable parameters. Furthermore, it outperforms the reference techniques in the achieved generalization ability and robustness to noise in the data. It is very likely to identify redundant input features and create a simple and transparent network structure during training. In such a way it simplifies knowledge extraction from the model.

Links: BibTeX, Thesis
M. Plátek, D. Pardubská, K. Oliva Redukční analýza a Pražský závislostní korpus
In: J. Yaghob (Ed.): Proceedings of the ITAT 2015 15th Conference on Information Technologies - Applications and Theory (Hotel Čingov, Slovenský Raj, Slovakia), September 17-21 2015, Charles University in Prague, Prague, 2015, CEUR, Vol. 683, pp. 43-50.
Abstract: Cílem tohoto příspěvku je uvést, formálně zavést a exaktně pozorovat větnou redukční analýzu svázanou s redukční analýzu D-stromů. Tímto způsobem upřesníme strukturální vlastnosti D-stromů se závislostmi a koordinacemi z Pražského závislostního korpusu (PDT). Zvýrazňujeme vlastnosti, kterými se závislosti a koordinace liší. Snažíme se pracovat metodou, která je blízká metodám matematické lingvistiky, a to především těm, které formulují omezující podmínky pro syntaxi přirozených jazyků. Ukazujeme nové možnosti takových formulací.
Links: BibTeX, Presentation
M. Plátek, F. Mráz On Minimalistic, Contextual, Categorial Restarting Automata, and Contextual Grammars
Annals of the University of Bucharest, Informatics Series, Anul LXII, No. 3, 2015, pp. 93-104.
Abstract: The paper provides a study of (minimalistic contextual) analysis by reduction. Inspired by the work of Solomon Marcus and by categorial grammars we present a formal tool which represents both categorial contextual restarting automata and categorial Marcus contextual grammars. Four types of linguistically relevant finite and infinite languages defined by these automata are discussed. Several types of infiite hierarchies for all the four types of classes of languages considered here are obtained.
Links: BibTeX
D. Průša (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars
In: F. Drewes (Ed.): Proceedings of the CIAA 2015 20th International Conference on Implementation and Application of Automata, LNCS, Vol. 9223, 2015, pp. 250-262.
Abstract: We study how dimensionality and form of context-free productions a_ect the power of multi-dimensional context-free grammars over unary alphabets. Attention is paid to the emptiness decision problem. It is an open question whether or not it is decidable for two-dimensional Kolam type context-free grammars of Siromoney. We show that the undecidability can be proved in the three-dimensional setting. For the two-dimensional variant, we present several results revealing that the process of generating is still much more complex than that one of the classical one-dimensional context-free grammar.
Links: BibTeX, DOI
J. van Leeuwen, J. Wiedermann Separating the Classes of Recursively Enumerable Languages Based on Machine Size
International Journal of Foundations of Computer Science, Vol. 26 (6), 2015, pp. 677-695.
Abstract: In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy RE1⊂RE2⊂⋯ based on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy. We show that for every finite language L one has that L, (L) over bar ∈ REn for some n ≤ p ⋅ ( m − ⌊log2p⌋ + 1 ) + 1 where m is the length of the longest word in L, c is the cardinality of L, and p = min { c, 2 ( m − 1 )}. If L ∈ REn, then (L) over bar ∈ REs for some s = O ( n + m ). We also prove that for every n, there is a finite language Ln with m = O ( n log2n ) such that Ln ∉ REn but Ln, (L) over bar (n) ∈ REs for some s = O (n log2n). Several further results are shown that how the hierarchy can be separated by increasing chains of finite languages. The proofs make use of several auxiliary results for Turing machines with advice.
Links: BibTeX, DOI
J. van Leeuwen, J. Wiedermann Towards a Computational Theory of Epistemic Creativity
Proceedings of the AISB 2015 41st Annual Convention of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour (London), 2015, pp. 235-242.
Abstract: We investigate the computational process of creativity from the viewpoint of our recent thesis stating that computation is a process of knowledge generation. Rather than considering the creativity process in its full generality, we restrict ourselves to so-called epistemic creativity which deals with the processes that create knowledge. Within this domain we mainly concentrate on elementary acts of creativity — viz. drawing analogies. In order to do so using the epistemic framework, we define analogies as certain relationships among linguistic expressions and we state what knowledge must be discovered in order to resolve a given incompletely specified analogy. We assume analogies are formed in a natural language and also require that a solution of each analogy must contain an explanation why the resulting analogy holds. Finally, the difference between noncreative and creative computational processes is discussed. Our approach differs from the majority of previous approaches in stressing the knowledge discovery aspects of computational creativity, in requiring explanations in analogy solving and, last but not least, in including theory-less domains serving as knowledge base for knowledge discovery process.
Links: BibTeX
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, Springer, accepted (to appear in 2016).
Abstract: 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.
Links:

Last updated: Sunday, 02/18/18