From 710f58ef4321c39886429617f08f5f67e2d3a0d6 Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Mon, 15 Mar 2010 03:07:37 +0100 Subject: [PATCH] tex: Strength Classifier - clean up --- tex/gostyle.tex | 69 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 34 insertions(+), 35 deletions(-) diff --git a/tex/gostyle.tex b/tex/gostyle.tex index dd23c80..620ce11 100644 --- a/tex/gostyle.tex +++ b/tex/gostyle.tex @@ -401,7 +401,10 @@ We use these features: \item capture move flag \item atari move flag \item atari escape flag -\item contiguity-to-last flag --- whether the move has been played in one of 8 neighbors of the last move +\item contiguity-to-last flag% +\footnote{We do not consider contiguity features in some cases when we are working +on small game samples and need to reduce pattern diversity.} +--- whether the move has been played in one of 8 neighbors of the last move \item contiguity-to-second-last flag \item board edge distance --- only up to distance 4 \item spatial pattern --- configuration of stones around the played move @@ -842,53 +845,49 @@ with no discernable structure revealed within the lower-order eigenvectors.} We measure the accuracy of strength approximation by the first dimension using Pearson's $r$ (see \ref{pearson}), yielding quite satisfying value of $r=0.979$ implying extremely strong correlation. -Using the eigenvector position directly for classification -of players within the test group yields MSE TODO, thus providing -reasonably satisfying accuracy by itself.% \footnote{Extended vector normalization (sec. \ref{xnorm}) produced noticeably less clear-cut results.} -\subsection{Strength classifier} -To further enhance the strength estimator usability, -we have tried to use a $k$-NN classifier on the testing set, consisting -of one $(\vec p, {\rm rank})$ pair per player. The testing set was -randomly separated as $10\%$ size of the game database. -We want to learn the smallest number of games for a~player's strength to be reasonably estimated. -The player files within each rank in the database were -merged to increase the size of files and to make the pattern distribution more reliable. - -TODO zminit uz na zacatku? -Moreover, we discarded \emph{ldist} and \emph{lldist} from the pattern files, since they increase -granularity of patterns (note that we are dealing with small input files, so the benefit of -having more features -- that increase variability -- is negligible in this case). - -The results for different file sizes are shown in the table \ref{table-str-class}. The smaller the -file, the smaller the number of games needed; however, with smaller files comes bigger error. -The error is listed as either MSE, or standard deviation $\sigma$ in percentage (meaning -the difference from the real rank on average). - -TODO je v pohode ta velikost souboru?? (zalezi na reprezentaci..) -TODO jestli jen hry tak predelat i nahore +\subsection{Strength classification} + +We have randomly separated $10\%$ of the game database as a testing set, +one $(\vec p, {\rm rank})$ pair per player. We then explore the influence +of game sample size% +\footnote{Arbitrary game numbers are approximated by pattern file sizes, +randomly selecting games of appropriate strength.} +on the accuracy of various classifiers. +In order to reduce the diversity of patterns (negatively impacting accuracy +on small samples), we do not consider the contiguity pattern features. + +Using the most significant PCA eigenvector position directly for classification +of players within the test group yields MSE TODO, thus providing +reasonably satisfying accuracy by itself. + +Using the $k$-NN classifier, we have achieved the results described +in the table \ref{table-str-class} --- overally obtaining quite impressive +accuracy even on rather small game sample sizes. +The error is listed as MSE (on rank rescaled to $[-1,1]$) and standard deviation +$\sigma$ in percentages (meaning the difference from the real rank on average). + \begin{table}[!t] % increase table row spacing, adjust to taste \renewcommand{\arraystretch}{1.3} -\caption{TODO} +\caption{Strength Classifier Performance} \label{table-str-class} \centering \begin{tabular}{|c|c|c|c|c|} \hline -File size ($\sim$ number of games) & MSE & $\sigma \%$ \\ \hline -$500 \mathrm{kB} (\sim85)$& $0.007$ & $4\%$ \\ -$250 \mathrm{kB} (\sim43)$& $0.029$ & $8\%$ \\ -$100 \mathrm{kB} (\sim17)$& $0.081$ & $14\%$ \\ -$50 \mathrm{kB} (\sim9)$& $0.131$ & $18\%$ \\ -$10 \mathrm{kB} (\sim2)$& $0.187$ & $22\%$ \\\hline +$\sim$ games & MSE & $\sigma \%$ \\ \hline +$85$& $0.007$ & $4\%$ \\ +$43$& $0.029$ & $8\%$ \\ +$17$& $0.081$ & $14\%$ \\ +$9$& $0.131$ & $18\%$ \\ +$2$& $0.187$ & $22\%$ \\\hline \end{tabular} \end{table} -Finally, we used a $8$-fold cross validation (see section \ref{crossval}) on one-file-per-rank files, -yielding MSE $0.085$ (rank encoded linearly in $[-1,1]$), which is equivalent to -standard deviation of $15\%$. +Finally, we used $8$-fold cross validation on one-file-per-rank files, +yielding a MSE $0.085$ which is equivalent to standard deviation of $15\%$. \section{Style Estimation} \label{styleest} -- 2.11.4.GIT