Ehrenfeucht-Fraïssé (EF) games are a basic tool in finite model theory for proving definability lower bounds, with many applications in complexity theory and related areas. They have been applied to study various logics, giving insights on quantifier rank and other logical complexity measures. In this paper, we present an EF game to capture formula size in counting logic with a bounded number of variables. The game combines games introduced previously for counting logic quantifier rank due to Immerman and Lander, and for first-order formula size due to Adler and Immerman, and Hella and Väänänen. The game is used to prove an extension of a formula size lower bound of Grohe and Schweikardt for distinguishing linear orders, from 3-variable first-order logic to 3-variable counting logic.

The KO (Kronecker Operation) code is a recent deep-learned error-correcting code using a neural network architecture to generalize a Reed-Muller code with Dumer decoding. Analyzing the encoder modules and using ablation techniques, we give interpretations of the KO encoder which significantly reduce the number of parameters. We also discuss interpretability aspects of the KO decoder. The interpretation opens up possibilities to give an explicit representation of KO codes, which could be useful for more efficient learning of KO codes and explaining the learning mechanism underlying the empirical observations made about its performance in previous work.

Several researchers have used deep learning to obtain novel feedback codes. Two such codes for AWGN channels with passive (possibly noisy) output feedback are Deepcode which employs a bit-by-bit rate 1/3 encoder, and Lightcode, which is a symbol-by-symbol code inspired by the Schalkwijk-Kailath (SK) scheme. Here, we build on prior work to interpret these codes by 1) providing the optimal maximum a posteriori (MAP) decoder for our simple non-linear interpretable encoder of a single-bit, two-round code that accurately approximates both single-bit Deepcode and Lightcode. This non-linear interpretable coding scheme, which mimics these codes, turns out to resemble both the functional form and performance of the Polyanskiy-Poor-Verdu (PPV) single bit feedback scheme that minimizes energy transmission asymptotically. 2) We extend our non-linear interpretable code to support more than one bit and two rounds, again providing an optimal MAP decoder. This remarkably simple and power-efficient nonlinear scheme provides insight into Lightcode.

Deep learning methods have recently been used to construct non-linear codes for the additive white Gaussian noise (AWGN) channel with feedback. However, there is limited understanding of how these black-box-like codes with many learned parameters use feedback. This study aims to uncover the fundamental principles underlying the first deep-learned feedback code, known as Deepcode, which is based on an RNN architecture. Our interpretable model based on Deepcode is built by analyzing the influence length of inputs and approximating the non-linear dynamics of the original black-box RNN encoder. Numerical experiments demonstrate that our interpretable model - which includes both an encoder and a decoder - achieves comparable performance to Deepcode while offering an interpretation of how it employs feedback for error correction.11This work was supported by NSF under awards 1900911, 2217023, and 2240532, and by the AI National Laboratory Program (RRF-2.3.1-21-2022- 00004). The contents of this article are solely the responsibility of the authors and do not necessarily represent the official views of the NSF.

As new deep-learned error-correcting codes continue to be introduced, it is important to develop tools to interpret the designed codes and understand the training process. Prior work focusing on the deep-learned TurboAE has both interpreted the learned encoders post-hoc by mapping these onto nearby "interpretable" encoders, and experimentally evaluated the performance of these interpretable encoders with various decoders. Here we look at developing tools for interpreting the training process for deep-learned error-correcting codes, focusing on: 1) using the Goldreich-Levin algorithm to quickly interpret the learned encoder; 2) using Fourier coefficients as a tool for understanding the training dynamics and the loss landscape; 3) reformulating the training loss, the binary cross entropy, by relating it to encoder and decoder parameters, and the bit error rate (BER); 4) using these insights to formulate and study a new training procedure. All tools are demonstrated on TurboAE, but are applicable to other deep-learned forward error correcting codes (without feedback).

Deep learning has been used recently to learn error-correcting encoders and decoders which may improve upon previously known codes in certain regimes. The encoders and decoders are learned "black-boxes", and interpreting their behavior is of interest both for further applications and for incorporating this work into coding theory. Understanding these codes provides a compelling case study for Explainable Artificial Intelligence (XAI): since coding theory is a well-developed and quantitative field, the interpretability problems that arise differ from those traditionally considered. We develop post-hoc interpretability techniques to analyze the deep-learned, autoencoder-based encoders of TurboAE-binary codes, using influence heatmaps, mixed integer linear programming (MILP), Fourier analysis, and property testing. We compare the learned, interpretable encoders combined with BCJR decoders to the original black-box code.

Word embeddings have developed into a major NLP tool with broad applicability. Understanding the semantic content of word embeddings remains an important challenge for additional applications. One aspect of this issue is to explore the interpretability of word embeddings. Sparse word embeddings have been proposed as models with improved interpretability. Continuing this line of research, we investigate the extent to which human interpretable semantic concepts emerge along the bases of sparse word representations. In order to have a broad framework for evaluation, we consider three general approaches for constructing sparse word representations, which are then evaluated in multiple ways. We propose a novel methodology to evaluate the semantic content of word embeddings using a commonsense knowledge base, applied here to the sparse case. This methodology is illustrated by two techniques using the ConceptNet knowledge base. The first approach assigns a commonsense concept label to the individual dimensions of the embedding space. The second approach uses a metric, derived by spreading activation, to quantify the coherence of coordinates along the individual axes. We also provide results on the relationship between the two approaches. The results show, for example, that in the individual dimensions of sparse word embeddings, words having high coefficients are more semantically related in terms of path lengths in the knowledge base than the ones having zero coefficients.

We administered the Verbal IQ (VIQ) part of the Wechsler Preschool and Primary Scale of Intelligence (WPPSI-III) to the ConceptNet 4 artificial intelligence (AI) system. The test questions (e.g. “Why do we shake hands?”) were translated into ConceptNet 4 inputs using a combination of the simple natural language processing tools that come with ConceptNet together with short Python programs that we wrote. The question answering used a version of ConceptNet based on spectral methods. The ConceptNet system scored a WPPSI-III VIQ that is average for a four-year-old child, but below average for 5–7 year olds. Large variations among subtests indicate potential areas of improvement. In particular, results were strongest for the Vocabulary and Similarities subtests, intermediate for the Information subtest and lowest for the Comprehension and Word Reasoning subtests. Comprehension is the subtest most strongly associated with common sense. The large variations among subtests and ordinary common sense strongly suggest that the WPPSI-III VIQ results do not show that “ConceptNet has the verbal abilities of a four-year-old”. Rather, children’s IQ tests offer one objective metric for the evaluation and comparison of AI systems. Also, this work continues previous research on psychometric AI.

Exploration and exploitation are the two cornerstones which characterize Evolutionary Algorithms (EAs) capabilities. Maintaining the reciprocal balance of the explorative and exploitative power is the key to the success of EA applications. Accordingly, this work is concerned with proposing a diversity-guided genetic algorithm with a new mutation scheme that is capable of exploring the unseen regions of the search space, as well as exploiting the already-found promising elements. The proposed mutation operator specifies different mutation rates for different sites of an encoded solution. These site-specific rates are carefully derived based on the underlying pattern of highly-fit solutions, adjusted to every single individual, and adapted throughout the evolution to retain a good ratio between exploration and exploitation. Furthermore, in order to more directly monitor the exploration vs. exploitation balance, the proposed method is augmented with a diversity control process assuring that the search process does not lose the required balance between the two forces.

This paper is concerned with proposing an elitist genetic algorithm which makes use of a new mutation scheme aimed to tackle both explorative and exploitative responsibilities of genetic operators. The proposed mutation scheme follows an approach similar to motif representation in biology, to derive the underlying pattern of highly-fit solutions discovered so far. This pattern is then used to derive mutation rates specified for every site along the encoded solutions. The site-specific rates are amended for every individual to balance the required explorative and exploitative power. The Markov chain model of the proposed method is also derived and used to analyze its convergence properties.

This work is concerned with proposing a robust framework for optimizing operator rates of simple Genetic Algorithms (GAs) during a GA run. The suggested framework is built upon a formerly proposed GA Markov chain model to estimate the optimal values of the operator rates based on the time and the current state of the evolution. Though the proposed framework has been formalized for optimizing both mutation and crossover rates, in the current paper, we only implemented it as the mutation rate optimizer and kept the crossover rate constant. To demonstrate the efficacy of the proposed algorithm, the method is evaluated using a set of benchmark problems and the outcome is compared with a series of well-known relevant algorithms. The results demonstrate that the newly suggested algorithm significantly outperforms its rivals.

It is known that a k-term DNF can have at most $2^k - 1$ prime implicants and that this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a nonrepeating decision tree with literals assigned to the leaves in a certain way. We also mention some related results and open problems.

The theory revision, or concept revision, problem is to correct a given, roughly correct concept. Given the representation of an initial concept, one would like to obtain a representation of the target concept by applying revisions, that is, syntactic modifications such as the deletion of a variable or a term. We give efficient revision algorithms using membership and equivalence queries for 2term monotone DNF, monotone k-DNF, and readonce formulas. An example is given showing that some monotone DNF formulas cannot be revised efficiently. These results all assume that the revisions allowed are the replacements of a variable occurrence with a constant, which, for DNFs, corresponds to deletions of variables and terms. We also discuss a more general error model where besides deletions, additions are also allowed. 1 INTRODUCTION What the computational learning theory community calls a concept is often referred to as a theory elsewhere in artificial intelligence and logic....

Article Learning atomic formulas with prescribed properties Share on Authors: Irene Tsapara Department of MSCS, University of Illinois at Chicago, 851 S.Morgan, M/C 249, Chicago, IL Department of MSCS, University of Illinois at Chicago, 851 S.Morgan, M/C 249, Chicago, ILView Profile , György Turán Department of MSCS, University of Illinois at Chicago, 851 S.Morgan, M/C 249, Chicago, IL Department of MSCS, University of Illinois at Chicago, 851 S.Morgan, M/C 249, Chicago, ILView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 166–174https://doi.org/10.1145/279943.279978Online:24 July 1998Publication History 1citation143DownloadsMetricsTotal Citations1Total Downloads143Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Learning logic programs by using the product homomorphism method Share on Authors: Tamás Horváth Dept. of Applied Informatics, József A. University, H-6720 Szeged, Hungary Dept. of Applied Informatics, József A. University, H-6720 Szeged, HungaryView Profile , Robert H. Sloan Dept. of EE & Comp. Sci., U. Illinois at Chicago, 851 S. Morgan St. Rm 1120, Chicago, IL Dept. of EE & Comp. Sci., U. Illinois at Chicago, 851 S. Morgan St. Rm 1120, Chicago, ILView Profile , György Turán Dept. of Math., Stat., & Comp. Sci., U. Illinois at Chicago, Research Group on Artificial Intelligence, Hungarian Academy of Sciences Dept. of Math., Stat., & Comp. Sci., U. Illinois at Chicago, Research Group on Artificial Intelligence, Hungarian Academy of SciencesView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 10–20https://doi.org/10.1145/267460.267468Online:01 July 1997Publication History 6citation217DownloadsMetricsTotal Citations6Total Downloads217Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We investigate learning with membership and equivalence queries assuming that the information provided to the learner is incomplete. By incomplete we mean that some of the membership queries may be answered by “I don't know.” This model is a worst-case version of the incomplete membership query model of Angluin and Slonim. It attempts to model practical learning situations, including an experiment of Lang and Baum that we describe, where the teacher may be unable to answer reliably some queries that are critical for the learning algorithm.

We consider the complexity of computing Boolean functions by analog circuits of bounded fan-in, i.e. by circuits of gates computing real-valued functions, either exactly or as a sign-representation. Sharp upper bounds are obtained for the complexity of the most difficult n-variable function over certain bases (sign-representation by arithmetic circuits and exact computation by piecewise linear circuits). Bounds are given for the computational power gained by adding discontinuous gate functions and nondeterminism. We also prove explicit nonlinear lower bounds for the formula size of analog circuits over bases containing addition, subtraction, multiplication, the sign function and all real constants.>

Article Free Access Share on Lower bounds for PAC learning with queries Author: György Turán View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 384–391https://doi.org/10.1145/168304.168382Published:01 August 1993Publication History 8citation255DownloadsMetricsTotal Citations8Total Downloads255Last 12 Months35Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

It is shown that for any concept class C the number of equivalence and membership queries that are needed to learn C is bounded from below by Omega (VC-dimension(C)). Furthermore, it is shown that the required number of equivalence and membership queries is also bounded from below by Omega (LC-ARB(C)/log(1+LC-ARB(C))), where LC-ARB(C) is the required number of steps in a different model where no membership queries but equivalence queries with arbitrary subsets of the domain are permitted. These two relationships are the only relationships between the learning complexities of the common online learning models and the related combinatorial parameters that have remained open. As an application of the first lower bound, the number of equivalence and membership queries that are needed to learn monomials of k out of n variables is determined. Learning algorithms for threshold gates that are based on equivalence queries are examined. It is shown that a threshold gate can learn not only concepts but also nondecreasing functions in polynomially many steps.>

The complexity of learning concepts belonging to various concrete concept classes C contained in 2/sup X/ over a finite domain X is analyzed in terms of the number of counterexamples that are needed in the worst case. It turns out that for many interesting concept classes there exist exponential differences between the number of counterexamples that are required by a 'naive' learning algorithm for C (e.g. one that always outputs the minimal consistent hypothesis) and a 'smart' learning algorithm for C, which attempts to make a more sophisticated prediction. theta (log n) bounds are given for the number of counterexamples that are required for learning boxes, balls, and halfspaces in a d-dimensional discrete space X=(1, . . ., n)/sup d/ (for every finite dimension d). Also given are an upper bound of O(d/sup 3/) and a lower bound of Omega (d/sup 2/) for the complexity of learning a threshold function with d input bits (i.e. X=(0, 1)/sup d/). For each of these concept classes one can give learning algorithms that are both optimal (or close to optimal in the case of threshold functions) with regard to the number of counterexamples which they require and computationally feasible. The complexity of learning the concept classes on several variations of the learning model considered is determined. The relationship between these learning models and some related combinatorial invariants is clarified.>

We prove θ(n log n) bounds for the deterministic 2-way communication complexity of the graph properties CONNECTIVITY, s-t-CONNECTIVITY and BIPARTITENESS (for arbitrary partitions of the variables into two sets of equal size). The proofs are based on combinatorial results of Dowling-Wilson and Lovász-Saks about partition matrices using the Möbius function, and the Regularity Lemma of Szemerédi. The bounds imply improved lower bounds for the VLSI complexity of these decision problems and sharp bounds for a generalized decision tree model which is related to the notion of evasiveness.

How many questions are needed to decide whether an unknown ordered set is isomorphic to a fixed ordered set $P_0 $? This recognition problem is considered, together with some related computational problems concerning ordered sets.

We examine a powerful model of parallel computation: polynomial size threshold circuits of bounded depth (the gates compute threshold functions with polynomial weights). Lower bounds are given to separate polynomial size threshold circuits of depth 2 from polynomial size threshold circuits of depth 3, and from probabilistic polynomial size threshold circuits of depth 2. We also consider circuits of unreliable threshold gates, circuits of imprecise threshold gates and threshold quantifiers.

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

Linial and Saks [2] have shown that $O(\log N)$ evaluations of an order preserving map $f:p \to \mathbb{R}$ are necessary and sufficient to determine whether $\alpha \in f(P)$, where N is the number of ideals of N and $\alpha \in \mathbb{R}$ is a given real number. In this paper, we investigate the problem of how to perform the evaluations so that Linial and Saks’ bound is guaranteed, and solve the problem for the classes of interval and series-parallel orders and hence, in particular, for rooted trees. We observe that the greedy-type binary search algorithm, which is optimal for chains, already need not be optimal for general rooted trees. We furthermore discuss the computational complexity of the general search problem and obtain results indicating that the general problem might be hard.