Suche nach Refinements auf der Basis von Bins

[mrapp-ke]

Als Teil von #226 muss eine Klasse implementiert werden, die nach dem besten Refinement einer Regel (für ein bestimmtes Feature) auf der Basis von Bins (der Datenstruktur aus #243) sucht.

Diese neue Klasse ApproximateRuleRefinementImpl (zu implementieren in boomer/common/cpp/rule_refinement.h/cpp) muss das Interface IRuleRefinement implementieren. Darauf ergibt sich folgendes Klassendiagram:

rule-refinement.zip

Wie im Klassendiagram zu sehen besitzt die neue Klasse ApproximateRuleRefinementImpl folgende Klassenattributte, die als Konstruktorargument übergeben werden:

• statistics_: Ein Pointer auf ein Objekt vom Typ AbstractStatistics, das zuvor mittels eines IHistogramBuilder erstellt wurde.
• binArray_: Ein Pointer auf ein struct vom Typ BinArray. Dieses struct existiert aktuell noch nicht.
• featureIndex_: Der Index des Features für das nach Refinements gesucht werden soll

Aktuell fehlt das struct BinArray noch. Es könnte folgendermaßen aussehen und sollte zu tuples.h hinzugefügt werden:

struct BinArray {
    uint32 numBins;
    Bin* bins;
};

Innerhalb der findRefinement-Methode muss über die Bins iteriert werden um mögliche Bedingungen zu evaluieren und letztendlich die beste Bedingung in Form eines structs vom Typ Refinement zurückzugeben. Als Pseudocode könnte das etwa folgendermaßen aussehen:

// Gesamtanzahl an verfügbaren Bins
numBins = binArray_->numBins;

// Lokale Variable um sich das beste Refinement zu merken
Refinement refinement;
// TODO Refinement initialisieren. Die Felder "indexedArray" und "indexedArrayWrapper" werden in Zukunft verschwinden, deshalb einfach auf NULL setzen

// Lokale Variable um sich den Head zu merken, der zum aktuell besten Refinement gehört
bestHead = currentHead;

// Erzeugt ein Objekt vom Typ `IStatisticsSubset`, das später an die `findHead`-Methode übergeben wird
// Indem man das Objekt in einen unique_ptr steckt, wird es automatisch deallokiert wenn diese Methode verlassen wird
std::unique_ptr<IStatisticsSubset> statisticsSubsetPtr;
statisticsSubsetPtr.reset(statistics_->createSubset(numLabelIndices, labelIndices));

// TODO Ersten Bin mit numExamples > 0 finden und `statisticsSubsetPtr.get()->addToSubset(r, 1)` aufrufen
r = // Index des gefundenen Bins
previousR = r;
previousValue = // maxValue des gefundenen Bins
numCoveredExamples = // numExamples des gefundenen Bins

// Über die verbleibenden Bins iterieren
for (r from r + 1 to numBins) {
    numExamples = // numExamples des aktuellen Bins

    if (numExamples > 0) { // Leere Bins ignorieren
        currentValue = // minValue des aktuellen Bins

        // Mögliche Bedingung mit Vergleichsoperator <= evaluieren
        currentHead = headRefinement->findHead(bestHead, refinement.head, labelIndices, statisticsSubsetPtr.get(), false, false)

        if (currentHead != NULL) {
            bestHead = currentHead
            refinement.comparator = LEQ
            refinement.threshold = (previousValue + currentValue) / 2.0
            refinement.start = 0  // Der Index des ersten Bin dessen Beispiele von der Bedingung abgedeckt werden
            refinement.end = r    // Der Index des letzten Bins dessen Beispiele abgedeckt werden (exklusiv)
            refinement.previous = previousR  // Der Index des letzten Bins mit numExamples > 0
            refinement.coveredWeights = numCoveredExamples  // Die Anzahl der Beispiele, die von der Bedingung abgedeckt werden
            refinement.covered = true
            // TODO Verbleibende Felder der Variable `refinement` aktualisieren
        }
        
        // Mögliche Bedinung mit Vergleichsoperator > evaluieren
        currentHead = headRefinement->findHead(bestHead, refinement.head, labelIndices, statisticsSubsetPtr.get(), true, false)

        if (currentHead != NULL) {
            bestHead = currentHead
            refinement.comparator = GR
            refinement.threshold = (previousValue + currentValue) / 2.0
            refinement.start = 0
            refinement.end = r
            refinement.previous = previousR
            refinement.coveredWeights = numCoveredExamples
            refinement.covered = false  // Zeigt an, dass die Bins in [refinement.start, refinement.end) NICHT abgedeckt werden, sondern alle verbleibenden Bins
            // TODO Verbleibende Felder der Variable `refinement` aktualisieren
        }

        previousValue = // maxValue des aktuellen Bins
        previousR = r
        numCoveredExamples += numExamples
        statisticsSubsetPtr.get()->addToSubset(r, 1)  // Markiert den aktuellen Bin als abgedeckt, jeder Bin hat ein Gewicht von 1
    }
}

return refinement

[LukasEberle]

Hallo,
ich weiß noch, dass es einen Grund gab einmal mit LEQ und einmal mit GR als Vergleichsoperator zu arbeiten. Aber ich bin mir nicht mehr sicher was das war. Kannst du mir das nochmal erklären?

[michael-rapp]

ich weiß noch, dass es einen Grund gab einmal mit LEQ und einmal mit GR als Vergleichsoperator zu arbeiten. Aber ich bin mir nicht mehr sicher was das war. Kannst du mir das nochmal erklären?

Stell dir vor du hast einige Beispiele (oder auch Bins), die nach einem bestimmten Feature sortiert sind. Wenn man jetzt eine neue Bedingung für dieses Feature finden will, dann geht man die Beispiele/Bins in der sortierten Reihenfolge durch und jeder Threshold zwischen zwei benachbarten Beispielen/Bins kommt im Frage um entweder eine Condition mit dem Operator <= (LEQ) oder > (GR) zu bilden. Der Grund warum man für jeden Threshold beide Fälle testet ist, dass eine Condition mit <= alle vorausgegangenen Beispiele (mit kleinerem Featurewert) abdeckt, während eine Condition mit > alle anderen Beispiele abdeckt. Würde man nur einen der beiden Fälle berücksichtigen, würde man die Hälfte der Möglichkeiten einfach ignorieren. Statt <= und > könnte man auch < und >= verwendet werden. Wichtig ist nur, dass sich die abgedeckten Bereiche nicht überlappen und die Vereinigung der Bereiche alle Beispiele umfasst.