Mise en œuvre efficace de l'information mutuelle en Java

Question

Je cherche à calculer l'information mutuelle entre deux caractéristiques, en utilisant Java.

J'ai lu Calcul de l'information mutuelle pour la sélection d'un ensemble d'entraînement en Java déjà, mais il s'agissait d'une discussion pour savoir si l'information mutuelle était appropriée pour le poster, avec seulement quelques pseudo-codes légers quant à l'implémentation.

Mon code actuel est ci-dessous, mais j'espère qu'il existe un moyen de l'optimiser, car j'ai de grandes quantités d'informations à traiter. Je suis conscient que le fait de faire appel à un autre langage/framework peut améliorer la vitesse, mais j'aimerais me concentrer sur la résolution de ce problème en Java pour le moment.

Toute aide est la bienvenue.

public static double calculateNewMutualInformation(double frequencyOfBoth, double frequencyOfLeft,
                                                   double frequencyOfRight, int noOfTransactions) {
    if (frequencyOfBoth == 0 || frequencyOfLeft == 0 || frequencyOfRight == 0)
        return 0;
    // supp = f11
    double supp = frequencyOfBoth / noOfTransactions; // P(x,y)
    double suppLeft = frequencyOfLeft / noOfTransactions; // P(x)
    double suppRight = frequencyOfRight / noOfTransactions; // P(y)
    double f10 = (suppLeft - supp); // P(x) - P(x,y)
    double f00 = (1 - suppRight) - f10; // (1-P(y)) - P(x,y)
    double f01 = (suppRight - supp); // P(y) - P(x,y)

    // -1 * ((P(x) * log(Px)) + ((1 - P(x)) * log(1-p(x)))
    double HX = -1 * ((suppLeft * MathUtils.logWithoutNaN(suppLeft)) + ((1 - suppLeft) * MathUtils.logWithoutNaN(1 - suppLeft)));
    // -1 * ((P(y) * log(Py)) + ((1 - P(y)) * log(1-p(y)))
    double HY = -1 * ((suppRight * MathUtils.logWithoutNaN(suppRight)) + ((1 - suppRight) * MathUtils.logWithoutNaN(1 - suppRight)));

    double one = (supp * MathUtils.logWithoutNaN(supp)); // P(x,y) * log(P(x,y))
    double two = (f10 * MathUtils.logWithoutNaN(f10)); 
    double three = (f01 * MathUtils.logWithoutNaN(f01));
    double four = (f00 * MathUtils.logWithoutNaN(f00));
    double HXY = -1 * (one + two + three + four);
    return (HX + HY - HXY) / (HX == 0 ? MathUtils.EPSILON : HX);
}        

public class MathUtils {
public static final double EPSILON = 0.000001;

public static double logWithoutNaN(double value) {
    if (value == 0) {
        return Math.log(EPSILON);
    } else if (value < 0) {
        return 0;
    }
    return Math.log(value);
}

Answer 1

Je ne suis pas mathématicien mais

Il y a juste un tas de calculs en virgule flottante ici. Un mathématicien pourrait être en mesure de réduire le nombre de calculs, essayez la méthode suivante Math SE .

Entre-temps, vous devriez être en mesure d'utiliser un static final double para Math.log(EPSILON)

Votre problème n'est peut-être pas un appel unique mais le volume de données pour lequel ce calcul doit être effectué. Ce problème sera mieux résolu si vous y ajoutez du matériel.

Answer 2

J'ai trouvé que la méthode suivante était rapide, mais je ne l'ai pas comparée à votre méthode - seulement à celle fournie dans weka .

Il fonctionne en partant du principe qu'il faut réorganiser l'équation MI de manière à minimiser le nombre d'opérations en virgule flottante :

Nous commençons par définir en tant que nombre/fréquence sur le nombre d'échantillons/transactions. Ainsi, nous définissons le nombre d'éléments comme n, le nombre de fois où x apparaît comme |x|, le nombre de fois où y apparaît comme |y| et le nombre de fois où ils apparaissent ensemble comme |x,y|. Nous obtenons alors ,

.

Maintenant, nous pouvons réorganiser cela en inversant le bas de la division interne, ce qui nous donne (n|x,y|)/(|x||y|). On peut aussi calculer en utilisant N = 1/n pour avoir une opération de division en moins. Ce qui nous donne :

Cela nous donne le code suivant :

/***
 * Computes MI between variables t and a. Assumes that a.length == t.length.
 * @param a candidate variable a
 * @param avals number of values a can take (max(a) == avals)
 * @param t target variable
 * @param tvals number of values a can take (max(t) == tvals)
 * @return 
 */
static double computeMI(int[] a, int avals, int[] t, int tvals) {
    double numinst = a.length;
    double oneovernuminst = 1/numinst;
    double sum = 0;

    // longs are required here because of big multiples in calculation
    long[][] crosscounts = new long[avals][tvals];
    long[] tcounts = new long[tvals];
    long[] acounts = new long[avals];
    // Compute counts for the two variables
    for (int i=0;i<a.length;i++) {
        int av = a[i];
        int tv = t[i];
        acounts[av]++;
        tcounts[tv]++;
        crosscounts[av][tv]++;
    }

    for (int tv=0;tv<tvals;tv++) {
        for (int av=0;av<avals;av++) {
            if (crosscounts[av][tv] != 0) {
                // Main fraction: (n|x,y|)/(|x||y|)
                double sumtmp = (numinst*crosscounts[av][tv])/(acounts[av]*tcounts[tv]);
                // Log bit (|x,y|/n) and update product
                sum += oneovernuminst*crosscounts[av][tv]*Math.log(sumtmp)*log2;
            }
        }

    }

    return sum;
}

Ce code suppose que les valeurs de a et t ne sont pas éparses (c'est-à-dire min(t)=0 et tvals=max(t)) pour qu'il soit efficace. Sinon (comme commenté), de grands tableaux inutiles sont créés.

Je pense que cette approche s'améliore encore lors du calcul de l'IM entre plusieurs variables à la fois (les opérations de comptage peuvent être condensées - notamment celle de la cible). L'implémentation que j'utilise est celle qui s'interface avec WEKA.

Enfin, il pourrait même être plus efficace de retirer le logarithme des sommations. Mais je ne sais pas si le log ou la puissance prendra plus de temps de calcul dans la boucle. Ceci est fait par :

1. Appliquer a*log(b) = log(a^b)
2. Déplacer le logarithme à l'extérieur des sommations, en utilisant log(a)+log(b) = log(ab)

et donne :