Implementation of Kernel Information-Theoretic Metric Learning proposed by V.Davis et al.

kitml.py

import numpy as np

def KernelITML(K,constraints,dm=None,dc=None,gamma=1.0,max_iter=1000,stop_threshold=1e-3):
    """
    K: initial kernel matrix.
    constraints: array or list whose element is in the form of (delta,i,j), where delta=1 if (i,j) is must-link and delta=-1 if (i,j) is cannot-link.
    dm: target distance for must-link. if not provided, dm is automatically selected.
    dc: target distance for cannot-link.
    gamma: trade-off parameter. gamma=1 gives stable solution. 
    max_iter: maximum number of iteration. 
    """
    if dm is None:
        Kdiag=np.c_[np.diag(K)]
        Kdist2=Kdiag+Kdiag.T-2*K
        dm=np.percentile(Kdist2,1)
    if dc is None:
        dc=np.percentile(Kdist2,99)
    print dm,dc
    Xi={}; Lambda={};
    for iteration in xrange(max_iter):
        Kold=K.copy()
        updates=0. # the number of updates. this should converge to 0
        for delta,i,j in constraints:
            p=K[i,i]+K[j,j]-2*K[i,j]
            if delta==1:
                Xi.setdefault((i,j),dm);
                if p<=Xi[(i,j)]: # if the must-link constraint is already satisfied
                    continue
            else:
                Xi.setdefault((i,j),dc);
                if p>=Xi[(i,j)]: # if the cannot-link constraint is already satisfied
                    continue
            Lambda.setdefault((i,j),0.)
            if p==0: 
                continue
            alpha=min(Lambda[(i,j)],(delta/2.)*(1./p-gamma/Xi[(i,j)]))
            if alpha==0:
                continue
            updates+=1
            beta=(delta*alpha)/(1.-delta*alpha*p)
            Xi[(i,j)]=(gamma*Xi[(i,j)])/(gamma+delta*alpha*Xi[(i,j)])
            Lambda[(i,j)]=Lambda[(i,j)]-alpha
            ki=np.c_[K[:,i]]
            kj=np.c_[K[:,j]]
            K=K+beta*(ki-kj).dot((ki-kj).T)
        print "number of updates:",updates
        diff=np.sqrt(np.sum((K-Kold)**2))
        print diff
        if diff<stop_threshold:
            print "converged at {0} steps".format(iteration)
            break
    return K