This page (revision-9) was last changed on 21-May-2009 22:06 by Dieter Käppel

This page was created on 21-May-2009 16:36 by Dieter Käppel

Only authorized users are allowed to rename pages.

Only authorized users are allowed to delete pages.

Page revision history

Version Date Modified Size Author Changes ... Change note
9 21-May-2009 22:06 4 KB Dieter Käppel to previous
8 21-May-2009 22:06 4 KB Dieter Käppel to previous | to last
7 21-May-2009 21:51 4 KB Dieter Käppel to previous | to last
6 21-May-2009 16:58 3 KB Dieter Käppel to previous | to last
5 21-May-2009 16:49 3 KB Dieter Käppel to previous | to last
4 21-May-2009 16:48 3 KB Dieter Käppel to previous | to last
3 21-May-2009 16:47 2 KB Dieter Käppel to previous | to last
2 21-May-2009 16:39 1 KB Dieter Käppel to previous | to last
1 21-May-2009 16:36 637 bytes Dieter Käppel to last

Page References

Incoming links Outgoing links

Version management

Difference between version and

At line 5 removed 81 lines
!Kombination von Symbolen
Basis unserer Sprachverarbeitung ist die Kombination von Symbolen. Die Wahrscheinlichkeit, dass die Symbole A und B gemeinsam auftreten ist hypergeometrisch verteilt.
Gegeben sei eine Sequenz von n Symbolen vor, in der Symbol A mit der Zahl nA und Symbol B mit der Zahl nB und die Kombination AB mit der Zahl nAB auftritt. Die Wahrscheinlichkeit, dass dies kein Zufall ist, ist genau hypergeomF(n, nA, nB, nAB).
{{{
public static double hypergeometricF(int n, int nA, int nB, int nAB) {
double p = 0;
for (int i = 0; i <= nAB; ++i) {
p += hypergeometric(n, nA, nB, i);
}
return p;
}
public static double hypergeometric(int n, int nA, int nB, int nAB) {
return binomial(nA, nAB) * binomial(n - nA, nB - nAB) / (double)binomial(n, nB);
}
public static long binomial(int n, int k) {
return factorial(n) / (factorial(k) * factorial(n - k));
}
public static long factorial(int n) {
long z = 1;
for (int i = 2; i <= n; ++i)
z *= i;
return z;
}
}}}
Die hier gezeigte Implementierung der hypergeometrischen Verteilungsfunktion haben wir nicht besonders optimiert, dafür ist der Algorithmus mathematisch sehr leicht durchschaubar. In der Praxis nutzen wir diese Implementierung sowieso nicht, da die Approximierung durch die Gauß-Verteilung in konstanter Komplexität berechnet werden kann und nicht den Integer-Einschränkungen im Wertebereich unterliegt:
{{{
public static double normalF(int n, int nA, int nB, int nAB) {
double pA = (double)nA / n;
double mu = nB * pA;
double c = (n - nB) / (double)(n - 1);
double sigma = Math.sqrt(mu * (1 - pA) * c);
return normalF(mu, sigma, nAB + 0.5 /* avg */);
}
public static double normalF(double mu, double sigma, double x) {
return normalF((x - mu) / sigma);
}
public static double normalF(double x) {
double t = 1.0 / (1.0 + 0.33267 * Math.abs(x));
double u = t * (0.3480242 + t * (-0.0958798 + t * 0.7478556));
double z = 0.5 * u * Math.exp(-0.5 * x * x);
return x < 0 ? z : 1 - z;
}
}}}
Ein Vergleich der hypergeometrischen Werte mit der Gauß-Approximation bringt folgendes Ergebnis:
{{{
p(14, 6, 7, 0) = 0.002331002331002331 ~ 0.004642135984499961
p(14, 6, 7, 1) = 0.05128205128205128 ~ 0.059229045502362444
p(14, 6, 7, 2) = 0.29603729603729606 ~ 0.30139821320402993
p(14, 6, 7, 3) = 0.703962703962704 ~ 0.6986017867959701
p(14, 6, 7, 4) = 0.9487179487179488 ~ 0.9407709544976376
p(14, 6, 7, 5) = 0.9976689976689977 ~ 0.9953578640155001
p(14, 6, 7, 6) = 1.0 ~ 0.999864197750926
p(11, 7, 3, 0) = 0.024242424242424242 ~ 0.029331570951360776
p(11, 7, 3, 1) = 0.27878787878787875 ~ 0.29153348349543307
p(11, 7, 3, 2) = 0.7878787878787878 ~ 0.786084674765772
p(11, 7, 3, 3) = 1.0 ~ 0.9836001998090625
}}}
Das Ergebnis ist für die Praxis zunächst völlig ausreichend. Die eigentliche Herausforderung liegt nicht in der Präzision der Berechnung, sondern in der strukturellen Vorgehensweise bei der Aufstellung des semantischen Gebildes.
!Analyse
Durch die Verarbeitung eines Textes werden zunächst die Wahrscheinlichkeiten für das Auftreten der vorliegenden Paare der Eingabesymbole ermittelt. Ausgehend von diesen Wahrscheinlichkeiten kann eine Symbolfolge nun logisch zerlegt werden, durch Paarbildung in absteigender Folge der Wahrscheinlichkeiten des Auftretens dieser Symbolpaare.
!Kombination von Kombinationen
Bei der Kombination der ersten Ebene, also die Kombination von Symbolen ist die Grundgesamtheit trivial festzustellen, sie entspricht der Anzahl von Symbolen in der verarbeiteten Zeichenkette. Bei der Kombination zweiter Ebene ist die Lage ebenfalls noch relativ einfach. Je höher man in der semantischen Hierarchie aufsteigt, desto mehr vermischen sich die Ebenen. Einige Silben, Wörter, Sätze etc. sind länger als andere, der Inhalt befindet sich jedoch auf derselben semantischen Ebene.
Sinnvoll wäre also ein iterativer Algorithmus.
!Anforderungen
Die Verarbeitung semantischer Informationen müsste folgenden Kriterien genügen:
* __Fehlertoleranz:__ Ungenauigkeiten in einzelnen Symbolen dürfen das Gesamtsystem nicht stören.
* __Abstraktion:__ Die Regeln müssen in abstrahierter Form vorliegen und nicht nur das Auftreten von Symbol- oder Kombinationspaaren beschreiben.