
## Projected Text

Over the many have to of data their ,,their ,,and their ..At the same time,,,and in many nd complex ,,such as the of data that in .. The of data the of how best to use this data to general and to ..Data ::using data to and ..The of in data follows from the of several :

## Original Text

Over the past decade many organizations have begun to routinely capture huge volumes of historical data describing their operations, their products, and their customers. At the same time, scientists and engineers in many fields find themselves capturing increasingly complex experimental datasets, such as the gigabytes of functional MRI data that describe brain activity in humans. The field of data mining addresses the question of how best to use this historical data to discover general regularities and to improve future decisions. Data Mining: using historical data to discover regularities and improve future decisions. The rapid growth of interest in data mining follows from the confluence of several recent trends:
Figure 1. An excerpt from the paper "Machine Learning and Data Mining" (?). Top: A projection of the text over the high frequency tokens; Bottom: The original text. Excerpt is taken from the paper Machine Learning and Data Mining (?).

## 6. Experiments

Here we describe our initial empirical studies of the proposed multiclass decomposition procedure. We compare our method with the "all-pairs' decomposition. Taking the MLA-100 dataset (see Section 5) we generated a a progressively increasing random subset as follows. From the MLA-100 we randomly chose 3 authors, then added another author, chosen randomly and uniformly from the remaining authors, etc.

This way we generated increasing sets of authors in the range of 3-100. So far we have experimented with multiclass subsets with k = 3 − 20, **50 and 100. In all**
the experiments we used an SVM with an RBF kernel. The SVM parameters where chosen using crossvalidation. The reported results are averages of 3-fold cross-validation.

The features generated for our authorship determination problems contained in all cases the top 5000 single tokens (see Section 5 for the token definition) as well as the following "high order pairs". After projecting the documents over the high frequency single tokens we took all bigrams. For instance, considering the projected text in Figure 1, the token pair 'to'+'of' appearing in the first line of the projected text (top)
is one of our features. Notice that in the original text this pair of words appears 5 words apart. This way our representation captures high order pairwise statistics of the tokens. Moreover, since we restrict ourselves to the most frequent tokens in the text these pairs of token do not suffer too much from the typical statistical sparsness which is usually experienced when considering n**-grams in text categorization and language**
models.

Accuracy results for both "all-pairs" and our hierarchical decomposition procedure appear in Figure 2. The first observation is that the absolute values of these classification results are rather high compared to typical figures reported in authorship determination. For example, (?**) report on accuracy around 70% for determining between 10 authors of newspaper articles.**
Such figures (i.e. number of authors and around 60%- 80% accuracy) appear to be common in this field. The closest results in both size and accuracy we have found are of (?**), who distinguish between 117 newsgroup authors with accuracy 58.8% and between 84 authors**
with accuracy 80.9%. Still, this is far from he 91% accuracy we obtain for 50 authors and 88% accuracy for 100 authors.

The consistent advantage of hierarchical decompositions over all-pairs is evident for small number of classes. However, for over 10 classes, there is no significant difference between the methods. Interestingly, the best hierarchical constructs our method generated (in terms of the Q(T **)) were completely skewed. It is** not clear to us at this stage whether this is an artifact of our Bayes error bound or a weakness of our heuristic procedure.

## 7. Concluding Remarks

This paper presents a new approach for hierarchical multiclass decomposition of multinomials. A similar hierarchical approach can be attempted with nonparameteric models. For instance using any nonparametric probabilistic binary discriminator one can attempt to heuristically estimate the hardness of the involved binary problems using empirical error rates and design reasonable hierarchical decompositions. However, a major difficulty in this approach is the computational burden.

When considering the main inherent deficiency of allpairs decompositions it appears that this deficiency should disappear or at least soften when the number of classes increases. The reason is that with large number of classes, the noisy votings of irrelevant classifiers will