Evolving Explanatory Novel Patterns for Semantically-Based Text Mining - Natural Language Processing and Text Mining - page 153

feature of SPEA is that in order to create niches, this does not define a neighbor-
hood by means of a distance metric on the genotypic or phenotypic space. Instead,
the classes of solutions are grouped according to the results of a clustering method
which uses the vector of objective functions of the individuals, and not the individ-
uals themselves.
Once the offspring is produced, the population update is performed using a
steady-state strategy. Here, each individual from a small number of the worst hy-
potheses is replaced by an individual from the offspring only if the latter are better
than the former.
For semantic constraints, judgements of similarity between hypotheses or compo-
nents of hypotheses (i.e., predicates, arguments, etc.) are carried out using the LSA
training data and predicate-level information previously discussed in the training
step.

Hypothesis Discovery

Using the semantic measure above and additional constraints discussed later on, we
propose new operations to allow guided discovery such that unrelated new knowledge
is avoided, as follows:

• Selection: selects a small number of the best parent hypotheses of every gen-

eration ( Generation Gap ) according to their fitness. Note that the notion of
optimum (and best ) is different here as there is more than one objective to be
traded off. Accordingly, this is usually referred to as a “Pareto Optimum” [29].
Assuming a minimization problem (i.e., “worse” involves smaller values), a de-
cision vector (i.e., vector of several objectives) is a Pareto optimal if there exists
no feasible vector which would increase some objective without causing a si-
multaneous decrease in at least one other objective. Unfortunately, this concept
almost always gives not a single solution, but rather a set of solutions called
the Pareto Optimal set . The decision vectors corresponding to the solutions in-
cluded in the Pareto optimal set are called non-dominated, and the space of the
objective functions whose nondominated vectors are in the Pareto optimal set is
called the Pareto front [4, 5, 11].

• Crossover: a simple recombination of both hypotheses' conditions and conclu-

sions takes place, where two individuals swap their conditions to produce new
offspring (the conclusions remain).
Under normal circumstances, crossover works on random parents and positions
where their parts should be exchanged. However, in our case this operation must
be restricted to preserve semantic coherence. We use soft semantic constraints
to define two kinds of recombinations:
a) Swanson's Crossover: based on Swanson's hypothesis [30, 31] we propose a
recombination operation as follows:
If there is a hypothesis (AB) such that “IF A THEN B” and another one
(BC) such that “IF B' THEN C,” (B' being something semantically similar
to B) then a new interesting hypothesis “IF A THEN C” can be inferred
via LSA if the conclusions of AB have high semantic similarity with the
conditions of hypothesis BC.
The above principle can be seen in Swanson's crossover between two learned
hypotheses as shown in figure 9.2