Polynomklassifikator

Polynomklassifikatoren zur Mustererkennung wurden aus der statistischen Entscheidungstheorie entwickelt und haben die Schlüsselfunktion in Texterkennung (OCR), einem Teilgebiet der Mustererkennung.

Ihr wesentlicher Vorteil liegt in der Möglichkeit, die Adaptionsaufgabe direkt zu lösen. Aufbauend auf dieser Basistechnologie wurden komplexe und hochleistungsfähige Klassifikatorstrukturen entwickelt (Bäume, Netze), die ihre Leistungsfähigkeit auf sehr unterschiedlichen Anwendungsfeldern unter Beweis stellen konnten, etwa für Anschriftenleser, Postautomatisierung oder Formularleser.

Mathematische Definition

Ein Polynomklassifikator ist eine Abbildung von Vektoren aus dem $d$-dimensionalen reellen Merkmalsraum auf eine Menge $\{1,\dots ,k\}$ von Klassen:

$f:{ℝ}^d\to \{1,\dots ,k\}$

Dabei ist $f$ definiert als höchstwertige Komponente des folgenden Vektors

$𝐲=𝐩(𝐯)=\left(\begin{array}{c}{p}_1(𝐯)\\ ⋮\\ p_k(𝐯)\end{array}\right)$

Die multivariaten Polynome $p_i(𝐯)=y_i\in [0,1]$ können als Wahrscheinlichkeitsfunktionen interpretiert werden, dass ein gegebener Merkmalsvektor $𝐯$ der Klasse $i$ angehört. Insgesamt gilt $\Vert 𝐲{\Vert }_1=1$.

Die obige Schreibweise lässt sich vereinfachen, indem statt vielen Polynomen $p_i(𝐯)$ nur ein Polynom $𝐱(𝐯)$ berechnet wird. Dann gilt $p_i(𝐯)=𝐚\cdot 𝐱(𝐯)$ mit einem reellwertigen Koeffizientenvektor. Insgesamt folgt $𝐩(𝐯)=A^T𝐱(𝐯)$.

Die Klassifikation eines neuen Merkmalsvektors $\widehat{𝐯}$ erfolgt somit durch $\arg \max 𝐩(\widehat{𝐯})=f(\widehat{𝐯})$.

Literatur

• J. Schürmann: Pattern Classification: A Unified View of Statistical and Neural Approaches. Wiley&Sons, 1996, ISBN 0471135348.
• H. Niemann: Klassifikation von Mustern. Springer, Berlin 1983, ISBN 3-540-12642-2. (2. Auflage, ohne Verlag, 2003: PDF-Datei; 6,5 MB).