Bewertung einer Gesamtlösung auf Basis dieser Teillösung noch besser werden kann als ein bereits berechneter oder vorab als Untergrenze geforderter Wert. Ist dies nicht der Fall, braucht man die entsprechenden Lösungen nicht mehr zu erzeugen und zu bewerten.

In ISSM wird die Berechnung der Interpretationen entsprechend einer Baumstruktur organisiert. Jeder Knoten repräsentiert eine Motivzuordnung und die Kanten die verschiedenen Möglichkeiten der Kombinationen von Zuordnungen. Die erste Ebene unter der Wurzel stellt die Zuordnung des ersten Motivs dar, darunter folgen die Verzweigungen zu den Zuordnungen des zweiten Motivs, dann die Zuordnung des dritten Motivs etc. In diesem Baum kann man für jede Zuordnung abschätzen, ob bei maximaler Bewertung der noch nicht zugeordneten Motive eine Verbesserung gegenüber der bisher besten Interpretation noch möglich ist. Sobald dies nicht mehr gegeben ist, kann man die Suche in diesem Zweig des Baums beenden, wie in Abbildung 10.2 dargestellt. Dadurch wird der Aufwand bei i Ebenen und Verzweigungsgrad t, entsprechend i und t - 1 Motiven in Eingabe und Vorgabe, im optimalen Fall von O(tⁱ) auf O(t ^. i) reduziert.

Welche Verbesserung tatsächlich erzielt wird, hängt bei diesem Verfahren vor allem von der Heuristik ab, d.h. in welcher Reihenfolge die Interpretationen bewertet werden. Je eher gute Ergebnisse gefunden werden, desto mehr Zweige können durch Abschätzung übersprungen werden. Im ungünstigsten Fall kann der zusätzliche Aufwand für die Abschätzungen den Gesamtaufwand der Berechnung sogar erhöhen. Im ISSM wird die Segmentierungsbewertung als Heuristik verwendet, die mit relativ wenig Aufwand vorab berechnet werden kann. Alle Kombinationen von Segmentierungen werden dann bezüglich ihrer Bewertung sortiert und anschließend als Grundlage der Interpretationserzeugung verwendet.

Abschätzung

Die Abschätzung der Bewertung durch das Ausgabeneuron out erfolgt, indem für alle noch nicht berechneten Merkmalsbewertungen x_i eine obere Grenze x_i bestimmt wird. Dazu wird eine Motivzuordnung unbekannt eingeführt, die Eingabemotive, deren Zuordnung noch nicht festgelegt wurde, von denen unterscheidet, die per Interpretation nicht zugeordnet sind. Bei der Erzeugung der Interpretationen wird bei gegebener Segmentierungen zunächst nur das erste Motiv zugeordnet und für die restlichen Motive die Zuordnung unbekannt eingesetzt. Merkmalsbewertungen, die auf eine Zuordnung unbekannt in den Daten treffen, geben die Obergrenze des möglichen Werts bei den gegebenen Informationen aus. Das ist bei allen Bewertungen auf Motivebene das Supremum des Wertebereichs W_i der Bewertungsfunktion. Da alle hier verwendeten Merkmalsbewertungen den Wertebereich [0,1] haben, liefert x_i den Wert 1. Auf der Phrasenebene bei COrder kann man die Berechnung genauer vornehmen, indem man nur für die nicht zugeordneten Gruppen die minimale Fehlerzahl annimmt:

(10.1)

Bei der Berechnung der oberen Grenze ist zu berücksichtigen, daß negative Gewichte