In the field of neuroevolution (NE), evolutionary algorithms are used to update the weights, biases and topologies of artificial neural networks (ANNs). A recent theoretical work presented the first runtime analysis of NE in a simple setting, considering a single neuron and intuitive benchmark function classes. However, this work was limited by the unrealistic settings with regard to activation functions and fitness measurements.

We consider a simple setting in neuroevolution where an evolutionary algorithm optimizes the weights and activation functions of a simple artificial neural network. We then define simple example functions to be learned by the network and conduct rigorous runtime analyses for networks with a single neuron and for a more advanced structure with several neurons and two layers. Our results show that the proposed algorithm is generally efficient on two example problems designed for one neuron and efficient with at least constant probability on the example problem for a two-layer network. In particular, the so-called harmonic mutation operator choosing steps of size j with probability proportional to 1/j turns out as a good choice for the underlying search space. However, for the case of one neuron, we also identify situations with hard-to-overcome local optima. Experimental investigations of our neu-roevolutionary algorithm and a state-of-the-art CMA-ES support the theoretical findings.

In this paper, we prove various results about PAC learning in the presence of malicious noise. Our main interest is the sample size behavior of learning algorithms. We prove the first nontrivial sample complexity lower bound in this model by showing that order of ε/Δ 2 + d /Δ (up to logarithmic factors) examples are necessary for PAC learning any target class of {0,1}-valued functions of VC dimension d , where ε is the desired accuracy and η = ε/(1 + ε) - Δ the malicious noise rate (it is well known that any nontrivial target class cannot be PAC learned with accuracy ε and malicious noise rate η ≥ ε/(1 + ε), this irrespective to sample complexity). We also show that this result cannot be significantly improved in general by presenting efficient learning algorithms for the class of all subsets of d elements and the class of unions of at most d intervals on the real line. This is especialy interesting as we can also show that the popular minimum disagreement strategy needs samples of size d ε/Δ 2 , hence is not optimal with respect to sample size. We then discuss the use of randomized hypotheses. For these the bound ε/(1 + ε) on the noise rate is no longer true and is replaced by 2ε/(1 + 2ε). In fact, we present a generic algorithm using randomized hypotheses that can tolerate noise rates slightly larger than ε/(1 + ε) while using samples of size d /ε as in the noise-free case. Again one observes a quadratic powerlaw (in this case d ε/Δ 2 , Δ = 2ε/(1 + 2ε) - η) as Δ goes to zero. We show upper and lower bounds of this order.

As part of the EU-funded SAVIAH project, a regression-based methodology for mapping traffic-related air pollution was developed within a GIS environment. Mapping was carried out for NO2 in Amsterdam, Huddersfield and Prague. In each centre, surveys of NO2, as a marker for traffic-related pollution, were conducted using passive diffusion tubes, exposed for four 2-week periods. A GIS was also established, containing data on monitored air pollution levels, road network, traffic volume, land cover, altitude and other, locally determined, features. Data from 80 of the monitoring sites were then used to construct a regression equation, on the basis of predictor environmental variables, and the resulting equation used to map air pollution across the study area. The accuracy of the map was then assessed by comparing predicted pollution levels with monitored levels at a range of independent reference sites. Results showed that the map produced extremely good predictions of monitored pollution levels, both for individual surveys and for the mean annual concentration, with r2 0.79-0.87 across 8-10 reference points, though the accuracy of predictions for individual survey periods was more variable. In Huddersfield and Amsterdam, further monitoring also showed that the pollution map provided reliable estimates of NO2 concentrations in the following year (r2 0.59-0.86 for n 20).

Permiaaion to make digital

In this paper we present a polynomial time algorithm for agnostic PAC-learning with convex handled and produces an empirically good hypothesis.

In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show that this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions, 2-term RSE, and 2-term-DNF, when the examples are generated by a random walk on {0,1}n.

In this paper, we investigate the problem of classifying objects which are given by feature vectors with Boolean or real entries. Our aim is to “(efficiently) learn probably almost optimal classifications” from examples. A classical approach in pattern recognition uses empirical estimations of the Bayesian discriminant functions for this purpose. We analyze this approach for different classes of distribution functions: In the Boolean case we look at the k-th order Bahadur-Lazarsfeld expansions and k-th order Chow expansions and in the continuous case at the class of normal distributions. In all cases, we obtain polynomial upper bounds for the required sample size. The bounds for the Boolean case improve and extend results from [FPS91].

The problem of learning ring-sum-expansions from examples is studied. Ring-sum-expansions (RSE) are representations of Boolean functions over the base $\{ \wedge , \oplus ,1 \}$, which reflect arithmetic operations in $GF(2)$. k-RSE is the class of ring-sum-expansions containing only monomials of length at most k. k-term is the class of ring-sum-expansions having at most k monomials. It is shown that k-RSE, $k \geq 1$, is learnable while k-term-RSE, $k \geq 2$, is not learnable if $RP \ne NP$. Without using a complexity-theoretical hypothesis, it is proven that k-RSE, $k \geq 1$, and k-term-RSE, $k \geq 2$ cannot be learned from positive (negative) examples alone. However, if the restriction that the hypothesis which is output by the learning algorithm is also a k-RSE is suspended, then k-RSE is learnable from positive (negative) examples only. Moreover, it is proved that 2-term is learnable by a conjunction of a 2-CNF and a 1-DNF. Finally the paper presents learning (on-line prediction) algorithms for k-RSE that are optimal with respect to the sample size (worst case mistake bound).

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees. In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).