\appendix
\chapter{Glossary and Definitions}\label{ch:gloss}

Definitions of the key terms appearing in the thesis.

\begin{itemize}

\item {\bf Clustering} is an unsupervised learning technique used for
discovering patterns in unlabeled data. For example, it might reveal that 
a set of data is well described by three distinct clouds of points. Clustering
is often used for dimension reduction whereby complex data is understood in
terms of simpler objects with only a slight loss in accuracy.
Clustering techniques apply when there is no class to be predicated but
rather when the instances are to be divided into natural groups. These clusters
presumably reflect some mechanism at work in the domain from which instances
are drawn, a mechanism that causes some instances to bear a stronger resemblance
to one another than they do to the remaining instances. There are a number of
different clustering techniques and among those most widely used ones are: 
the classic {\it k}-means algorithm, which forms clusters in numeric domains, and 
partitioning instances into disjoint clusters. The second is an incremental 
technique that was developed in the late 1980s and is embodied in a pair 
of clustering systems. The third is a statistical clustering method based
on a {\it mixture model} of different probability distributions, one for each
cluster, which assigns instances to classes probabilistically, not 
deterministically.

\item {\bf Decision Problem} is a search problem in which we wish to
know the answer to a simple yes/no question. The question is usually
of the form ``Does there exists a configuration $\sigma \in \Sigma$
such that property $P$ holds for system $X$?''. For example, for a
given traveling salesman problem, ``Does there exist a solution with
total length less than 1200 miles?'' -- see also optimization problem.

\item {\bf Entropy} is a mathematical measure of the amount of disorder
in a system.

\item {\bf Equilibrium} is used differently by experts in different
fields. For example, physicists tend to use equilibrium to mean a
fixed-point of the system's dynamics (perhaps in a statistical sense)
whether a stable or unstable. In this thesis, we use ``steady-state
equilibrium'' or ``static equilibrium'' to mean a fixed-point. Then a
``dynamic equilibrium'' subsumes that definition into a larger class
which includes cyclic states. Note that by examining, for example,
higher iterates of a map, or an average over time, many dynamical
equilibria can be considered static equilibria of a derived
system. However, that derived system does not necessarily retain all
the interesting characteristics of the original.
In the process of annealing, how do we test for equilibrium?  that is, 
at which temperature should we test for equilibrium? 
So, for example, if we start with ``sufficiently high'' starting
temperatures, can we infer that these also are the lowest initial
temperatures for which equilibrium can be reached? One difficulty in
determining this is that equilibrium might not be reached at the
starting temperature itself. But if the following temperatures are
very close to it, annealing might make several times as many moves at
what is in effect the same temperature, and might then reach
equilibrium! In general, we don't have a satisfactory answer to this
issue. 

What should really be tested is whether equilibrium is reached at any
of the temperatures near the starting temperature, but this means
making many tests for equilibrium instead of one.
Another related but more general issue to check for is whether a
cooling schedule may reach equilibrium even if a single generation of
it does not.

\item {\bf Evolutionary Algorithms} (EAs) are based upon the theory of 
evolution by natural selection -- a population of candidate solutions
maintained, and allowed to ``evolve''. The three main styles of EA
exist: Genetic Algorithms, Evolutionary Programming, and Evolution
Strategies -- but the basic idea behind them is the same and the
difference can be considered historical.

\item {\bf Fitness Function} is a mathematical
equation that describes the relative value of each member of a family
of objects with respect to some criterion. The fitness function is
maximized or minimized (depending upon the criterion) to find the best
object in the family.

\item {\bf Fitness Landscape} were first introduced in the 30's in the 
context of evolutionary theory, and have proven to be a powerful tool
for the investigation of optimization dynamics in many fields. 
A fitness landscape is a particular kind of representation of a large
space of ``configurations''. For example, this space could be ``The
space of all possible routes through 100 given cities'' or ``The space
of all possible genotypes of a given length''. A fitness landscape
requires both a {\it fitness function} assigning a value (usually in
real numbers) to each {\it configuration}, and a {\it neighborhood
relation} amongst the configurations.

\item {\bf Fixed-point} of a map $f : X \rightarrow X$ is a point $x
\in X$ such that $f(x) = x$. Fixed-points can then be further
categorized as stable, unstable, meta-stable, etc.

\item {\bf Hypercube} is an n-dimensional cube whose vertices have
coordinates ($d_1,\ldots , d_n$) with $d_j = 0$ or $1$. Moreover, two
vertices of this cube are called {\it adjacent} if they differ in
exactly one coordinate. So we can have a set of $2^n$ numbers $x_0 \leq 
x_1 \leq \ldots \leq x_{2^{n} - 1}$ to be assigned to the $2^n$
vertices in such a way that $\Sigma_{i,j} |x_i - x_j|$ is minimized,
where the sum is over all $i$ and $j$ such that $x_i$ and $x_j$ have
been assigned to adjacent vertices.

\item {\bf K-satisfiability} (k-SAT) one of the earliest
standard NP-hard problems in computer science. Consider $N$ boolean
variables $x_1, x_2, \ldots, x_N$. A clause is formed by picking $k$
variables at random (with replacement) and considering the logical
disjunction (`or' operation) of either the variable $x_i$ or its
negation $\overline{x_i}$ (selected randomly with $50\%$ probabilities
for each variable in the clause) of $M$ such clauses (selected
independently). The search problem is to find a set of true/false
assignments to the $x_i$ such that the entire problem instance is true 
(which requires that each of the $M$ clauses is true).

\item {\bf Landscape Analysis} is a mathematical
process used to search for the best solution to a multi-variable
optimization problem. It utilizes a fitness function. Within the
search space (i.e., a plot of all the possible solutions), the fitness 
of a particular solution can be shown graphically as its height. The
resulting ``landscape'' will have peaks in the regions of the search
space that contain better solutions; further analysis of the peak
regions can be used to refine the results and achieve even more
precise solutions.

\item {\bf Mapping}\footnote{In his thesis~\cite{AH:mapping}, Heirich
talks about mapping in terms of the mapping problem and equates it
with the load balancing problem. Also he points out how similar both
problems are to a number of other problems, such as the problems of
partitioning circuits for VLSI placement and
simulation.}\footnote{In its simplistic form, the {\it mapping
problem} can be stated as follows: given a network graph $G_n =
<V_n,E_n>$ and a problem graph $G_p = <V_p,E_p>$, find a mapping $m:
V_p \rightarrow V_n$ that maximizes or minimizes some metric $E$.} in
its abstract form, is a functional representation from a Euclidean or a
non-Euclidean space onto another space of either type. Our reference
to `mapping' throughout the thesis would be in the context of
functional mapping of the representation of an optimization problem
onto a Euclidean space or a graphical structure, also behaving as a
search space for a solution to the problem, or acting itself as a
method for tackling the problem.

\item {\bf Mean-field theory} (MFT) 
is an approach for analyzing a system which may be non-ergodic 
(i.e. have a broken symmetry). The approach consists of three 
basic steps: (1) identify a parameter (the `order parameter') to 
characterize the broken symmetry; (2) assume most of
the system's behavior can be calculated from a given value of the
order parameter, and calculate how one small part would behave given
that choice for the rest of the system; (3) ensure self-consistency:
adjust the order-parameter until its value for the small part is
consistent with the assumed value for the system as a whole. This
procedure is understood to give a reasonably accurate qualitative
picture of the system, but with not-so-accurate quantitative
predictions of various exponents which characterize the system (for
that we turn to renormalization group techniques, or replica
trick). Why? This is mainly because a mean-field theory is usually a
phenomenological approximation rather than a real mathematical
approximation of a given distribution. However, it can usually be
shown to be valid and accurate in some limit of high-dimension or many 
degrees of freedom, etc.

\item {\bf Mean-field annealing} (MFA)
is an approximation method with principles from the well-known
approximation method in the field of statistical physics, and that is
the mean field approximation. The theory is concerned with systems of
spin elements that interact with each other in a magnetic
field. Conceptually, the mean field approximation replaces a spin
variable that occurs in an energy field by its expectation or mean
value when evaluating the probability distribution of any other
variable. This approximation allows the statistical mechanics of
complicated magnetic systems to be described by a closed set of
equations relating to the expected values of the variables. MFA
replaces the stochastic nature of simulated annealing with a set of
deterministic update rules that need to be solved iteratively. This
deterministic relaxation procedure exhibits fast convergence toward
the ``solution'' for complex optimization problems. MFA has received
great deal of attention in the field of artificial neural networks
(ANNs). In fact, some of the most important neural network models,
such as those of Hopfield and Tank, are closely related to the
principles of MFA.

\item {\bf Model}, {\bf System} to avoid any confusion, in this thesis 
we always use the term {\it system} to describe the `big'
picture. That is we study physical systems, optimizing systems,
$\ldots$ .Inside these systems, agents (or problem solvers) will have
{\it models} which they use to dictate their own behavior. Those
agents may use a discrete-choice model, a predictive model, a
least-squares learning model, $\ldots$. In this sense a model can be
considered an algorithm (which is the word we use when describing
explicitly those systems). For example, an agent on a landscape
optimizing via hill-climbing can be set to use a `hill-climbing model' 
to dictate its behavior, etc.

\item {\bf Multi-Objective Optimization} is the task of maximizing or
minimizing a number of criteria simultaneously. Multi-objective
optimization is more difficult than most kinds of optimization
problems because the trade-offs between the multiple objectives may
be unknown. 

\item {\bf Optimization problem} is a search problem in which we wish to 
know, in some given domain, the minimal (or maximal) value of a given
function. E.g. find $min_{\sigma \in \Sigma} f(\sigma)$, where $f:
\Sigma \rightarrow {\cal R}$.

\item {\bf Pareto Optimality} is that in multi-objective optimization,
the trade-offs between the multiple objectives are often unknown. A Pareto 
optimal solution is one that cannot be improved with respect to any one
objective; thus a compromise is reached between the various objectives.

\item {\bf Phase transition} is, loosely, a qualitative change in
behavior resulting from the smooth variation of a parameter. For
example as we reduce the temperature, water undergoes a phase
transition when it freezes: change from water into ice.

\item {\bf Renormalization group} (RG) is a mathematical approach for
analyzing systems, especially near critical points, which are
approximately self-similar. It proceeds by integrating out all the
details smaller than a given size, and then changing the system's
scale until the transformed system is close to the original. By
relating the characteristics of the system under such a
transformation, or considering the limit of an infinite number of
iterations of the above process, RG techniques have been able to
predict critical exponents of many systems to great accuracy, and
calculate how they must be adjusted for systems of finite size. The
theory also explains why many such exponents are universal; that is
only depending on a few global properties of the system (for instance, 
dimension of the order parameter), and not the local details. Note
that strictly speaking RG forms a semi-group, not a full group.

\item {\bf Replica trick} (RT) is the use of the identity
$\overline{log Z} = \lim_{n \rightarrow n} {\overline{Z^{n} - 1} \over
n}$ under non-rigorous (or at least questionable) circumstances to
calculate the $log Z$ average by analytic continuation of an
expression for $Z^n$ for integral $n$.

\item {\bf Ruggedness} is a heuristic measure of the character of a
fitness landscape. If used rigorously then it is inversely related to
the average correlation length of a sequence of steps on the
landscape. It is very hard to search effectively on a rugged
landscape, as compared with smooth one. This is simply because on a
rugged/uncorrelated landscape local information is of little use in
predicting global trends (and hence locating optima in the
landscape). 
\item {\bf Simulated Annealing} (SA) is a mathematical technique for general
optimization problems. The same comes from the physical process of
annealing, during which a material is first heated and then slowly
cooled. During annealing, the component atoms of a material are
allowed to settle into a lower energy state so that a more stable
arrangement of atoms is maintained throughout the cooling process. SA
has been applied with success to a wide variety of optimization tasks.

\item {\bf Spin Glass} is a simplified model from
physics describing dilute magnetic alloys. It defines an energy
function (or equivalently a fitness function) over tiny magnetic
dipoles called spins. Spins may point either up (+1) or down (-1). 
For every configuration of spins (e.g., +1-1+1+1-1 for a configuration
of 5 spins), the energy function assigns that configuration's energy
by summing up the interactions between spins. Many aspects of spin 
glasses are utilized by physicists and they comprise a well-understood 
family of fitness landscapes.


\end{itemize}




