Institute of Computer Science of the Czech Academy of Sciences
The science of causality explains/determines 'cause-effect' relationship between the entities of a system by providing mathematical tools for the purpose. In spite of all the success and widespread applications of machine-learning (ML) algorithms, these algorithms are based on statistical learning alone. Currently, they are nowhere close to 'human-like' intelligence as they fail to answer and learn based on the important "Why?" questions. Hence, researchers are attempting to integrate ML with the science of causality. Among the many causal learning issues encountered by ML, one is that these algorithms are dumb to the temporal order or structure in data. In this work we develop a machine learning pipeline based on a recently proposed 'neurochaos' feature learning technique (ChaosFEX feature extractor), that helps us to learn generalized causal-structure in given time-series data.
The one-variable fragment of any first-order logic may be considered as a modal logic, where the universal and existential quantifiers are replaced by a box and diamond modality, respectively. In several cases, axiomatizations of algebraic semantics for these logics have been obtained: most notably, for the modal counterparts S5 and MIPC of the one-variable fragments of first-order classical logic and intuitionistic logic, respectively. Outside the setting of first-order intermediate logics, however, a general approach is lacking. This paper provides the basis for such an approach in the setting of first-order lattice-valued logics, where formulas are interpreted in algebraic structures with a lattice reduct. In particular, axiomatizations are obtained for modal counterparts of one-variable fragments of a broad family of these logics by generalizing a functional representation theorem of Bezhanishvili and Harding for monadic Heyting algebras. An alternative proof-theoretic proof is also provided for one-variable fragments of first-order substructural logics that have a cut-free sequent calculus and admit a certain bounded interpolation property.
The theory of graphons has proven to be a powerful tool in many areas of graph theory. In this paper, we introduce several foundational aspects of the theory of digraphons -- asymmetric two-variable functions that arise as limits of sequences of directed graphs (digraphs). Our results address their decomposition into strongly connected components, periodicity, spectral properties, and asymptotic behaviour of their large powers.
The one-variable fragment of any first-order logic may be considered as a modal logic, where the universal and existential quantifiers are replaced by a box and diamond modality, respectively. In several cases, axiomatizations of algebraic semantics for these logics have been obtained: most notably, for the modal counterparts S5 and MIPC of the one-variable fragments of first-order classical logic and intuitionistic logic, respectively. Outside the setting of first-order intermediate logics, however, a general approach is lacking. This paper provides the basis for such an approach in the setting of first-order lattice-valued logics, where formulas are interpreted in algebraic structures with a lattice reduct. In particular, axiomatizations are obtained for modal counterparts of one-variable fragments of a broad family of these logics by generalizing a functional representation theorem of Bezhanishvili and Harding for monadic Heyting algebras. An alternative proof-theoretic proof is also provided for one-variable fragments of first-order substructural logics that have a cut-free sequent calculus and admit a certain bounded interpolation property.
The concept of causality is fundamental to numerous scientific explanations; nonetheless, its extension to the quantum regime has yet to be explored rigorously. This paper introduces the development of a quantum causal index, a novel extension of the classical causal inference framework, tailored to grasp the causal relationships inherent in quantum systems. Our study focuses on the asymmetric quantum conditional mutual information (QCMI), incorporating the von Neumann entropy, as a directional metric of causal influence in quantum many-body systems. We analyze spin chains using the QCMI, implementing a projective measurement on one site as the intervention and monitoring its effect on a distant site conditioned on intermediate spins. Additionally, we study the effective causal propagation velocity, which is the speed at which QCMI becomes significant at distant sites. These findings indicate the presence of finite-speed propagation of causal influence, along with the emergence of coherent oscillations.
We exhibit a uniform method for obtaining (wellfounded and non-wellfounded) cut-free sequent-style proof systems that are sound and complete for various classes of action algebras, i.e., Kleene algebras enriched with meets and residuals. Our method applies to any class of *-continuous action algebras that is defined, relative to the class of all *-continuous action algebras, by analytic quasiequations. The latter make up an expansive class of conditions encompassing the algebraic analogues of most well-known structural rules. These results are achieved by wedding existing work on non-wellfounded proof theory for action algebras with tools from algebraic proof theory.
Railway scheduling is a problem that exhibits both non-trivial discrete and continuous behavior. In this paper, we simulate train networks at a low level, where a number of timing and ordering constraints can appear. We model this problem using a combination of SAT and ordinary differential equations (SAT modulo ODE). In addition, we adapt our existing method for solving such problems in such a way that the resulting solver is competitive with methods based on dedicated railway simulators while being more general and extensible.
Vop\v{e}nka's Alternative Set Theory can be viewed both as an evolution and as a revolution: it is based on his previous experience with nonstandard universes, inspired by Skolem's construction of a nonstandard model of arithmetic, and its inception has been explicitly mentioned as an attempt to axiomatize Robinson's Nonstandard Analysis. Vop\v{e}nka preferred working in an axiomatic theory to investigating its individual models; he also viewed other areas of nonclassical mathematics through this prism. This article is a contribution to the mapping of the mathematical neighbourhood of the Alternative Set Theory, and at the same time, it submits a challenge to analyze in more detail the genesis and structure of the philosophical links that eventually influenced the Alternative Set Theory.
Approximation and learning of classifiers of large data sets by neural networks in terms of high-dimensional geometry and statistical learning theory are investigated. The influence of the VC dimension of sets of input-output functions of networks on approximation capabilities is compared with its influence on consistency in learning from samples of data. It is shown that, whereas finite VC dimension is desirable for uniform convergence of empirical errors, it may not be desirable for approximation of functions drawn from a probability distribution modeling the likelihood that they occur in a given type of application. Based on the concentration-of-measure properties of high dimensional geometry, it is proven that both errors in approximation and empirical errors behave almost deterministically for networks implementing sets of input-output functions with finite VC dimensions in processing large data sets. Practical limitations of the universal approximation property, the trade-offs between the accuracy of approximation and consistency in learning from data, and the influence of depth of networks with ReLU units on their accuracy and consistency are discussed.
Inter-rater reliability (IRR), which is a prerequisite of high-quality ratings and assessments, may be affected by contextual variables such as the rater's or ratee's gender, major, or experience. Identification of such heterogeneity sources in IRR is important for implementation of policies with the potential to decrease measurement error and to increase IRR by focusing on the most relevant subgroups. In this study, we propose a flexible approach for assessing IRR in cases of heterogeneity due to covariates by directly modeling differences in variance components. We use Bayes factors to select the best performing model, and we suggest using Bayesian model-averaging as an alternative approach for obtaining IRR and variance component estimates, allowing us to account for model uncertainty. We use inclusion Bayes factors considering the whole model space to provide evidence for or against differences in variance components due to covariates. The proposed method is compared with other Bayesian and frequentist approaches in a simulation study, and we demonstrate its superiority in some situations. Finally, we provide real data examples from grant proposal peer-review, demonstrating the usefulness of this method and its flexibility in the generalization of more complex designs.
The description of the dynamics of complex systems, in particular the capture of the interaction structure and causal relationships between elements of the system, is one of the central questions of interdisciplinary research. While the characterization of pairwise causal interactions is a relatively ripe field with established theoretical concepts and the current focus is on technical issues of their efficient estimation, it turns out that the standard concepts such as Granger causality or transfer entropy may not faithfully reflect possible synergies or interactions of higher orders, phenomena highly relevant for many real-world complex systems. In this paper, we propose a generalization and refinement of the information-theoretic approach to causal inference, enabling the description of truly multivariate, rather than multiple pairwise, causal interactions, and moving thus from causal networks to causal hypernetworks. In particular, while keeping the ability to control for mediating variables or common causes, in case of purely synergetic interactions such as the exclusive disjunction, it ascribes the causal role to the multivariate causal set but \emph{not} to individual inputs, distinguishing it thus from the case of e.g. two additive univariate causes. We demonstrate this concept by application to illustrative theoretical examples as well as a biophysically realistic simulation of biological neuronal dynamics recently reported to employ synergetic computations.
Item Response Theory (IRT) and Factor Analysis (FA) are two major frameworks used to model multi-item measurements of latent traits. While the relationship between two-parameter IRT models and dichotomized FA models is well established, IRT models with additional parameters have lacked corresponding FA formulations. This work introduces a four-parameter factor analytic (4P FA) model for multi-item measurements composed of binary items, building on the traditional dichotomized single-factor FA model. We derive the relationship between the proposed 4P FA model and its counterpart in the IRT framework, the 4P IRT model. A Bayesian estimation method is developed to estimate the four item parameters, the respondents' latent scores, and the scores adjusted for guessing and inattention effects. The proposed algorithm is implemented in R and Python, and the relationship between the 4P FA and 4P IRT models is empirically examined using two real datasets: a standardized admission test and a psychological anxiety inventory.
ShinyItemAnalysis (SIA) is an R package and shiny application for an interactive presentation of psychometric methods and analysis of multi-item measurements in psychology, education, and social sciences in general. In this article, we present a new feature introduced in the recent version of the package, called "SIA modules", which allows researchers and practitioners to offer new analytical methods for broader use via add-on extensions. We describe how to build the add-on modules with the support of the new SIAtools package and demonstrate the concepts using sample modules from the newly introduced SIAmodules package. SIA modules are designed to integrate with and build upon the SIA interactive application, enabling them to leverage the existing infrastructure for tasks such as data uploading and processing. They can access a range of outputs from various analyses, including item response theory models, exploratory factor analysis, or differential item functioning models. Because SIA modules come in R packages (or extend the existing ones), they may come bundled with their datasets, use object-oriented systems, or even compiled code. We discuss the possibility of broader use of the concept of SIA modules in other areas and the importance of freely available interactive psychometric software for methods dissemination.
In their study of the giant component in inhomogeneous random graphs, Bollob\'as, Janson, and Riordan introduced a class of branching processes parametrized by a possibly unbounded graphon. We prove that two such branching processes have the same distribution if and only if the corresponding graphons are fractionally isomorphic, a notion introduced by Greb\'ik and Rocha. A different class of branching processes was introduced by Hladk\'y, Nachmias, and Tran in relation to uniform spanning trees in finite graphs approximating a given connected graphon. We prove that two such branching processes have the same distribution if and only if the corresponding graphons are fractionally isomorphic up to scalar multiple. Combined with a recent result of Archer and Shalev, this implies that if uniform spanning trees of two dense graphs have a similar local structure, they have a similar scaling limit. As a side result we give a characterization of fractional isomorphism for graphs as well as graphons in terms of their connected components.
In this short note, we introduce cospectral graphons, paralleling the notion of cospectral graphs. As in the graph case, we give three equivalent definitions: by equality of spectra, by equality of cycle densities, and by a unitary transformation. We also give an example of two cospectral graphons that cannot be approximated by two sequences of cospectral graphs in the cut distance.
This paper focuses on a fundamental inquiry in a coupled oscillator model framework. It specifically addresses the direction of net information flow in mutually coupled non-identical chaotic oscillators. Adopting a specific form of conditional mutual information as a model-free and asymmetric index, we establish that if the magnitude of the maximum Lyapunov exponent can be defined as the 'degree of chaos' of a given isolated chaotic system, a predominant net information transfer exists from the oscillator exhibiting a higher degree of chaos to the other while they are coupled. We incorporate two distinct categories of coupled 'non-identical' oscillators to strengthen our claim. In the first category, both oscillators share identical functional forms, differing solely in one parameter value. We also adopt another measure, the Liang-Kleeman information flow, to support the generality of our results. The functional forms of the interacting oscillators are entirely different in the second category. We further extend our study to the coupled oscillator models, where the interacting oscillators possess different dimensions in phase space. These comprehensive analyses support the broad applicability of our results.
Recently, the influence of potentially present symmetries has begun to be studied in complex networks. A typical way of studying symmetries is via the automorphism group of the corresponding graph. Since complex networks are often subject to uncertainty and automorphisms are very sensitive to small changes, this characterization needs to be modified to an approximate version for successful application. This paper considers a recently introduced approximate symmetry of complex networks computed as an automorphism with acceptance of small edge preservation error, see Liu 2020. This problem is generally very hard with respect to the large space of candidate permutations, and hence the corresponding computation methods typically lead to the utilization of local algorithms such as the simulated annealing used in the original work. This paper proposes a new heuristic algorithm extending such iterative search algorithm method by using network centralities as heuristics. Centralities are shown to be a good tool to navigate the local search towards more appropriate permutations and lead to better search results.
08 Aug 2023
A representation theorem is proved for De Morgan monoids that are (i) semilinear, i.e., subdirect products of totally ordered algebras, and (ii) negatively generated, i.e., generated by lower bounds of the neutral element. Using this theorem, we prove that the De Morgan monoids satisfying (i) and (ii) form a locally finite variety. We then prove that epimorphisms are surjective in every variety of negatively generated semilinear De Morgan monoids. In the process, epimorphism-surjectivity is established for several other classes as well, including the variety of all semilinear idempotent commutative residuated lattices and all varieties of negatively generated semilinear Dunn monoids. The results settle natural questions about Beth-style definability for a range of substructural logics.
Graphlets are small subgraphs rooted at a fixed vertex. The number of occurrences of graphlets aligned to a particular vertex, called graphlet degree sequence, gives a topological description of the surrounding of the analyzed vertex. In this article, we study properties and uniqueness of graphlet degree sequences. The information given by graphlets up to size (n-1) is utilized graphs having certain type of asymmetric vertex-deleted subgraphs. Moreover, we show a reconstruction of trees from their (<= n-1)-graphlet degree sequences, which is much easier compared to the standard reconstruction from vertex-deleted subgraphs.
We analyze the computational power of discrete-time recurrent neural networks (NNs) with the saturated-linear activation function within the Chomsky hierarchy. This model restricted to integer weights coincides with binary-state NNs with the Heaviside activation function, which are equivalent to finite automata (Chomsky level 3) recognizing regular languages (REG), while rational weights make this model Turing-complete even for three analog-state units (Chomsky level 0). For the intermediate model α\alphaANN of a binary-state NN that is extended with α0\alpha\geq 0 extra analog-state neurons with rational weights, we have established the analog neuron hierarchy 0ANNs \subset 1ANNs \subset 2ANNs \subseteq 3ANNs. The separation 1ANNs \subsetneqq 2ANNs has been witnessed by the non-regular deterministic context-free language (DCFL) L#={0n1nn1}L_\#=\{0^n1^n\mid n\geq 1\} which cannot be recognized by any 1ANN even with real weights, while any DCFL (Chomsky level 2) is accepted by a 2ANN with rational weights. In this paper, we strengthen this separation by showing that any non-regular DCFL cannot be recognized by 1ANNs with real weights, which means (DCFLs \setminus REG) \subset (2ANNs \setminus 1ANNs), implying 1ANNs \cap DCFLs = 0ANNs. For this purpose, we have shown that L#L_\# is the simplest non-regular DCFL by reducing L#L_\# to any language in this class, which is by itself an interesting achievement in computability theory.
There are no more papers matching your filters at the moment.