samuizo

You can often strike a balance between rare words that appear in only a couple of documents and very frequent words that occur all over the place by employing both a term frequency and a document frequency weighting scheme; 'tf-idf' in the nomenclature [1].

The basic idea is that you keep track of counts both within documents and among documents. For English, word like 'the' will be frequent in each document it occurs in. It will also occur in every document. The high document frequency counteracts the high term frequency. On the other hand, 'motherboard' might be infrequent overall (but not extremely so), but its low document frequency boosts its importance.

The scheme is commonly employed and works quite well, sometimes obviating the need for careful vocabulary pruning. FWIW, scikit-learn implements it in their feature extraction library [2].

[1] http://en.wikipedia.org/wiki/Tf–idf‎ [2] http://scikit-learn.org/stable/modules/generated/sklearn.fea...

While CPU cost is a concern, often memory and correspondingly IO is the bottleneck in vector space approaches. Practitioners can leverage highly-optimized libraries for performing the matrix decompositions, so random disk seeks become more of a concern than CPU time. It's in iterative SVD that Gensim really shines in my opinion.

Turning to your example, any model based on term frequencies, vector space treatments included, would have trouble identifying 'Drakaal' as the most important term. But, this can be mitigated to some extent by preprocessing. In particular, naive coreference resolution would simply assign 'Drakaal' to every occurrence of 'he'/'his' in the sentence (since there are no other candidates). In which case, the count of 'Drakaal' jumps from 1 to 5. Just taking the comments in this thread as the corpus, that's a pretty high frequency for a single document, which might indeed get it to stand out on that basis alone.

Now whether we could get even more nuanced and determine that it's not just about 'Drakaal' but also a certain disposition toward him really depends on the task. If it's important to uncover those sorts of patterns then I would incorporate some documents that are illustrative of the distinction. In this sense, vector space approaches can be both purely exploratory as well as guided toward the divisions you aim for.

I could be mistaken, but I think there's a fundamental distinction between the computing power required to recognize a language and the kinds of functions a language can compute. AFAIK (which isn't much), usually the distinction between regular, context-free, context-sensitive and recursively-enumerable languages turns on the power of the recognizer rather than the power of the language to express functions. In other words, the languages are limited in their syntactic expressivity but not their semantic expressivity. I've always understood the latter to be the key to determining the computational power. Take lambda calculus as an example. It is Turing complete, but it is amenable to a context-free syntactic implementation (see http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/la...). For C++, I always thought it was that not only is it capable of expressing semantically any computable function, but that a [EDIT: Turing Complete] parser was required to parse C++ strings.