Theoretical Computer Science 348 (2005) 1 – 2
www.elsevier.com/locate/tcs

PrefaceThis special issue of Theoretical Computer Science consists of seven papers selected from the papers presented at the11th International Conference, Algorithmic Learning Theory, held in Sydney, Australia, December 2000. Preliminary
version of the papers appeared in Lecture Notes in Artiﬁcial Intelligence, vol. 1968. Following the conference, authors
were invited to submit full versions of their papers to the special issue. All the papers were subjected to the standard
refereeing procedure of Theoretical Computer Science.
Algorithmic learning theory aims at theoretical study of learning problems and algorithms by providing formal
models of learning and analyzing complexity of learning problems and performance of learning algorithms. It provides
foundations for such varied branches of artiﬁcial intelligence as machine learning, inductive logic programming, datamining, and others.
The ﬁrst paper, an invited paper by Watanabe, deals with sequential sampling algorithms for algorithmic learningtheory. In algorithmic learning theory, random sampling is a basic mean to estimate the proportion of instances witha certain property, and the estimation of the appropriate sample size is often essential to achieve efﬁcient learning.
Sequential sampling is a useful technique for designing adoptive sampling algorithms, which obtains instances one by
one and determines from these instances whether or not it has already seen enough number of examples for a giventask. Watanabe shows two typical sequential sampling algorithms for simple estimation problems, and explains whenand how such sequential sampling algorithms are used for designing learning algorithms with theoretically guaranteedperformance.
The next paper by Lange, Grieser and Zeugmann falls under the area of inductive inference and gives a systematic study of learning of indexable concept classes in which the ﬁnal hypothesis describes a ﬁnite variant of thetarget hypothesis. Various models are studied: learning in the limit, ﬁnite identiﬁcation, set-driven learning, conservative inference and behaviourally correct learning. For unbounded, but ﬁnite, number of errors, results shown
include the equivalence of set-driven, conservative and limit learning and behaviourally correct learning being strictly
more powerful than limit learning. This contrasts with the non-error case where limit learning and behaviourally
correct learning coincide, and limit and conservative learning separate for learning indexed families. The authors alsoestablish nice characterizations of the criteria of learning with unbounded (but ﬁnite) number of errors in terms ofﬁnite tell-tale sets.
The next paper by Nessel and Lange deals with the learnability of erasing pattern languages within Angluin’s modelof learning with queries. The type of queries considered include membership, subset, superset and equivalence queries(along with their restricted forms). The authors study, to what extent, the results for non-erasing pattern languages
and the subclass of (non-erasing) regular pattern languages carry over to the setting of erasing pattern languages. Theauthors also consider the situation in which additional information (in the form of a string from the target language) isavailable to the learner before starting the process of asking queries. It is shown that most of the results about learnabilityof regular pattern languages carry over to the case of erasing regular pattern languages. However, when the full class oferasing pattern languages is considered, some query types (membership/restricted superset queries) are not sufﬁcient
for learning.
The next paper by Satoh considers learning of taxonomic relations, where a taxonomy is represented by a treestructured concept hierarchy. Formalizing this problem as case-based reasoning problem with a taxonomy, the author
ﬁrst analyzes the representability of the case-based reasoning framework by showing upperbounds of necessary postiveand negative examples in the framework of PAC learning. Using the approximation method of ﬁnding a critical casebase, the author presents an efﬁcient algorithm that learns a minimal case-base from polynomially many random cases
0304-3975/$ - see front matter © 2005 Elsevier B.V. All rights reserved.
doi:10.1016/j.tcs.2005.09.002

2

Preface / Theoretical Computer Science 348 (2005) 1 – 2using polynomially many membership queries in terms of the DNS size and CNF size of a target relation. This result
solves an open problem on the learning complexity of case-based reasoning with taxonomic information.
The next paper by Denis, Gilleron and Letouzey considers learning from positive and unlabeled examples. In many
machine learning settings, getting labeled examples are difﬁcult, however unlabeled data is abundant. Also for someclassiﬁcation problems positive data are available. Many machine learning algorithms, such as decision tree induction
algorithms and naïve Bayes algorithms use examples only to evaluate statistical queries. Kearns designed the Statistical
Query learning model in order to describe such algorithms. In this paper authors design a scheme which transforms anySQ-like algorithm into an algorithm based on positive statistical queries and instance statistical queries. The authors
show that any class learnable in the Statistical Query model is learnable from positive statistical queries and instancestatistical queries only if a lower bound on the weight of any target concept f can be estimated in polynomial time. Then
this result is used to design a decision tree induction algorithm based on C4.5 that uses only positive and unlabeled
examples.
The ﬁnal two papers study the hardness of learning from examples. The paper by Hirata considers a learning
problem for acyclic conjunctive queries over relational databases from instances within the inductive logic programming
framework. Acyclicity is a natural concept in hypergraph theory, and proved to be effective to restrict the computational
complexity of many combinatorial problems in database area. This paper presents prediction hardness results forfragments of acyclic conjunctive queries with the model of PAC learning. First, the author shows under a standard
cryptographic assumption that acyclic conjunctive queries are not polynomial time predictable even if the maximum
arity of the predicates in a database is bounded by constant. Furthermore, it is shown that acyclic conjunctive queries
are as hard to predict as DNF formulas when the maximum arity is bounded by two. These results show a gap between
reasoning and learning of conjunctive queries in relational databases.
The paper by Dasgupta and Hammer considers efﬁcient learning of feedforward neural networks. The authors consider
the objective of maximizing the ratio of correctly classiﬁed points compared to the size of the training set. They show that
it is NP-hard to approximate the ratio within some constant relative error if architecture with varying input dimension,
one hidden layer and two hidden neurons are considered under some assumptions about the activation function. For
single hidden layer threshold networks with varying input dimension and n hidden neurons, approximation within arelative error depending on n is NP-hard even if restricted to situations where the number of examples is limited withrespect to n. Also, the objective of minimizing the failure ratio in the presence of misclassiﬁcation errors is considered,and some NP-hardness results have been obtained.
Due to unexpected problems this special issue appears with an unusual delay with respect to the event to which it isdevoted. We apologize to the authors and to TCS readers for this inconvenience but we are nevertheless pleased thatthe excellent papers selected for this issue are ﬁnally appearing. We would like to express our immense gratitude to all
the members of the ALT 2000 program committee for their careful selection of these papers, the anonymous referees
for their quick and constructive reviews, and the authors for their effort in improving the papers. Moreover, we are very
grateful to Giorgio Ausiello, the Editor-in-Chief of Theoretical Computer Science, for giving us a chance to edit thisspecial issue.
H. Arimura, S. Jain
Hokkaido University, Japan
E-mail addresses: arim@ist.hokudai.ac.jp (H. Arimura), sanjay@comp.nus.edu.sg (S. Jain)