From 0a72029bcb1ec9046848a936fd22257a65d32edb Mon Sep 17 00:00:00 2001 From: Vasil Zlatanov Date: Wed, 13 Feb 2019 18:28:33 +0000 Subject: Ammend part 3 --- report/paper.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/report/paper.md b/report/paper.md index 0674557..5fb0443 100644 --- a/report/paper.md +++ b/report/paper.md @@ -95,10 +95,10 @@ Figure \ref{fig:km_cm} shows a confusion matrix for K-means+RF CLassifier with 2 # RF codebook -An alternative to codebook creation via K-means involves using an ensemble of totally random trees. We code each decriptor according to which leaf of each tree in the ensemble it is sorted. This effectively performs and unsupervised transformation of our dataset to a high-dimensional spare representation. The vocabulary size is determined by the number of leaves in each random tree multiplied by the ensemble size. From comparing execution times of K-means in figure \ref{fig:km_vocsize} and the RF codebook in \ref{fig:p3_voc} we observe considerable speed gains from utilising the RF codebook. This may be attributed to the reduce complexity of RF Codebook creation, +An alternative to codebook creation via K-means involves using an ensemble of totally random trees. We code each decriptor according to which leaf of each tree in the ensemble it is sorted. This effectively performs and unsupervised transformation of our descriptors to a high-dimensional sparse representation. The vocabulary size is determined by the number of leaves in each random tree multiplied by the ensemble size. From comparing execution times of K-means in figure \ref{fig:km_vocsize} and the RF codebook in \ref{fig:p3_voc} we observe considerable speed gains from utilising the RF codebook. This may be attributed to the reduce complexity of RF Codebook creation, which is $O(\sqrt{D} N \log K)$ compared to $O(DNK)$ for K-means. Codebook mapping given a created vocabulary is also quicker than K-means, $O(\log K)$ (assuming a balanced tree) vs $O(KD)$. -The effect of vocabulary size on classification accuracy can be observed both in figure \ref{fig:p3_voc}, in which we independently vary number of leaves and ensemble size, and figure \ref{fig:p3_colormap}, in which both parameters are varied simultaneously. It is possible to notice that these two parameters make classification accuracy plateau for *leaves>80* and *estimators>100*. The peaks at 82% shownin figure \ref{fig:p3_colormap} are just due to the seed. +The effect of vocabulary size on classification accuracy can be observed both in figure \ref{fig:p3_voc}, in which we independently vary number of leaves and ensemble size, and figure \ref{fig:p3_colormap}, in which both parameters are varied simultaneously. It is possible to notice that these two parameters make classification accuracy plateau for *leaves*$>80$ and *estimators*$>100$. The peaks of 82% accuracy visible on the heatmap in figure \ref{fig:p3_colormap} are highly dependent on the seed and indicate the range of *good* hyperparametres. \begin{figure}[H] \begin{center} -- cgit v1.2.3-54-g00ecf From 6c6a0100561be0525774eff0b7212ae7e61826f0 Mon Sep 17 00:00:00 2001 From: Vasil Zlatanov Date: Wed, 13 Feb 2019 18:44:43 +0000 Subject: Fix part 3 so it reads well --- report/paper.md | 27 ++++++++++++--------------- 1 file changed, 12 insertions(+), 15 deletions(-) diff --git a/report/paper.md b/report/paper.md index 5fb0443..a6452d3 100644 --- a/report/paper.md +++ b/report/paper.md @@ -68,7 +68,7 @@ This parameter also affects correlation between trees. We expect in fact trees t \begin{center} \includegraphics[width=12em]{fig/new_kmean_random.pdf} \includegraphics[width=12em]{fig/p3_rand.pdf} -\caption{Classification error for different number of random features; K-means left, RF-codebooks right} +\caption{Classification error for different number of random features; K-means left, RF codebooks right} \label{fig:kmeanrandom} \end{center} \end{figure} @@ -104,40 +104,37 @@ The effect of vocabulary size on classification accuracy can be observed both in \begin{center} \includegraphics[width=12em]{fig/error_depth_p3.pdf} \includegraphics[width=12em]{fig/trees_p3.pdf} -\caption{RF-codebooks Classification error varying trees depth (left) and numbers of trees (right)} +\caption{RF codebooks Classification error varying trees depth (left) and numbers of trees (right)} \label{fig:p3_trees} \end{center} \end{figure} -Similarly to K-means+RF Classifier, in this case we find optimal tree depth and number of trees to be respectively close to 5 and 100 as it can be seen in figure \ref{fig:p3_trees}. The classification accuracy on average is 1% to 2% lower (78% on average, peaking at 82%). +Similarly to K-means codebook, we find that for the RF codebook the optimal tree depth and number of trees are around 5 and 100 as it can be seen in figure \ref{fig:p3_trees}. The classification accuracy on average is 1% to 2% lower (78% on average, peaking at 82%). \begin{figure}[H] \begin{center} \includegraphics[width=12em]{fig/p3_vocsize.pdf} \includegraphics[width=12em]{fig/p3_time.pdf} -\caption{RF-codebooks Effect of vocabulary size; classification error (left) and time (right)} +\caption{RF codebooks Effect of vocabulary size; classification error (left) and time (right)} \label{fig:p3_voc} \end{center} \end{figure} -Varying the randomness parameter (figure \ref{fig:kmeanrandom}) achieves similar results to the K-means+RF Classifier case. +Varying the randomness parameter of the RF classifier (as in figure \ref{fig:kmeanrandom}) when using a RF codebook gives similar results as using the K-Means codebook. -Figure \ref{fig:p3_cm} shows the confusion matrix for a case in whichi we choose Codebook Forest Size=256, Classifier Forest Size=100, Trees Depth=5 (examples of success and failure in figure \ref{fig:p3_succ}). The classification accuracy for this case is 79%, with the top performing class being *windsor_chair*. Also in this case *water_lilly* was the worst performing class. The results are in general similar to the ones obtained with K-Means+RF Classifier, but the increase in time performance of RF Codebooks+RF Classifier is significant. +Figure \ref{fig:p3_cm} shows the confusion matrix for results with Codebook Forest Size=256, Classifier Forest Size=100, Trees Depth=5 (examples of success and failure in figure \ref{fig:p3_succ}). The classification accuracy for this case is 79%, with the top performing class being `windsor_chair`. In our tests, we observed poorest performance with the `water_lilly` class. The per class accuracy of classification with the RF codebook is similar to that of K-Means coded data, but we observe a significant speedup in training performance when building RF tree based vocabulary. # Comparison of methods and conclusions -Overall we observe slightly higher accuracy when using K-means codebooks compared to RF codebook at the expense of a higher execution time for training and testing. +Overall we observe marginally higher accuracy when using K-means codebooks compared to RF codebook at the expense of a higher execution time for training and testing. -As discussed in section I, due to the initialization process for optimal centroids placements, K-means can result unpreferable for large -descriptors' sizes (in absence of methods for dimensionality reduction), -and in many cases the increase in training time would not justify the minimum increase in classification performance. +As discussed in section I, due to the initialization process for optimal centroids placements, K-means can be unpreferable for large +descriptors' counts (and in absence of methods for dimensionality reduction). +In many applications the increase in training time would not justify the minimum increase in classification performance. -For Caltech_101 RF-codebook seems to be the most suitable method to perform RF-classification. +For the Caltech_101 dataset, a RF codebook seems to be the most suitable method to perform RF-classification. -It is observable that for the particular dataset we are analysing the class *water_lilly* -is the one that gets misclassified the most, both in k-means and RF-codebook (refer to figures \ref{fig:km_cm} and \ref{fig:p3_cm}). This means that the features obtained -from this class do not guarantee very discriminative splits, hence the first splits in the trees -will prioritize features taken from other classes. +The `water_lilly` is the most misclassified class, both in k-means and RF codebook (refer to figures \ref{fig:km_cm} and \ref{fig:p3_cm}). This indicates that the features obtained from the class do not provide for very discriminative splits, resulting in the prioritsation of other features in the first nodes of the decision trees. \newpage -- cgit v1.2.3-54-g00ecf