Technical Report Series in Neural and Computational Learning

[John Shawe-Taylor]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT): three new reports available

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-015:
----------------------------------------
Computability and complexity over the reals
by Paolo Boldi, University of Milan

Abstract:
In this work, we sketch a (rather superficial) survey about the problem of
extending some of the classical notions from computation and complexity theory
to the non-classical realm of real numbers.  We first present an algorithmic
approach, deeply studied by Blum, Shub, Smale et al., and give a non-trivial
separation result recently obtained by Cucker.  Then, we introduce some concepts
from another line of research, namely the one based on the notion of computable
real number.  

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-016:
----------------------------------------
Probably Approximately Optimal Satisficing Strategies
by Russell Greiner, Siemens Corporate Research
   Pekka Orponen, Department of Computer Science, University of Helsinki

Abstract:
A {\em satisficing search problem} consists of a set of probabilistic
experiments to be performed in some order, seeking a satisfying
configuration of successes and failures.  The expected cost of the search
depends both on the success probabilities of the individual experiments,
and on the {\em search strategy}, which specifies the order in which the
experiments are to be performed.  A strategy that minimizes the expected
cost is {\em optimal}.  Earlier work has provided ``optimizing functions''
that compute optimal strategies for certain classes of search problems from
the success probabilities of the individual experiments.  We extend those
results by providing a general model of such strategies, and an algorithm
\pao\ that identifies an approximately optimal strategy when the
probability values are not known.  The algorithm first estimates the
relevant probabilities from a number of trials of each undetermined
experiment, and then uses these estimates, and the proper optimizing
function, to identify a strategy whose cost is, with high probability,
close to optimal.  We also show that if the search problem can be
formulated as an and-or tree, then the PAO algorithm can also ``learn
while doing'', i.e. gather the necessary statistics while performing the
search.  


----------------------------------------
NeuroCOLT Technical Report NC-TR-95-018:
----------------------------------------
On real Turing machines that toss coins
by  Felipe Cucker, Universitat Pompeu Fabra,
    Marek Karpinski, Universit\"at Bonn,
    Pascal Koiran, DIMACS, Rutgers University,
    Thomas Lickteig, Universit\"at Bonn,
    Kai Werther, Universit\"at Bonn

Abstract:
In this paper we consider real counterparts of classical probabilistic
complexity classes in the framework of real Turing machines as
introduced by Blum, Shub, and Smale \cite{BSS}.  We give an extension
of the well-known ``$\BPP \subseteq \P/\poly$'' result from discrete
complexity theory to a very general setting in the real number model.
This result holds for real inputs, real outputs, and random elements
drawn from an arbitrary probability distribution over~$\R^m$. Then we
turn to the study of Boolean parts, that is, classes of languages of
zero-one vectors accepted by real machines.  In particular we show that
the classes $\BPP$, $\PP$, $\PH$, and $\PSPACE$ are not enlarged by
allowing the use of real constants and arithmetic at unit cost provided
we restrict branching to equality tests.



-----------------------
The Report NC-TR-95-015 can be accessed and printed as follows 

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-95-015.ps.Z
ftp> bye
% zcat nc-tr-95-015.ps.Z | lpr -l

Similarly for the other technical report.

Uncompressed versions of the postscript files have also been
left for anyone not having an uncompress facility.

A full list of the currently available Technical Reports in the 
Series is held in a file `abstracts' in the same directory.

The files may also be accessed via WWW starting from the NeuroCOLT homepage:

http://www.dcs.rhbnc.ac.uk/neurocolt.html


Best wishes
John Shawe-Taylor