edu.iu.pcl.absurdist.penalty
Class PenaltyMinimizer

java.lang.Object
  |
  +--edu.iu.pcl.absurdist.penalty.PenaltyMinimizer

All Implemented Interfaces:

SystemMatcher

public class PenaltyMinimizer

extends java.lang.Object

implements SystemMatcher

This algorithm tries to compute the correspondence between two concept systems that minimizes a certain penalty function. The penalty function is constructed so that there is a penalty imposed whenever there is a correspondence between node a in the first concept system and node x in the second concept system, and a correspondence between node b and node y, while the relationship between a and b in the first system is not identical to the relationship between x and y in the second system.

The penalty function is defined as a function of a correspondence matrix C as follows:

Penalty(C) = MatchingPenalty(C) + kappa * NormalizationPenalty(C)

Here, MatchingPenalty(C) is designed as to minimize the degree of mismatch between the structures of the graphs (i.e., for two graphs that are isomorphic, the absolute minimum of MatchingPenalty(C)=0 will be reached on a correspondence matrix C where C(a,x)!=0 only on pairs (a,x)=(a,f(a)) for some isomorphism f). NormalizationPenalty(C) is designed to be zero on a matrix C for which the values in each row and each column sum to 1. (Or to sqrt(m/n) and sqrt(n/m), respectively, if the two systems have a different number of nodes). Namely,

MatchingPenalty(C) = 
  = K1 * sum_{a,b,x,y: linked(a,b) & !linked(x,y)}{ C(a,x)*C(b,y)} +
  + K1 * sum_{a,b,x,y: !linked(a,b) & linked(x,y)}{ C(a,x)*C(b,y)} +
  + K2 * sum_{a,x,y:  !linked(x,y)}{ C(a,x)*C(a,y)} +
  + K2 * sum_{a,b,x:  !linked(a,b)}{ C(a,x)*C(b,x)} +
  + K3 * sum_{a,x,y:  linked(x,y)}{ C(a,x)*C(a,y)} +
  + K3 * sum_{a,b,x:  linked(a,b)}{ C(a,x)*C(b,x)}.

Thus, K1 is the penalty for matching a pair of linked nodes to a pair of non-linked nodes, or vice versa; K2 is the penalty for matching a single node to two non-linked nodes, or vice versa; and K3 is the penalty for matching a single node to two linked nodes, or vice versa.

NormalizationPenalty(C) =
   = sum_{a}{ (sum_{x}{C(a,x)} - sqrt(m/n))^2 } +
   + sum_{x}{ (sum_{a}{C(a,x)} - sqrt(n/m))^2 }.

The approach used in this method, that is, minimizing MatchingPenalty(C)+kappa*NormalizationPenalty(C) on the set of all matrices with non-negative coeffciients, is, really, a cludge, and may only produce an approximate solution. To obtain an exact solution, one would want to minimize MatchingPenalty(C) over the set of all matrices for which NormalizationPenalty(C)=0. But the latter would be a somewhat more complex quadratic-programming problem.

This program uses a very traditional fastest descent method, and works as follows:

1. We take an initial point C (a random matrix with positive
coefficients);

2. We compute the gradient of the penalty functional g; we
know that C is increases in the direction of vector g, and decreases
in the direction  of -g;

3. We obtain the "restricted" ascent vector v. v is based on g,
but if the current point C alread has some zero coefficients we
may replace the corresponding component of v with 0 to ensure that
going along the direction of -v won't make that component of C negative.

4. We solve the one-dimension minimization problem, finding the
real number xi that minimzes Penalty( C - xi * v), while C'=C-xi*v
still stays in the non-negative domain.

5. Assign C := C' = C - xi*v, and continue to step 2.

This program termiates after a specified number of iterations, or when it is detected that the penalty function cannot be noticeably reduced any more. (That is, when Penalty(C)-Penalty(C') is very small, or when v is almost zero).

The general outline of the code is based on that of Absurdist class, as it stood in April 2003.

See Also:

Absurdist

Field Summary

double	K1 K1 and K3 are the mapping penalty parameters.
double	K2 K1 and K3 are the mapping penalty parameters.
double	K3 K1 and K3 are the mapping penalty parameters.
double	kappa Kappa is the normzlization penalty parameter.

Constructor Summary

PenaltyMinimizer()

Method Summary

void	adjustCoeff()
void	evalMap() Computes the accuracy of the mapping.
double	evalMap2() An alternative way to evaluate the accuracy of the mapping.
void	findMapping() Finds the strongest valid correspondence as successful mappings.
void	iterateNet() Iterates, using the steepest descent method, to find a correspondence between two concept systems minimizing the penalty functional.
void	mapSystem(ConceptSystem systemO, ConceptSystem systemN) Maps orginal concept system to the one with added noise.
void	print(boolean toFile) Prints the original and noisy concept systems, the correspondence matrix, and the final mappings.
void	printCorrespond(java.io.PrintWriter out)
void	printMapping(java.io.PrintWriter out)
void	printMatrix(double[][] c, java.io.PrintWriter out)
void	printSystem(java.io.PrintWriter out)
void	setSystem(ConceptSystem systemO, ConceptSystem systemN)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

K1

public double K1

K1 and K3 are the mapping penalty parameters. In general, the elements of the penalty matrix are as follows:

            C(a,a)  C(a,b)  C(a,c)
   C(x,x)   0       K3      K2
   C(x,y)   K3      0       K1
   C(x,z)   K2      K1      0

Here, a is a node in the first graph; b is a node in the first graph linked to a; c is a node in the first graph NOT linked to a. Similarly, x is a node in the second graph; y is a node in the second graph linked to x; z is a node in the second graph NOT linked to x.

Thus, K1 is a penalty for mapping a pair of linked nodes to a pair of distinct but not lined nodes; K2 is a penalty for mapping a single node to two distinct, not linked nodes; and K3 is a penalty for mapping a single node to two distinct linked nodes.

However, in order to be able to construct an efficient implementation, we always have K1=K2. Thus, K1=K2 is a penalty for a mapping two

K2

public double K2

K1 and K3 are the mapping penalty parameters. In general, the elements of the penalty matrix are as follows:

            C(a,a)  C(a,b)  C(a,c)
   C(x,x)   0       K3      K2
   C(x,y)   K3      0       K1
   C(x,z)   K2      K1      0

Here, a is a node in the first graph; b is a node in the first graph linked to a; c is a node in the first graph NOT linked to a. Similarly, x is a node in the second graph; y is a node in the second graph linked to x; z is a node in the second graph NOT linked to x.

Thus, K1 is a penalty for mapping a pair of linked nodes to a pair of distinct but not lined nodes; K2 is a penalty for mapping a single node to two distinct, not linked nodes; and K3 is a penalty for mapping a single node to two distinct linked nodes.

However, in order to be able to construct an efficient implementation, we always have K1=K2. Thus, K1=K2 is a penalty for a mapping two

K3

public double K3

K1 and K3 are the mapping penalty parameters. In general, the elements of the penalty matrix are as follows:

            C(a,a)  C(a,b)  C(a,c)
   C(x,x)   0       K3      K2
   C(x,y)   K3      0       K1
   C(x,z)   K2      K1      0

Here, a is a node in the first graph; b is a node in the first graph linked to a; c is a node in the first graph NOT linked to a. Similarly, x is a node in the second graph; y is a node in the second graph linked to x; z is a node in the second graph NOT linked to x.

Thus, K1 is a penalty for mapping a pair of linked nodes to a pair of distinct but not lined nodes; K2 is a penalty for mapping a single node to two distinct, not linked nodes; and K3 is a penalty for mapping a single node to two distinct linked nodes.

However, in order to be able to construct an efficient implementation, we always have K1=K2. Thus, K1=K2 is a penalty for a mapping two

kappa

public double kappa

Kappa is the normzlization penalty parameter. The larger it is, the closer the solution will be to the "normalized-matrix plane", where the values in each row and each column of the matrix sums to 1.

Constructor Detail

PenaltyMinimizer

public PenaltyMinimizer()

Method Detail

setSystem

public void setSystem(ConceptSystem systemO,
                      ConceptSystem systemN)

adjustCoeff

public void adjustCoeff()

iterateNet

public void iterateNet()
                throws java.lang.Exception

Iterates, using the steepest descent method, to find a correspondence between two concept systems minimizing the penalty functional.

In practice, this methods often converges to a local minimum, rather than the global one, thus providing a poor quality match.

java.lang.Exception

findMapping

public void findMapping()

Finds the strongest valid correspondence as successful mappings.

evalMap

public void evalMap()

Computes the accuracy of the mapping.

evalMap2

public double evalMap2()

An alternative way to evaluate the accuracy of the mapping.

Returns:

The number that counts edges present in one graph in absent in its "image", and vice versa. This should be 0 is the mapping is a homomorphism, i.e. a perfect matching date: April-10-2003

mapSystem

public void mapSystem(ConceptSystem systemO,
                      ConceptSystem systemN)
               throws java.lang.Exception

Maps orginal concept system to the one with added noise.

Specified by:

mapSystem in interface SystemMatcher

Parameters:

systemO - The first concept system to match. In our experiments, this is the "original" one.

systemN - The second system to match. In our experiments, this system has been obtained from the first one by adding some "noise".

java.lang.Exception

printSystem

public void printSystem(java.io.PrintWriter out)
                 throws java.lang.Exception

java.lang.Exception

printCorrespond

public void printCorrespond(java.io.PrintWriter out)
                     throws java.lang.Exception

java.lang.Exception

printMatrix

public void printMatrix(double[][] c,
                        java.io.PrintWriter out)
                 throws java.lang.Exception

java.lang.Exception

printMapping

public void printMapping(java.io.PrintWriter out)
                  throws java.lang.Exception

java.lang.Exception

print

public void print(boolean toFile)
           throws java.lang.Exception

Prints the original and noisy concept systems, the correspondence matrix, and the final mappings.

Specified by:

print in interface SystemMatcher

java.lang.Exception