ARTFL Project Research Blog

shlax and ElementTree

2011-03-30T10:39:00.007-05:00

I've just pushed a few commits to the central philo4 repository;

mostly small bugfixes to the makefile and the parser, but I added a convenience method to the shlax XML parser.

As you may know, Python has a really nice XML library called ElementTree, but it has a few quirks:

1) it uses standard, "fussy" XML parsers that choke on the slightest flaw, and

2) it has a formally correct but incomprehensible approach to namespaces that is exceedingly impractical for day-to-day TEI hacking.

In this update, I've added a shlaxtree module to the philo4 distribution that hooks our fault-tolerant, namespace-agnostic XML parser up to ElementTree's XPath evaluator and serialization facilities. It generally prefers the 1.3 version of ElementTree, which is standard in python 2.7, but a simple install in 2.6 and 2.5.

Basically, the method philologic.shlaxtree.parse() will take in a file object, and return the root node of the xml document in the file, assuming it found one. You can use this to make a simple bibliographic extractor like so:


#!/usr/bin/env python
import philologic.shlaxtree as st
import sys
import codecs

for filename in sys.argv[1:]:
    file = codecs.open(filename,"r","utf-8")
    root = st.parse(file)
    header = root.find("teiHeader")
    print st.et.tostring(header)
    print header.findtext(".//titleStmt/title")
    print header.findtext(".//titleStmt/author")

Not bad for 10 lines, no? What's really cool is that you can modify trees, nodes, and fragments before writing them out, with neat recursive functions and what not. I've been using it for converting old SGML dictionaries to TEI--once you get the hang of it, it's much easier than regular expressions, and much easier to maintain and modify as well.

shlax: a shallow, lazy XML parser in python

2010-08-18T10:44:00.006-05:00

Recently, I stumbled upon a paper from the dawn age of XML:

"REX: XML Shallow Parsing with Regular Expressions", Robert D. Cameron

http://www.cs.sfu.ca/~cameron/REX.html

It describes how to do something I'd never seen done before: parse the entirety of standard XML syntax in a single regular expression.

We've all written short regexes to find some particular feature in an XML document, but we've also all seen those fail because of oddities of whitespace, quoting, linebreaks, etc., that are perfectly legal, but hard to account for in a short, line-by-line regular expression.

Standard XML parsers, like expat, are fabulous, well maintained, and efficient. However, they have a common achilles heel: the XML standard's insistence that XML processors "MUST" report a fatal error if a document contains unbalanced tags. For working with HTML or SGML based documents, this is disastrous!

In contrast, Cameron's regex-based parser is extremely fault-tolerant--it extracts as much structure from the document as possible, and reports the rest as plain text. Further, it supports "round-tripping": the ability to exactly re-generate a document from parser output, which standard parser typically lack. As a corollary of this property, it becomes possible to report absolute byte offsets, which is a "killer feature" for the purposes of indexing.

Because of all these benefits, I've opted to translate his source code from javascript to python. I call my modified implementation "shlax" [pronounced like "shellacs", sort of], a shallow, lazy XML parser. "Shallow" meaning that it doesn't check for well-formedness, and simply reports tokens, offsets, and attributes as best it can. "Lazy" meaning that it iterates over the input, and yields one object at a time--so you don't have to write 8 asynchronous event handlers to use it, as in a typical SAX-style parser. This is often called a "pull" parser, but "shpux" doesn't sound as good, does it?

If you're interested, you can look at the source at the libphilo github repo. The regular expression itself is built up over the course of about 30 expressions, to allow for maintainability and readability. I've made some further modifications to Cameron's code to fit our typical workflow. I've buffered the text input, which allows us to iterate over a file-handle, rather than a string--this saves vast amounts of memory for processing large XML files, in particular. And I return "node" objects, rather than strings, that contain several useful items of information:

the original text content of the node
the "type" of the node: text, StartTag,EndTag, or Markup[for DTD's, comments, etc.]
any attributes the node has
the absolute byte offset in the string or file

You don't need anything more than that to power PhiloLogic. If you'd like to see an example of how to use it, take a look at my DirtyParser class, which takes as input a set of xpaths to recognize for containers and metadata, and outputs a set of objects suitable for the index builder I wrote about last time.

Oh, and about performance: shlax is noticeably slower than Mark's perl loader. I've tried to mitigate for that in a variety of ways, but in general, python's regex engine is not as fast as perl's. On the other hand, I've recently had a lot of success with running a load in parallel on an 8-core machine, which I'll write about when the code settles. That said, if efficiency is a concern, our best option would be to use well-formed XML with a standard parser.

So, my major development push now is to refactor the loader into a framework that can handle multiple parser backends, flexible metadata recognizers, and multiple simultaneous parser processes. I'll be posting about that as soon as it's ready.

A Unified Index Construction Library

2010-05-19T10:47:00.008-05:00

I've spent the last two weeks replacing PhiloLogic's index-construction routines, following my prior work on the query and database interfaces.

The legacy index-packing code dates back to sometime before PhiloLogic 2, and is spread over 3 executable programs linked together by a Makefile and some obscure binary state files.

Unfortunately, the 3 programs all link to different versions of the same compression library, so they couldn't simply be refactored and recompiled as a single unit.

Instead, I worked backwards from the decompression routines I wrote last month, to write a new index construction library from scratch.

Thus, I had the luxury of being able to define an abstract, high-level interface that meets my four major goals:

1)simple, efficient operation

2)flexible enough for various index formats

3)easy to bind to other languages.

4)fully compatible with 3-series PhiloLogic

The main loop is below. It's pretty clean. All the details are handled by a hit-buffer object named "hb" that does compression, memory management, and database interfacing.

while(1) {
 // as long as we read lines from standard input.
 if (fgets(line,511,stdin) == NULL) {
   hitbuffer_finish(hb);
   break;
 }
 // scan for hits in standard Philo3 format.
 state = sscanf(line,
           "%s %d %d %d %d %d %d %d %d %s\n",
           word, &hit[0],...);

 if (state == 10) {
   // if we read a valid hit
   if ((strcmp(word,hb->word))) {
     //if we have a new word...
     hitbuffer_finish(hb); // write out the current buffer.
     hitbuffer_init(hb, word); // and reinitialize
     uniq_words += 1LLU; //LLU for a 64-bit unsigned int.
   }
   hitbuffer_inc(hb, hit); //add the hit to whichever word you're on.
   totalhits += 1LLU;
 }
 else {
   fprintf(stderr, "Couldn't understand hit.\n");
 }
}

The code is publicly available on github, but I'm having some problems with their web interface. I'll post a link once it's sorted out.

Vector Processing for OHCO

2010-05-06T11:06:00.002-05:00

I've posted an expanded version of my CI Days talk on Google docs. I'd recommend looking at the speaker notes (click "actions" on the bottom left) since I won't be narrating it in person.

The presentation is an attempt to describe, somewhat formally, how PhiloLogic is capable of performing as well as it does. This comes from spending three years learning how Leonid's search core works, and attempting to extend and elucidate whatever I can. It's also the intellectual framework that I'm using to plan new features, like search on line and meter position, metadata, joins, etc. Hopefully, I can get someone who's better at math than I am to help me tighten up the formalities.

Basically, I refer to the infamous OHCO thesis as a useful axiom for translating the features of a text into a set of numerical objects, and then compare the characteristics of this representation to XML or Relational approaches. I'd love to know how interesting/useful/comprehensible others find the presentation, or the concept. What needs more explanation? What gets tedious?

If you look at the speaker notes, you can see me derive a claim that PhiloLogic runs 866 times faster than a relational database for word search. Math is fun!

PhiloLogic proto-binding for Python

2010-04-13T15:27:00.007-05:00

In an earlier post, I mentioned that I'd try to to call the philologic C routines via ctypes, a Python Foreign Function Interface library. I did, and it worked awesomely well! Ctypes lets you call C functions from python without writing any glue at all in some cases, giving you access to high-performance C routines in a clean, modern programming language. We'd ultimately want a much more hand-crafted approach, but for prototyping interfaces, this is a very, very useful tool.

First, I had to compile the search engine as a shared library, rather than an executable:

gcc -dynamiclib -std=gnu99 search.o word.o retreive.o level.o gmap.o blockmap.o log.o out.o plugin/libindex.a db/db.o db/bitsvector.o db/unpack.o -lgdbm -o libphilo.dylib

All that refactoring certainly paid off. The search4 executable will now happily link against the shared library with no modification, and so can any other program that wants high-speed text object search:

#!/usr/bin/python

import sys,os
from ctypes import *

# First, we need to get the C standard library loaded in
# so that we can pass python's input on to the search engine.
stdlib=cdll.LoadLibrary("libc.dylib")
stdin = stdlib.fdopen(sys.stdin.fileno(),"r")
# Honestly, that's an architectural error.
# I'd prefer to pass in strings, not a file handle

# Now load in philologic from a shared library
libphilo = cdll.LoadLibrary("./libphilo.dylib")

# Give it a path to the database. The C routines parse the db definitions.
db = libphilo.init_dbh_folder("/var/lib/philologic/databases/mvotest5/")

# now initialize a new search object, with some reasonable defaults.
s = libphilo.new_search(db,"phrase",None,1,100000,0,None)

# Read words from standard input.
libphilo.process_input(s,stdin)

# Then dump the results to standard output.
libphilo.search_pass(s,0)
# Done.

That was pretty easy, right? Notice that there weren't any boilerplate classes. I could hold pointers to arbitrary data in regular variables, and pass them directly into the C subroutines as void pointers. Not safe, but very, very convenient.

Of course, this opens us up for quite a bit more work: the C library really needs a lot more ways to get data in and out than a pair of input/output file descriptors, I would say. In all likelihood, after some more experiments, we'll eventually settle on a set of standard interfaces, and generate lower-level bindings with SWIG, which would alow us to call philo natively from Perl or PHP or Ruby or Java or LISP or Lua or...anything, really.

Ctypes still has some advantages over automatically-generated wrappers, however. In particular, it lets you pass python functions back into C, allowing us to write search operators in python, rather than C--for example, a metadata join, or a custom optimizer for part-of-speech searching. Neat!

Unix Daemon Recipes

2010-04-08T15:14:00.004-05:00

I was digging through some older UNIX folkways when I stumbled upon an answer to a long-standing PhiloLogic design question:

How do I create a long-running worker process that will neither:

1) terminate when it's parent terminates, such as a terminal session or a CGI script, or
2) create the dreaded "zombie" processes that clog process tables and eventually crash the system.

as it turns out, this is the same basic problem as any UNIX daemon program; this just happens to be one designed to, eventually, terminate. PhiloLogic needs processes of this nature at various places: most prominently, to allow the CGI interface to return preliminary results.

Currently, we use a lightweight Perl daemon process, called nserver.pl, to accept search requests from the CGI scripts, invoke the search engine, and then clean up the process after it terminates. Effective, but there's a simpler way, with a tricky UNIX idiom.

First, fork(). This allows you to return control to the terminal or CGI script. If you aren't going to exit immediately you should SIGCHLD as well, so that you don't get interrupted later.

Second, have the child process call setsid() to gain a new session, and thus detach from the parent. This prevents terminal hangups from killing the child process.

Third, call fork() again, then immediately exit the (original) child. The new "grandchild" process is now an "orphan", and detached from a terminal, so it will run to completion, and then be reaped by the system, so you can do whatever long-term analytics you like.

A command line example could go like this:


#!/usr/bin/perl
use POSIX qw(setsid);

my $word = $ARGV[0] or die "Usage:searchwork.pl word outfile\n";
my $outfile = $ARGV[1] or die "Usage:searchwork.pl word outfile\n";

print STDERR "starting worker process.\n";
&daemonize;

open(SEARCH, "| search4 --ascii --limit 1000000 /var/lib/philologic/somedb);

print SEARCH "$word\n";
close(SEARCH);

exit;

sub daemonize {
    open STDIN, '/dev/null'   or die "Can't read /dev/null: $!";
    open STDOUT, '>>/dev/null' or die "Can't write to /dev/null: $!";
    open STDERR, '>>/dev/null' or die "Can't write to /dev/null: $!";
    defined(my $childpid = fork)   or die "Can't fork: $!";
    if ($childpid) {
        print STDERR "[parent process exiting]\n";
        exit;
    }
    setsid                    or die "Can't start a new session: $!";
    print STDERR "Child detached from terminal\n";
    defined(my $grandchildpid = fork) or die "Can't fork: $!";
    if ($grandchildpid) {
        print STDERR "[child process exiting]\n";
        exit;
    }
    umask 0;
}

The benefit is that a similar &daemonize subroutine could entirely replace nserver, and thus vastly simplify the installation process. There's clearly a lot more that could be done with routing and control, of course, but this is an exciting proof of concept, particularly for UNIX geeks like myself.

The Joy of Refactoring Legacy Code

2010-03-31T11:23:00.007-05:00

I've spent the last few weeks rehabbing PhiloLogic's low-level search engine, and I thought I'd write up the process a bit.

PhiloLogic is commonly known as being a rather large Perl/CGI project, but all of the actual database interactions are done by our custom search engine, which is in highly optimized C. The flow of control in a typical Philo install looks something like this:

--CGI script search3t accepts user requests, and parses them.
--CGI passes requests off to a long-running Perl daemon process, called nserver.
--nserver spawns a long-running worker process search3 to evaluate the request
--the worker process loads in a compiled decompression module, at runtime, specific to the database.
--search3t watches the results of the worker process
--when the worker is finished, or outputs more than 50 results, search3t passes them off to a report generator.

This architecture is extremely efficient, but as PhiloLogic has accrued features over the years it has started to grow less flexible, and parts of the code base have started to decay. The command line arguments to search3, in particular, are arcane and undocumented. A typical example:

export SYSTEM_DIR=/path/to/db

export LD_LIBRARY_PATH=/path/to/db/specific/decompression/lib/
search3 -P:binary -E:L=1000000 -S:phrase -E:L=1000000 -C:1 /tmp/corpus.10866

The internals are quite a bit scarier. Arguments are processed haphazardly in bizarre corners of the code, and many paths and filenames are hard-coded in. And terrifying unsafe type-casts abound. Casting a structure containing an array of ints into an array of ints? Oh my.

I've long been advocating a much, much simpler interface to the search engine. The holy grail would be a single-point-of-entry that could be installed as a C library, and called from any scripting language with appropriate interfacing code. There are several obstacles, particularly with respect to caching and memory management, but the main one is organizational.

How do you take a 15-year-old C executable, in some state of disrepair, and reconfigure the "good parts" into a modern C library? Slowly and carefully. Modern debugging tools like Valgrind help, as does the collective C wisdom preserved by Google. A particular issue is imperative vs. object-oriented or functional style. Older C programs tend to use a few global variables to represent whatever global data structure they work upon--in effect, what modern OOP practices would call a "singleton" object, but in practice a real headache.

For example, PhiloLogic typically chooses to represent the database being searched as a global variable, often set in the OS's environment. But what if you want to search two databases at once? What if you don't have a UNIX system? An object-oriented representation of the large-scale constructs of a program allows the code to go above and beyond its original purpose.

Or maybe I'm just a neat freak--regardless, the [simplified] top-level architecture of 'search3.999' {an asymptotic approach to an as-yet unannounced product} should show the point of it all:

{

static struct option long_options[] = {

{"ascii", no_argument, 0, 'a'},

{"corpussize", required_argument, 0, 'c'},

{"corpusfile", required_argument, 0, 'f'},

{"debug", required_argument, 0, 'd'},

{"limit", required_argument, 0, 'l'},

{0,0,0,0}

};

//...process options with GNU getopt_long...

db = init_dbh_folder(dbname);

if (!method_set) {

strncpy(method,"phrase",256);

}

s = new_search(db,

method,

ascii_set,

corpussize,

corpusfile,

debug,

limit);

status = process_input ( s, stdin );

//...print output...

//...free memory...

return 0

}

An equivalent command-line call would be:

search3999 --ascii --limit 1000000 --corpussize 1 --corpusfile /tmp/corpus.10866 dbname search_method

which is definitely an improvement. It can also print a help message.

Beyond organizational issues, I also ended up rewriting large portions of the decompression routines. The database can now fully configure itself at runtime, which adds about 4 ms to each request, but with the benefit that database builds no longer require compilation. TODO: The overhead can be eliminated if we store that database parameters as integers, rather than as formatted text files.

I think at this point the codebase is clean enough to try hooking up to python, via ctypes, and then experiment with other scripting language bindings. Once I clean up the makefiles I'll put it up on our repository.

Reclassifying the Encyclopédie

2010-03-29T23:43:00.013-05:00

Diderot and D'Alembert's Encyclopédie might almost have been designed as a document classification exercise. For starters, it comes complete with a branching, hierarchical ontology of classes of knowledge. Out of the 77,000+ articles contained therein, 60,000 are classified according to this system, while 17,000 were left unclassified, providing a ready-made training set and evaluation set, respectively. To make it challenging, within the classified articles, the editors have chosen to apply some classifications with obfuscatory intent or, at least, result, rendering topic boundaries somewhat fuzzy. The categories span the entire breadth of human knowledge, and the articles range from brief renvois ("see XXX") to protracted philosophical treatises. In short, it has everything to make a machine learner happy, and miserable, in one package.

At ARTFL we've been mining this rich vein for some time now. We presented Mining Eighteenth Century Ontologies: Machine Learning and Knowledge Classification in the Encyclopédie at Digital Humanities 2007, detailing our initial attempts at classification and the critical interpretation of machine learning results. We followed up at DH 2008 with Twisted Roads and Hidden Paths, in which we expanded our toolkit to include k-nearest-neighbor vector space classifications, and a meta-classifying decision tree. Where we had previously achieved around 72% accuracy in categorizing articles medium-length and long articles using Naive Bayes alone, using multiple classifiers combined in this way we were able to get similar rates of accuracy over the entire encyclopedia, including the very short articles, which are quite difficult to classify due to their dearth of distinctive content. This post describes an effort to productionize the results of that latter paper, in order to insert our new, machine-generated classifications into our public edition of the Encyclopédie.

For the impatient, jump ahead to the ARTFL Encyclopédie search form and start digging. The new machine generated classifications can be searched just as any other item of Philologic metadata, allowing very sophisticated queries to be constructed.

For instance, we can ask questions like "Are there any articles originally classified under Géographie that are reclassified as Philsophie?" In fact there are several, and it's interesting to peruse them and deduce why their original classifications and generated classifications fall as they do. The editors followed a policy of not including biographies in the Encyclopédie, but evidently could not restrain themselves in many cases. Instead of creating a biography class, however, they categorized such entries under the headword corresponding to the region of the notable person's birth, and assigned it the class Géographie. Thus the article JOPOLI contains a discussion of the philosopher Augustin Nyphus, born there in 1472, and hence is classified by our machine learner under Philosophie.

Our goals in re-classifying the Encyclopédie are several: to provide better access for our users by adding class descriptions to previously unclassified articles; to identify articles that are re-classified differently from their original classes, allowing users to find them by their generated classes which are often more indicative of the overall content of an article; and to identify interesting patterns in the authors' uses of their classification system, again primarily by seeing what classes tend to be re-classified differently.

We initially undertook to examine a wide range of classifiers including Naive Bayesian, SVM and KNN vector space, with a range of parameters for word count normalization and other settings. After examining hundreds of such runs, we found two that, combined, provided the greatest accuracy in correctly re-classifying articles to their previous classifications: Naive Bayes, using simple word counts, and KNN, using 50 neighbors and tf-idf values for the feature vectors.

Each classifier alone was right about 64% of the time -- but together, at least one of them was right 77% of the time. If we could only decide which one to trust when they differed on a given classification decision, we could reap a substantial gain in accuracy on the previously classified articles, and presumably get more useful classifications of the unclassified articles. We must note that the class labels for each article, which appear at the beginning of the text, we retained for these runs, giving our classifiers an unfair advantage in re-classifying the articles that had such labels present. The class labels get no more weight, however, than any other words in the article. We retained them because our primary objective is to accurately classify the unclassified articles, which do not contain these labels, but may well contain words from these labels in other contexts.

It turned out that KNN was most accurate on smaller articles and smaller classes, whereas Naive Bayes worked best on longer articles that belonged to bigger classes, which gave us something to go on when deciding which classifier got to make the call when they were at odds with each other. By feeding the article and class meta-data into a simple decision tree classifier, along with the results of each classifier, we were able to learn some rules for deciding which classifier to prefer for a given decision where they disagreed on the class assignment. See the decision tree in the DH 2008 with DH 2008 paper for the details.

Of course, we couldn't make the perfect decision every time, but we were close enough to increase our accuracy on previously classified articles to 73%, 9% higher than the average of the individual classifiers. By using a meta-classifier to learn the relative strengths and weaknesses of the sub-classifiers, we were able to better exploit them to get more interesting data for our users, and peel back another layer of the great Encyclopédie. Additionally, we learned characteristics of the classifiers themselves that will enable us to target their applications more precisely in the future.

P.S.: For all you Diderot-philes, here are the stats on the original and machine-learned classes of the articles he authored:

If any of this piques your interest, please do get in touch with us (artfl dawt project at gee-male dawt com should work). We'd love to discuss our work and possible future directions. Or come check us out in Virginia next week!

using the JSON perl mod

2010-03-08T17:16:00.004-06:00

I just thought I'd make a quick blog post on how to use the JSON perl mod. Why use JSON when we have XML, I'll leave that to Russ or Richard, but to make a long story short, easier object handling for the projected javascript driven DVLF.
So, the perl JSON module is actually very easy and nice to use, it will convert your perl data structure into JSON without a sweat.
Here's a quick example which I hope will be useful :

#!/usr/bin/perl

use strict;

use warnings;

use JSON;

my %hash;

foreach my $file (@list_of_files) {

open(FILE,"$file");

my @list;

while (<FILE>) {

push(@array,$_);

}

%hash{$file} = [@array]; # store array reference in hash

}

my $obj = \%results;

my $json = new JSON;

my $js = $json->encode($obj, {pretty => 1, indent => 2}); # convert Perl data structure to JSON representation

$output .= "$js\n\n";

print $output;

And done!

Lemma Collocations on Perseus

2010-02-01T09:07:00.007-06:00

See UPDATE at the end.

This post actually relates nicely to Mark's recent post. I have recently been working on lemmatized collocation tables for the Greek texts on Perseus. If you just want to see the results, skim to the end, the rest describes how I got there.

It is not so difficult to look up the lemma for each word surrounding a certain search hit, as for these texts the structure to do so is already in place and the information is stored in SQL tables. Efficiency in gathering this information is the main difficulty. Looking up the lemma in the tables now in place can take a couple different SQL queries, which each take up a small chunk of time. For a few lookups, or even a few hundred, this is not too big of a problem. However, for a collocation table spanning five words on either side, we need at least 10 lookups in the databases per hit. The time it takes to do that adds up quite quickly.

So, following a suggestion from Mark, I wrote a script and generated a file with a line for every word in the Perseus database. Basically, it takes each word id starting with 1 on up to 5.5 million something and looks up its lemma. This generated a 5.5 million line file with lines likes this:

2334550 δέ
2334551 ὅς
2334552 ἕκαστος
2334553 ἵππος
2334554 nolemma
2334555 ὅς
2334556 δέ
2334557 πέτομαι
2334558 κονίω
2334559 πεδίον

Now, looking up the words on either side of a hit is much simpler - all you need to know is the "word id" of the hit and you can look at those around it. The "nolemma" entries are primarily punctuation and such which were given word tags at some point.

The size of this massive file however was another hindrance to efficient generation of collocation tables. Although we now know exactly what line we need to look at for the information we need, getting that line is still costly as it could require reading in a couple million lines of a file to get the one we need. After playing around with it a bit, command line grep searching seemed to be the fastest way to go, but even an grep search 10 times per hit adds up fast. So, I tried combining the searches into one massive egrep command to be read into a perl array. My searches looked something like:

egrep "23345[456][0-9]" lemmafile

Giving a window of 30 lines in the file starting at 2334540 and ending at 2334569. This limited the searches to one per hit instead of 10, but it still wasn't fast enough. So, I combine all of the searches like so:

egrep "(2342[234]|33329[678]|...|829[567])[0-9]"

(A bit of accounting for numbers ending in 0 is needed so that a window around 400 doesn't include things in the 490's, but this is not too difficult.)

This looked nice and seemed to work until I tried running it on more hits. It was then coming up with such massive regular expressions to grep for that grep was complaining that they were too big. So, I broke them up into chunks of roughly 350 at a time. Fewer, and the time would go up due to the added number of grep searches; too many more, and grep would overflow again. I may not have hit on the exact time minimizing value, but it is close at least.

Finally, here are some example searches:

Search for logoi.
Search for lemma:logos. (The time estimate is higher than actual load time).

Or, here is the search form:

Search Form.

Make sure that you choose Collocation Table and check the lemma button under the "Refined Search Results" Tab at the bottom.

It can handle most searches, except for very high frequency words. If anyone has ideas on how to make it faster, it could perhaps enable us to get results for all searches. Though perhaps this is not possible without somehow creating and saving those results somewhere.

UPDATE:

After talking to Mark, I altered the way the data is read from the file and now things should be running faster. The reason that all this discussion and speed streamlining for lemmatized collocation tables is necessary is the fact that the texts on Perseus do not have the lemmas embedded in the text. As Mark noted, many of the other databases would allow for much simpler and faster generation of the same data due to the fact that they do have lemmas in the text. However, for the purposes of Perseus, lemmas needed to be separated from the texts to allow them to be more dynamically updated, changed and maintained.

As for the speed, it should now be faster thanks to a handy function in Perl. I had investigated methods for reading a certain line of a file, since I happened to know exactly what lines I needed. However, finding none that did not read the whole contents of the file up to that line, I instead implemented the process described above. I overlooked SEEK. I dismissed it because it starts from a certain byte offset and not a certain line. Nevertheless, we can harness its power by simply padding each line with spaces to ensure every line in our file is the same byte length. With this pointer from Mark and some padding on the lines, knowing the line number and the number of bytes per line is enough to start reading from the exact location in the file that we desire.

MONK Data Under PhiloLogic: 1

2010-01-20T11:14:00.009-06:00

Introduction

As I'm sure you all know, the MONK Project (http://monkproject.org/), directed by Martin Mueller and John Unsworth, has generated a large collection of tagged data some of which has been made public and some of which is limited to CIC or other institutions (http://monkproject.org/downloads/). Each word in this group of different collections is tagged for part of speech, lemma, and normalization. Martin has documented the encoding scheme in great detail at http://panini.northwestern.edu/mmueller/nupos.pdf.

The following is a long post describing in some detail one approach to integrating this kind of information. Some of this will be deeply geeky and you can feel free to skip over sections. There is, towards the bottom of this post, a link to a standard PhiloLogic search form, so you can play with this proof-of-concept build yourself.

Richard and Helma have developed a mechanism to search for part of speech and lemma searching under PhiloLogic for their Greek and Latin databases (link). This is based on some truly inspired hacking by Richard and forms one model of how to handle this kind of functionality. My understanding of this, and Richard please correct me if I am wrong, is that it uses an undocumented feature in the index/search3 subsystem that allows us to have multiple index entries for each word position in the main index. This works and is certainly an approach to be considered as we think about a new series of PhiloLogic.

Build Notes

I have been experimenting with a somewhat different mechanism to handle this kind of problem, which is based on previous examples of mapping multiple word attributes to an index entry, using multiple field "crapser" entries. You may recall that this is the mechanism by which we merged Martin's virtual normalization data to very large collections of early modern English data and is currently running at Northwestern (link). My approach is to index not words, but pairs of surface forms and part of speech tags and to link these to an expanded (5 field) word database (called by crapser) containing the index form, surface form, lemma, part of speech and normalized forms. Here are some index entry forms (and frequencies):

24 conquer:vvb
445 conquer:vvi
143 conquered:vvd
414 conquered:vvn

These map to the word vector database which looks like:

idx               surf      pos        lem        normal
conquered:j     conquered    j       conquer     conquered
conquered:j-vvn conquered    j-vvn   conquer     conquered
conquered:n-vvn conquered    n-vvn   conquer     conquered
conquered:vvd   conquered    vvd     conquer     conquered
conquered:vvn   conquered    vvn     conquer     conquered

To build this I first reduced for fully verbose form of the data in which each token is tagged:

<w eos="0" lem="country" pos="n1" reg="COUNTRY" spe="COUNTRY">COUNTRY</w>

I eliminated all encoding that is redundant, just to make things easier to work with since the files are huge:

<w pos="n1">COUNTRY</w>

Where there is some additional information, I keep it in the encoded document:

<w lem="illustration" pos="n2">ILLUSTRATIONS</w>

I then loaded this data into a very slightly modified PhiloLogic textloader. This simply builds an index representation of the surface form of the word and the part of speech, by getting the PoS from encoding:

if ($thetag =~ /<w/) {
$thepartofspeech = "";
$thetag =~ m/pos="([^"]*)"/i;
$thepartofspeech = $1;
}

and adding this to the index entry:
$theword = $theword . ":" . $thepartofspeech;

When loaded to this point, you have modified index entries. The next step is simply to build a multi-field word vector database (crapser). I did this by reading the input data and adding entries for lemmas or normalizations. This is simply an extension of what is already documented in the "virtual-normalize" directory in the "goodies" in the PhiloLogic release.

The next step was to slightly modify a version of Leonid's original "gimme". The "sequential" version of this function (in the standard Philologic distribution), maps a multi-field (tab delimited) query using regexp patterns in egrep. This is fast and simple. It allows naming of fields, so you can simply specify "lem=justice" and it will generate a regular expression pattern (where TAB = the tab character):

^[^TAB]*TAB[^TAB]*TAB[^TAB]*TABjusticeTAB[^TAB]*$

And you get, of course, full regular expressions. (Note, this renders with some odd spacing, there are no spaces). Swap in this version of crapser and it all appears to run without further modification.

So, to summarize, the implementation does not require any modifications to core system components. It requires only slight modifications to a textloader, which we do all the time for specific databases, and a slightly modified "crapser" with a suitably build word vector database.

The Database

The database has 567 documents containing 38.5 million words (types) and 273,600 index entries. Recall that these are surface form words and part of speech tags and not normal types. The dataset has selections from various sources, including Documenting the American South as well as some British Early Modern texts. It should have full PhiloLogic search and reporting capabilities. You can query the words in the database as usual, simply by typing in words. To force searches on lemmas, normalizations, and parts of speech by specifying (with examples):

lem=conquer
nrm=conquer
pos=pns32

and finally, if you want to get one surface form and part of speech you can search the index entry directly, such as "conquered:vvd". Note that the Part of Speech is specified after a colon and you don't need to specify anything else. This is obviously not a real query interface, but it suggests how we can think about interfaces further along (eg, pull down menus, etc). You can also use regular expressions, such as lem=conque.* Finally, you can combine these, such as "pos=po.* lem=enemy", which means find forms of enemy followed by possessive pronous within three words, such as : "their most mortall enemies". You will need to consult Martin's discussion of the encoding to see all of the parts of speech. It is an extensive and well reasoned scheme.

After all of that, here is the search form. (Reloaded 7/28/11)

Now, before running of to play with this, there are some important notes following which describes how to use this in more detail.

Discussion

This is a proof-of-concept build. In a full implementation, I would need to add some search syntax to allow the user to indicate a set of combined criteria for a single word. I was having some problems coming up with a use case, but I guess one could want to say search for a particular lemma AND part of speech. It would all work with a little massaging. Aside from that, this simple model should support all of the standard PhiloLogic searching and reporting
features. Do let me know if you find something that does not work.

This model supports disambiguating searches, such as to find dog when it is used as a verb. Try "dog:vvi" for hits like "we can dog them" (thanks Russ for this example). It also appears to work properly form most other searches, such as lemmas, normalizations, etc. Part of speech for single entries looks reasonable in terms of performance.

My primary interest, however, in this experiment is to test performance on sequences of parts of speech searching. For example: "pos=po3. pos=j pos=n1" will find sequences like: "their strange confusion" and "his Princely wisedome". Chains of four also seem to work reasonably. Eg: "pos=vvn pos=po3. pos=j pos=n1" returns phrases like "neglected their even elevation", "stimulated their adventurous courage", and "aroused his little troop". You can always find a part of speech after a particular word (lemma): "after pos=po3.".

Now, this is all fine and dandy. Except that doing conjoined searches on parts of speech reveals a significant conceptual difficulty, which I believe also applies to Richard's implementation. Each part of speech generates thousands of surface form index entries. For example:
"pos=vvn pos=po3. pos=j pos=n1"
generates 81,000 unique terms (index entries) in 4 vectors. The evaluation then does a massive join at the level of index entry evaluation. So, it is SLOW and subject to possible memory buffer overflow or other problems. In fact, the system will begin to generate results of this type fairly quickly, due to PhiloLogic's lazy evaluation (start returning results as soon as you have a few). But it can take several minutes to complete the task. We would certainly not want to put this on a high traffic machine, since if you have many similar queries, it would bog it down. Obviously, we could simply test to make sure that users search criteria would not drag the whole system down or simply lock this database to one user at a time, or some other work around. If we got reasonable French NLP, this could be implemented quickly.

However, I believe we have bumped up upon a conceptual problem. To find POS1 and POS2 and POS3 either in a row or within N number of words requires an evaluation of word and/or part of speech positions in documents.

There are a couple of possible solutions, all of which would require consideration of distinct indexing structures. The first is simply to build another kind of NGRAM POS index which would have sequences of parts of speech indexed and mapped to document regions. The second would be a another kind of index which would look like a standard PhiloLogic index entry, except that it would be ONLY part of speech. This would reduce the size of the word vectors, but would not in itself improve the index evaluation to find those sequences that fit the query in the actual documents, since we still have to return to word positions in documents.

We might call this "The Conjoined Part of Speech Problem (CPSP)". It is, in my opinion, a highly specialized type of search and it is not clear just what the use cases might look like in relatively simple languages (English, French) as opposed to Greek, for which Helma makes a convincing case. So, there is a question of just how important this might be. In email communication, Martin makes the case that it would be and that researchers who want this kind of query would be willing to wait a few minutes.

It would be a trivial and useful experiment to run a load where I would index ONLY part of speech information. This would be a good test to see if evaluation speed for conjoined part of speech searches would be reasonable. In fact, Richard and I did a few quick experiments that suggest this would work. The idea would be to distinguish between simple queries -- and run them as usual -- and multiple PoS queries, which would be run on a dedicated index build. So, build parallel indicies. Oddly enuff, in the current architecture, I suspect that one could simply have a switch to say WHICH database to consult dynamically, simply by evaluating the query and then setting the database argument. That would be another one of my famous, award-winning, hall of shame hacks. But it could be made to work.

Martin has also pointed out another issue, which is searching, sorting, and counting of PoS, lemma, and other data. Now, that makes a lot of sense. I want to search for "country" and find distributions of particular parts of speech. Or, I want to do a collocation table searching on a lemma and counting the lemmas around the word. I think all of this is certainly doable -- the latter is something I wrote about some 15 years ago -- with hacks to the various reporting subsystems (not in 3, which is just too much of a mess). In an SOA model of PhiloLogic, this would be quite reasonably handled, ideally by other teams using PhiloLogic if not here at Chicago.

I think these are important issues to raise, but not necessarily resolve at this time, if (when?) we consider the architecture of any future Philologic4 development effort. For example, the current models of report generators would have to know about lemmas, etc. And we would need to at least leave hooks in any future model to support different indexing schemes for things like.

Finally, watch this space. I believe Richard is doing a build of this data using his model as well.

Please do play around with all of this and let me know what you think. One consideration would be implementing this for selected French collections. We would obviously need real virtual normalizers, lemmatizers and PoS identifiers for a broader range of French than we have now.

KWIC Modifications

2010-01-14T13:01:00.007-06:00

I have been working on getting a cleaner output format from KWIC for the Greek texts on Perseus. Helma was desirous of the KWIC output leaving in the word tags which occur in the Perseus texts in order that the word lookup function be usable directly from the KWIC results page. Since KWIC leaves as little formatting as possible, it strips out all tags, including the word tags, from the text. While I worked on that, I also added a few other modifications to KWIC to give a better look to the results page for the Greek texts.

The problem with KWIC for Greek texts is that Greek fonts to not support single-width fonts, which KWIC uses to align the results more cleanly. In addition, the title lines, which give the bibliographic information and link, can be different lengths and this also causes problems aligning the search terms. See for instance, this search.

To solve the word tag problem I just made a few modifications to the KwicFormat subroutine in philosubs. The main edit there was changing the line that stripped all tags into this:

$bf=~ s#<(?!(w |/w))[^>]*># #gi; #keep only word tags

For the alignment issue, things were more complicated. Keeping track of the length of the left side of the line doesn't allow for a consistent place on the page due to the differing widths of the letters. In the end, I modified artfl_kwic to chop the left side of the hit to a size as close to a certain length as possible without breaking any words. Previously, both the right and the left were chopped to a certain length regardless of breaking words and length including tags, often resulting in very little content. Now, only the length of the display string is accounted for and in addition the length is adjusted for the length of the bibliographic title.

I also added a span around the left and right sides of the hit to allow for positioning and alignment using Javascript (and CSS). Then, adding the following lines to the Results Header, the search terms are all lined up in a neat line:

span.left { right:46%; position:absolute; }
span.right { left:54.5%; position:absolute;
         height:18px; overflow:hidden;}

The numbers may look a little messy, but they give nice results. I found that without the decimal, the two sides were a bit too far apart, but there may be another way around that.

The extra bits for formatting the right span are in place of trimming the content of the right side in perl as I did for the left side. I found that the overflow:hidden attribute is quite handy if you can get it to work (it is a bit tempermental). As long as it is found in an absolutely positioned object with restricted size, AND it is contained within an element with overflow set to auto, it should work. It simply hides any content that does not fit within the given boundaries. It gives a very clean look to the right side of the page and even adjusts to different window sides so that the content never leaks to the next line.

Take a look at this page and play with the window size to see what I mean. Unfortunately, there is no such nice property for trimming the overflow off of the left side instead of the right side. That is why I did it in perl instead of Javascript. There is a function called clip in javascript which is designed to clip an image, but again the way it works makes it much easier to trim from the right side than the left side. One could probably twist the clip function enough to make something similar happen for the left side (and make everything nicely adjustable and lovely), but for now, it is happening in perl. (I tried for a while, but my concoctions just seemed to slow things down and not add anything exciting results).

UPDATE: I couldn't resist playing a bit more with the javascript, and now it works like I wanted it to! Now, if you click on the link above, it won't illustrate what I said it would, because the javascript has been improved. I added this function:

function trimKwicLines(){
var contentwidth = $(".content").width();
$(".left").each(function (i) {
var width = $(this).width();
var leftoffset = contentwidth*.4 - width*1 - 2;
$(this).css("left", leftoffset);
});
}

And changed things here and there in the CSS.

Natural Language Morphology Queries in Perseus

2009-12-14T13:28:00.007-06:00

Natural language queries are now possible on Perseus under Philologic. Previously, Richard had implemented searching for various parts of speech in various forms. For instance, as noted in the About page for Perseus, a search for 'pos:v*roa*' will return all the instances of perfect active aorist verbs in the selected corpus. Now, a search for 'form:could-I-please-have-some-perfect-active-optatives?' will return the same results. In fact, searching for 'form:perf-act-opt', 'form:perfect-active-optative', 'form:perfection-of-action-optimizations', or 'form:perfact-actovy-opts-pretty-please' will all accomplish this same task. Note that the dashes are necessary between the words, otherwise a search for plural nouns written as 'form:plural nouns' will actually be searching for any plural word followed by the word "nouns", which will fail. I carefully chose shorter forms of all the keywords, such as "impf" and "ind" for "imperfect" and "indicative" so that a search including any word starting with "ind" will match indicatives regardless of what follows the 'd'. Hopefully, there are no overlapping matches (such as using "im" to abbreviate "imperfect" which would also match "imperative"). If you do encounter any, please let me know. Potentially, we could put a list of acceptable abbreviations somewhere, although they are fairly straightforward and typing the full term out is always a fail-safe method.

Basically, the modified crapser script simply translates searches beginning with "form:" into the corresponding "pos:" search. Using a hash of regular expressions and string searching, it simply returns the corresponding code. In the previous example, the search is actually looking for "pos:....roa..". Notice that it fills in the empty space of the code with dots, allowing them to be anything. I implemented an alternative filler, the dash, so that when you search for something like "form:perf-act-opt-exact", you will actually be searching for "pos:----roa--" (and your search will fail because there are no terms that are only and exactly perfect active optative without other specifications).

One limitation that this method of natural language querying has is that it cannot match the versatility of the "pos:" searches. That is, because it selects either dots or dashes as fillers, you cannot get a mixture of them in your search. You cannot run a search such as "pos:v-.sroa---". However, this limitation will likely have little effect for the average user and the user needing such a search can still obtain it using the "pos:" method. An alternative method involving drop down input boxes for each slot of the code would enable the full power of the pos searches, but it would also be potentially more tedious to implement and potentially tedious to use as well. Such a input form would require the user to know more about the encoding than the "form:" searching I implemented does. For example, a user would need to know that "verb" is required in the first slot, even if "aorist optative" makes that the only possibility. Whereas searching for 'form:aorist-optative' works without the user ever needing to know that a 'v' is required in the first slot.

Encyclopédie: Similar Article Identification II

2009-12-14T12:09:00.005-06:00

After doing a series of revisions as part of my last post this subject (link), I thought it might be helpful to provide an update posting. We have been interested in teasing out how the VSM handles small vs large articles and to get some sense of why various similar articles are selected. Over the weekend, I reran the vector space similarity function on 39,218 articles, taking some 29 hours. I excluded some 150 surface forms of words in a stopword list, all sequences of numbers (and roman numerals), as well as features (in this case word stems) found in more than 1568 and less than 35 articles. This last step removed features like blanch, entend, mort, and so on. Thus, I removed some 600 features, leaving 10,157 features used for the calculation. Here is the search form:

The number of matching terms for small articles can be, of course, very small. For example, article "Tout-Bec" (62 words) is left with four stems [amer 1|oiseau 2|ornith 1|bec 3]. The first most of the most similar articles is Rhinoceros (Hist. nat. Ornith.) -- remember, only the main article here -- matches on three stems:

word               frq1     frq2
bec                 3        5
oiseau              2        2
ornith              1        1

Are these similar? Well, both very small articles refer to kinds of rare birds that are notable by their beaks, one with a very large beak and one that looks like it has two or more beaks. It is also important to note that "ornith" (the class of knowledge) in both is picked up by this example. The next article down (Pipeliene) matches on:

amer                1        1
bec                 3        1
oiseau              2        2

The third most similar in this example is "Connoissance des Oiseaux par le bec & par les pattes.", a plate legend, with as you expect, lots of beaks. This matches on two stems, bec and oiseau.

It seems that the size of the query article, now that I have eliminated many function words and other extraneous data, carries a significant impact. The larger the article, the more possible matches you will get (Zipf's Law applies). Longer articles will tend to be most similar to other longer articles, and shorter will match better to shorter. So, similarity would appear to be a function of relative frequencies of common features and the length of the articles. We saw this in our original examination of the Encyclopédie and the Dictionnaire de Trévoux, and had built in some restrictions in terms of size as well as comparing articles with the same first letter rather than all to all. As far as I can tell, the kind of more of feature pruning shown here does not have a significant impact on larger articles.

User feedback might be significant in determining just how many features and what kinds of features are required to get more interesting matches. For any pair, we could store the VSM score, the sizes, and the matching features along with the user rating of the match. That might generate some actionable data for future applications.

[Aside: In some cases, similar passages lead to possibly related plates and legends. Cadrature, for example, links to numerous plate legends dealing with clockmaking.]

Mapping Encyclopédie classes of knowledge to LDA generated topics

2009-12-13T17:06:00.000-06:00

As was described in my previous blog entry, I've been working on comparing the results given by LDA generated topics with the classes of knowledge identified by the philosophes in the Encyclopédie. My initial experiment was to try to see if out of 5000 articles belonging to 100 classes of knowledge, with 50 articles per class, I would find those 100 topics using an LDA topic modeler. My conclusion was that it didn't find all of them, but still found quite a few. Since then, I have played a bit more with this dataset and have come up with better results.

Since a topic modeler will give you the topic proportion per article (I just use the top three), what I tried to do this time was to draw up a table with each class of knowledge, and what the topic modeler identified in terms of topics for each class of knowledge. Before looking at this, it's important to keep in mind that in the sample of articles I used, there are 50 articles per class of knowledge. Therefore, the closer the number of the dominant topic in a class of knowledge gets to 50, the better the topic modeler will have done in identifying the class of knowledge and in reproducing the human classification.

Of course, the classification of articles in the Encyclopédie can be at times a little puzzling. The articles were written by a large number of people and therefore the classification is not always consistent. With that in mind, one should not expect to get perfect matches using a topic modeler. Moreover, since the topic modeler will assume that each article is about N number of topics, the calculation might be further off.
For my experiment, I settled on 107 topics, of which I eliminated 7, which were identified as stopwords lists. When looking at the results of this experiment, there are 41 classes of knowledge in which we find 40 or more articles grouped within the same LDA topic. This means that 41% of the classes of knowledge were identified with a great level of accuracy. If we look at topics that have more than 25 articles matching the same class of knowledge we get up to 83 classes (or 83%).

If we look at those results, there are strange flaws, such as physique and divination that don't seem to be identified. This might be due to a miscalculation, but I have yet to figure out what it could be. Highly specialized classes, such as corroyerie, poésie, or astronomie get excellent matches, which is to be expected.
This experiment also gave us an idea of what the percentage of LDA topics are to be considered as stopwords lists. Between 5 and 10% of the topics should be discarded when using an LDA classifier.
Finally, we should consider that LDA generated topics do not systematically match human identified topics. An unsupervised model is bound to give different results, it would be interesting to see how well supervised LDA (sLDA) would do in our particular test case.

Index Design Notes 1: PhiloLogic Index Overview

2009-12-07T10:09:00.005-06:00

I've been playing around with some perl code in response to several questions about the structure of PhiloLogic's main word index--I'll post it soon, but in the meantime, I thought I'd try to give a conceptual overview of how the index works. As you may know, PhiloLogic's main index data structure is a hash table supporting O(1) lookup of any given keyword. You may also know that PhiloLogic only stores integers in the index: all text objects are represented as hierarchical addresses, something like a normalized, fixed-width Xpointer.

Let's say we can represent the position of some occurrence of the word "cat" as
0 1 2 -1 1 12 7 135556 56
which could be interpreted as
document 0,
book 1,
chapter 2,
section ,
paragraph 1,
sentence 12,
word 7,
byte 135556,
page 56, for example.

A structured, positional index allows us to evaluate phrase queries, positional queries, or metadata queries very efficiently. Unfortunately, storing each of these 9 numbers as 32-bit integers would take 36 bytes of disk space, for every occurence of the word. In contrast, it's actually possible to encode all 9 of the above numbers in just 39 bits, if we store them efficiently--that's a 93% saving. The document field has the value 0, which we can store in a single bit, whereas byte position, our most expensive, can be stored in just 18 bits. The difficulty being that the simple array of integers becomes a single long bit string stored in a hash. First we encode each number in binary, like so
0 1 01 11 1 0011 111 001000011000100001 000111

but this is only 18 bits, so we have to pad it off with 6 extra bits to get an even byte alignment, and then we can store it in our hash table under "cat".

Now, suppose that we use somthing like this format to index a set of small documents with 10,000 words total. We can expect, among other things, a handful of occurrences of "cat", and probably somewhere around a few hundred occurrences of the word "the". In a GDBM table, duplicate keywords aren't permitted--there can be exactly one record of "cat". For a database this size, it would be feasible to append every occurrence into a single long bit string Let's say our text structures require 50 bits to encode, and that we have 5 occurrences of cat. We look up "cat" in GDBM, and get a packed bit string 32 bytes, or 256 bits long. we can divide that by the size of a single occurrence, so we know that we have 5 occurrences and 6 bits of padding.

"The", on the other hand, would be at least on the order of few kilobytes, maybe more. 1 or 2 K of memory is quite cheap on a modern machine, but as your database scales into the millions of words, you could have hundreds of thousands, even millions of occurrences of the most frequent words. At some point, you will certainly not want to have to load megabytes of data into memory at once for each key-word lookup. Indeed, in a search for "the cat", you'd prefer not to read every occurrence of "the" in the first place.

Since PhiloLogic currently doesn't support updating a live database, and all word occurrences are kept in sorted order, it's relatively easy for us to devise an on-disk, cache-friendly data structure that can meet our requirements. Let's divide up the word occurences into 2-kilobyte blocks, and keep track of the first position in each block. Then, we can rapidly skip hundreds of occurrences of a frequent word, like "the", when we know that the next occurence of "cat" isn't in the same document!

Of course, to perform this optimization, we would need to know the frequency of all terms in a query before we scan through them, so we'll have to add that information to the main hash table. Finally, we'd prefer not to pay the overhead of an additional disk seek for low-frequency words, so we'll need a flag in each key-word entry to signal whether we have:
1) a low frequency word, with all occurences stored inline
or
2) a high frequency word, stored in the block tree.

Just like the actual positional parameters, the frequencies and tree headers can also be compressed to an optimal size on a per-database level. In philologic, this is stored in databasedir/src/dbspecs.h, a c header file that is generated at the same time as the index, then compiled into a custom compression/decompression module for each loaded database, which the search engine can dynamically load and unload at run time.

In a later post, I'll provide some perl code to unpack the indices, and try to think about what a clean search API would look like.

Encyclopédie: Similar Article Identification

2009-12-03T11:22:00.015-06:00

The Vector Space Model (VSM) is a classic approach to information retrieval. We integrated this as a standard function in PhiloMine and have used it for a number of specific research projects, such as identifying borrowings from the Dictionnaire de Trévoux in the Encyclopédie, which is described in our forthcoming paper "Plundering Philosophers" and related talks[1]. While originally developed by Gerard Salton[2] in 1975 as a model for classic information retrieval, where a user submits a query and gets results in an ranked relevancy list, the algorithm is also very useful to identify similar blocks of text, such as encyclopedia articles or other delimited objects. Indeed, this kind of use of the VSM was proposed by Salton and Singhal[3] in a paper presented months before Salton's death. They demonstrated the use of VSM to produce links between parts of documents, forming a type of automatic hypertext:

The capability of generating weighted vectors for arbitrary texts also makes it possible to decompose individual documents into pieces and explore the relationships between these text pieces. [...] Such insights can be used for picking only the "good" parts of the document to be presented to the reader.

Salton and Singhal further argued that manual link creation would be impractical for huge amounts of text, but these conclusions may have had limited influence given the general interest at that time in human generated hypertext links on the WWW.

Based on earlier work using PhiloMine, we have seen a number of "interesting" -- and at times unexpected -- connections between articles in the Encyclopédie, often drawing connections between previously unrelated articles, if by unrelated we mean having different authors, classes of knowledge and few cross-references (renvois) between them. One might consider this kind of similarity measure between articles as a kind of intertextual discovery tool, where the system would propose articles possibly related to a specific article.

The Vector Space Model functions by comparing a query vector to all of the vectors in a corpus, making it an expensive calculation, not always suitable to real time use. In this experiment, I have recast the VSM implementation in PhiloMine to function as a batch job to generate a database of 27,753 Encyclopédie articles (those with 100 or more words) with the 20 most similar articles for each article. To do this, I pruned features (word stems) which more than 8,325 and less than 41 articles, resulting in a vector size of 10,431 features. I used a standard French word stemmer to reduce lexical variation and a Log Normalization function to handle variations in article sizes. The task took about 17 hours to run.

Update (December 7): I have replaced the VSM build above with the same on 39,200 articles -- all articles with 60 or more words -- which took about 29 hours to run. I pruned features found in more than 11,200 documents and less than 50, leaving 9,710 features. This may change some results by adding more small articles. Note, this is about as large a VSM task as can be performed in memory using perl hashes, since anything large runs out of memory. If we want to go larger, probably store vectors on disk and TIE them to perl hashes.

The results for a query shows the 20 most similar articles, ranked by the similarity score, where an exact match is equal to 1. For example, the article OUESSANT (Modern Geography) -- based on 27,000 articles -- is related to the articles VERTU [0.274], Luxe [0.267], ECONOMIE ou OECONOMIE [0.265], POPULATION [0.263], CHRISTIANISME [0.261], SOCIÉTÉ [0.256], AVERTISSEMENT DES ÉDITEURS (suite) [0.255], MANICHÉISME [0.254], CYNIQUE, secte de philosophes anciens [0.254], Gout [0.250], EDUCATION [0.248] and so on. This reflects the discussion of the moral conditions of the inhabitants of the small island off the coast of Brittany.

You can give it a try using this form (again now for 39,200 articles):

[Dec 9: I added word count info for each article. You can restrict searches to articles in ranges of size. Also, now storing 50 top matches, which you can limit. Showing matching articles which are smaller than source article. Dec 10: added function to display matching stems for any pairwise comparison for inspection.]

There are a number of other options that I might add to the VSM calculations, including using TF-IDF as an alternative normalization weighting scheme and use of virtual normalization to again reduce lexical variations and improve the performance of the stemming algorithm. I have also thought of using Latent Semantic Analysis as another way to handle similarity weighting, but given that we have many query terms, it is not clear that LSA would help all that much.

In a real production environment, I think we will add a "similar article link" from articles in the Encyclopédie. We have talked about having users rank the quality of the similarity performance. The scores assigned are somewhat helpful in ranking, but not in assessing an absolute number, since they can vary by the size of the input article. VSM is an unsupervised learning model. It is not clear to me that we could integrate user evaluations in any systematic fashion, but this is certainly an interesting subject of further consideration.

As always, please let me know what you think. I have a couple of general queries. I have used main and sub articles (as well plate legends, etc.) as units of similarity calculation. Should I use main entries only? I also limited this to articles with more than 100 words. At 50 words, we have some 43,000 articles. Should I do this for a full implementation?

References

[1] See Timothy Allen, Stéphane Douard, Charles Cooney, Russell Horton, Robert Morrissey, Mark Olsen, Glenn Roe, and Robert Voyer, "Plundering Philosophers: Identifying Sources of the Encyclopédie", Journal of the Association for History and Computing (forthcoming 2009). Also, see Ceglowski, Maxiej. 2003: "Building a Vector Space Search Engine in Perl", Perl.com [http://www.perl.com/pub/a/2003/02/19/engine.html].

[2] Salton, G., A. Wong, and C. S. Yang. 1975: "A Vector Space Model for Automatic Indexing," Communications of the ACM 18/11: 613-620.

[3] Singhal, A. and Salton, G. 1995: "Automatic Text Broswing Using Vector Space Model" in Proceedings of the Dual-Use Technologies and Applications Conference 318-324.

Frequencies in the Greek and Latin texts

2009-11-20T15:39:00.007-06:00

Earlier this year Mark built a frequency query for the French texts (affectionately named wordcount.pl)

Kristin has now implemented this for our Greek and Latin texts. If you wonder what's new about this: Word count for individual documents has always been there in PhiloLogic loads, but the difference here is that you can see frequencies over the entire corpus, or a subset of works/authors.

You can find the forms here:
http://perseus.uchicago.edu/LatinFrequency.html
http://perseus.uchicago.edu/GreekFrequency.html

Update: Forms moved to the 'production site', perseus.uchicago.edu. You can now specify genre as well. Stay tuned for further stats, meant to provide a friendly reminder of Zipf's Law.

Note: the counts are raw frequency counts, without lemmatization.

I have edited the search form a tiny bit - let me know if you encounter any problems.

Do LDA generated topics match human identified topics?

2009-11-18T14:41:00.009-06:00

I've been experimenting lately on how LDA generated topics and the Encyclopédie classes of knowledge match. The experiment was conducted in the following way:

- I chose 100 classes of knowledge in the Encyclopédie, and picked 50 articles of each.

- I then ran a first LDA topic trainer choosing 100 topics.

- I then proceeded to identify each generated topic and name after the Encyclopédie classes of knowledge.

- My plan was then to look at the topic proportions per article and see if the top topic would correspond to its class of knowledge. Would the computer manage to classify the articles in the same way the encyclopedists had?

I was not able to get that far when choosing 100 topics for my first LDA run. This is because LDA will always generate a couple topics which aren't really topics, but are just lists of very common words and they just happen to be used in the same documents. Therefore, one should always disregard these topics and focus on the others. What this means is that I had to add a couple more topics to my LDA run in order to get 100 identifiable topics. So I settled with 103 topics. I found 3 distributions of words which were unidentifiable, so I dismissed them.

The results show that LDA topics and the Encyclopédie classes of knowledge do not match (see links to results below). Some do very well, like Artillerie, for which the corresponding distribution of words is :

canon piece poudre artillerie boulet fusil ligne calibre mortier bombe feu charge culasse livre met chambre pouce lumiere roue affut diametre coup batterie levier bouche ame flasque balle tourillon tire

Other distribution of words make sense in themselves but do not match any of the original classes of knowledge. For instance, there is no topic on 'teinture', 'peinture'. What we get instead is a mixture of both classes of knowledge which could be identified as colors :

couleur rouge blanc bleu tableau jaune verd peinture ombre teinture noir toile tableaux nuance papier etoffe bien teint peintre pinceau trait teinturier melange veut figure teindre feuille beau sert colle

Now the topic modeler is not wrong here. It's telling us that these words tend to occur together, which is true. Another significant example is the one with 'Boutonnier', 'Soie', and 'Rubanier' :

soie fil rouet corde brin tour main bouton gauche longueur boutonnier droite attache bout fils tourner sert molette noeud cordon doigt piece emerillon moule broche ouvrage ruban rochet branche aiguille

What we get here is a topic about the art of making clothes, which is more general than 'Boutonnier' or 'Rubanier'.

For this to actually work, the philosophes would have had to have been extremely rigorous in their choice of vocabulary, because this is what LDA expects. Also, another problem is that LDA considers that each document is a mixture of topics, and not made out of one topic. So if one document is exclusively focused on one topic, LDA will still try to extract a certain number of topics out of it. If this is the case, then you are going to get some topics which are mere subdivisions of the class of knowledge in this document. The reason why our experiment broke down could be that the LDA topic trainer created new subdivisions for some classes of knowledge, or regrouped several classes of knowledge. These are all valid as topics, but do not correspond to human identified topics.

Link to results

Section Highlighting in Philologic

2009-11-13T10:12:00.002-06:00

In many of the Perseus texts currently loaded under philologic, the section labels would overlap and be unreadable. These labels come from the milestone tags in the xml text and are placed along the edge of the text. One particularly problematic text in this regard was the New Testament, as the sections were verses and were thus often small sections of text.

In order to fix the overlapping issue, I wrote a little bit of javascript to hide the tags which would be placed in the same position as a previous tag. I also added a function to recalculate this if the window is resized. My main function is fairly simple:

function killOverlap (){
$lastOffset = 0;
$(".mstonecustom").each(function (i) {
if (this.offsetTop == $lastOffset){
this.className = "mstonen2";
}
else {
$lastOffset = this.offsetTop;
}});}

I also added a function which highlights a section when you hover over its milestone label along the side of the text. This seems useful to me, as often it is helpful to know where a section starts and ends. This was a slightly more complex problem. I had to alter the citequery3.pl script in order to add a span tag and some ids in order to get the javascript to work. The javascript was then fairly simple:

In order for it to work though, you have to alter the citequery3.pl script with this:

my $spanid = $citepoints{$offsets[$offset]};
$spanid =~ s/.*\.([0-9]+)\.([0-9]+)$/a$1b$2/;
#...
$tempstring =~ s/(^<[^>]+>)/$1<span class="mstonecustom" id="$spanid">$citepoints{$offsets[$offset]}<\/span>/;
#... {
$tempstring =~ s/<span class="mstonecustom" id="$spanid">$citepoints{$offsets[$offset]}<\/span>//;}

$milesubstrings[$offset] = "<span class=" . $citeunits{$offsets[$offset]} . " id="text">" . $tempstring . "<\/span>";

That's about it. It may come in useful again someday. For an example, take a look at this.

Towards PhiloLogic4

2009-11-02T10:55:00.010-06:00

Earlier this year I wrote a long discussion paper called "Renovating PhiloLogic" which provided an overview of the system architecture, a frank review of the strengths and (many) failings of the current implementation of the 3 series of PhiloLogic, and proposed a general design model for what would effectively be a complete reimplementation of the system, retaining only selected portions of the existing code base. While we are still discussing this, often in great detail, a few general objectives for any future renovation have emerged, including:

service oriented architecture;
release of new system in perl module libraries;
multiple database query support, and,
options for advanced or extended indexing models.

I will be putting together a public version of this discussion draft in the near future and will blog it when I have something ready.

Before sallying forth to do start working on a PhiloLogic4, there are a number of preliminary steps that Richard and I agree are required in order to 1) support the existing PhiloLogic3 series, and 2) clear the existing (messy) code base of some of the most egregious sections of the system, most notably the loader. Some of these are simply housekeeping and updates, some of these are patches and bug fixes, and some others are clean-ups which should streamline the current system and help in any redevelopment.

We will start by retasking one of our current machines, a 32 bit OS-X installation, to be the primary PhiloLogic development machine. We will also get the Linux branch on a 32 bit Linux machine (flavor to be determined). There is a known 64 bit installation problem which we will address at the end of this initial process. When we reach the right step, we will install it all on 64 bit machines and fix it then, hopefully with much less effort on a streamlined version, while releasing upgraded 32 bit versions on the way. The other element for our consideration is the degree to which we can merge the OS-X and Linux branches of the system. Right now, we have two completely distinct branches. It would be much better to have one, which we think may be accomplished in a couple of different ways.

We are currently thinking of 4 distinct steps, which should each result in new maintenance releases of PhiloLogic3.

Step One

Apply the most recent OS-X Leopard patch kit to both the OS-X and Linux branches as required and feasible. This is the patch kit that Richard and I assembled for the migration to our new servers and has some nifty little extensions. We will also be updating the PhiloLogic code release site (Google Code) and retooling the new PhiloLogic site, which will then be referred from the existing location (philologic.uchicago.edu). Maintenance release when done. [MVO]

Step Two

The PhiloLogic loader currently using a GNU Makefile scheme to load databases. This made good sense many years ago, when loads could take many hours (or days), but is probably no longer needed. There are also many places where we use various utilities (sed, gawk, gzip, etc.) which add complications and make the entire scheme more brittle. Our current thinking is to fold all of the Makefile functions into a revised version of philoload, but may determine a better way to proceed once we get into it. We're planning a maintenance release of this when done. [MVO]

Step Three

The current PhiloLogic loader performs a number of C compiles, many of which are no longer needed. For example, the system still compiles the search2 binaries. These were left in Philologic3 in order to have backwards compatibility. We need to keep the ability to generate the correct pack and unpack libraries which are used by search3. Once we have cleared out all unnecessary C compiles, we will investigate a couple of known bugs in search3, and attempt to resolve these. Again, once done, we would do a maintenance release. [RW and MVO]

Step Four

As noted above, some users have reported 64 bit compile problem on either installation or load. Once we have the loader streamlined, eliminating as much of the old C compiles are possible, we will investigate this problem. We're hoping that this will be easily remedied and, even better, could be resolved in a combined release which would merge the current OS-X and Linux branches. This would be the terminal release of the PhiloLogic3 series. Any future releases would be only for bug fixes.

We hoping that these steps will result in a stable terminal release of the PhiloLogic3 series, which will be easier to install and use. It will also result in significant streamlining which will help in any future Philologic renovation or a new PhiloLogic4 series.

This is an initial plan, so please do post your comments, suggestions, and complaints.

Encyclopédie under KinoSearch

2009-10-29T10:54:00.022-05:00

One of the things that I have wanted to do for a while is to examine implementations of Lucene, both as a search tool to complement PhiloLogic and possibly as a model for future PhiloLogic renovations. Late this summer, Clovis identified a particular nice open source, perl implementation of Lucene called KinoSearch. This looks like it will fit both bills very nicely indeed. As a little experiment, I loaded 73,000 articles (and other objects) from the Encyclopédie, and cooked up a super simple query script. This allows you to type in query words and get links to articles sorted by their relevancy to your query (the italicized number next to the headword). At this time, I am limiting to the top 100 "hits". Words should be lower case, accents are required, and words should be separated by spaces. Try it:

Query Words: or
Require all words

Here are a couple of examples which you can block copy in: artisan laboureur ouvrier paysan malade symptome douleur estomac
peuple pays nation ancien république décadence

The first thing to notice is search speed. Lucene is known to be robust, massively scalable, and fast. The KinoSearch implementation is certainly very fast. A six term search returns in a real .35 seconds and less than 1/10 of a second of system time, using time on the command line. I did not time the indexing run, but think 10 minutes or so. [Addition: by reading 147 TEI files rather than 77,000 split files, the loading indexing time for the Encyclopédie is falls to (using time) real 2m45.9s, user 2m33.8s sys 0m11.1s.]

The KinoSearch developer, Marvin Humphrey, has a splendid slide show, outlining how it works, with specific reference to the kind of parameters, such as stemmers and stopwords, that one needs to consider as well as an overview of the indexing scheme. Clovis and I thought this might be the easiest way to begin working with Lucene, since it is a perl module with C components, so it is easy to install and get running. Given the performance and utility of KinoSearch, I suspect that we will be using it extensively for projects where ranked relevancy results are of interest. These might include structured texts, such as newspaper and encyclopedia articles, and possibly large collections of uncorrected OCR materials which may not suitable for text analysis applications supported by PhiloLogic. Also, on first review, the code base is very nicely designed and, since it has many of the same kinds of functions as PhiloLogic, strikes me as being a really fine model of how we might want to renovate PhiloLogic.

For this experiment, I took the articles as individual documents in TEI, which Clovis had prepared for other work. For each article, I grabbed the headword and PhiloLogic document id, which are loaded as fielded data. The rest of the article is stripped of all encoding and loaded in. It would be perfectly simple to read the data from our normal TEI files. We could see simply adding a script that would load source data from a PhiloLogic database build, to add a different kind of search, which would need to have a different search box/form.

I have not played at all with parameters and I can imagine that we would want to perform some functions, such as using simple rules for normalization, on input, since it uses a stemmer package also by M Humphrey. Please email me, post comments, or add a blog entry here if you see problems, particularly search oddities, have ideas about other use cases, or more general interface notions. I will be writing a more generalized loader and query script -- with paging, numbers of hits per page, filtering by minimum relvancy scores and looking at a version of the Philologic object fetch which would try to high-light matching terms -- and moving that over to our main servers.

back to comparing similar documents

2009-10-26T14:35:00.002-05:00

I mentioned a little while ago some work I did on comparing one document with the rest of the corpus it belongs to ( the examples I used in that blog post will not give the same results anymore, the results might not be as good, I haven't optimized the new code for the Encyclopédie yet). The idea behind it was to use the topic proportions for each article generated from LDA, and come up with a set of calculations to decide which document(s) was closest to the original document. The reason why I'm mentioning here once more is that I've been through that code again, cleaned it up quite a bit, improved its performance, tweaked the calculations. Basically, I made it usable for other people but myself. Last time I built a basic search form to use with Encyclopédie articles. This time I'm going to show the command line version, which has a couple more options than the web version.
In the web version, I was using both the top three topics in each document, and their individual proportion within that document. For instance, Document A would have topic 1, 2 and 3 as its main topics. Topic1 would have a proportion of 0.36, Topic2 0.12, Topic3 0.09. In the command line version, there's the option of only using the topics, without the proportion. The order of importance of each topic is of course still respected. Depending on the corpus you're looking at, you might want to use one model rather than the other. It does give different results. One could of course tweak this some more and decide to only take the proportion of the prominent topic, therefore giving it more importance. There is definitely room for improvement.
There was also another option that was left out of the web version. By default, I set a tolerance level, that is the score needed by each document in order to be given as a result of the query. In the command line version, I made it possible to define this tolerance in order to get more or fewer results. This option is currently only possible with the refined model (the one with topic proportions). The code is currently living in
robespierre:/Users/clovis/LDA_scripts/
It's called compare_to_all.pl. There's some documentation in the header to explain how to use it. It's fairly simple. I might do some more work on it, and will update the script accordingly.
There are other applications of this script besides using on a corpus made of well defined documents. One could very well imagine applying this to a corpus subdivided in chunks of text using a text segmentation algorithm. On could then try to find passages on the same topic(s) using a combination of LDA and this script. The Archives parlementaires could be a good test case.
Another option would be to run every document of a corpus against the whole corpus and store all the results in a SQL database. This would allow having a corpus where each document can be linked to various others according to the mixture of topics they are made of.
I will try to give more concrete results some time soon.

Supervised LDA: Preliminary Results on Homer

2009-10-26T11:30:00.002-05:00

While Clovis has been running LDA tests on Encyclopédie texts using the Mallet code, I have been running some tests using the sLDA algorithm. After a few minor glitches, Richard and I managed to get the sLDA code, written by Chong Wang and David Blei, from Blei's website up and running.

Unlike LDA, sLDA (Supervised Latent Dirichlet Allocation), requires a training set of documents paired with corresponding class labels or responses. As Blei suggests, these can be categories, responses, ratings, counts or many other things. In my experiments on Homeric texts, I used only two classes, corresponding to Homer's two major works: the Iliad and the Odyssey. Akin to LDA, topics are inferred from the given texts and a model is made of the data. This model, having seen the class labels of the texts it was trained on, can then be used to infer the class labels of previously unseen data.

For my experiments, I modified the xml versions of the Homer texts that we have on hand using a few simple perl scripts. Getting the xml transformed into an acceptable format for Wang's code required a bit of finagling, but was not too terrible. My scripts first took the xml and split it into books (the 24 books of the Iliad and likewise for the Odyssey), then stripped the xml tags from the text. Saving out four books from each text for applying the inference step, I took the rest of the books and output the corresponding data file necessary for input into the algorithm (data format here).

I played around a bit with leaving out words that occurred extremely frequently or extremely rarely. For the results I am posting here, the English vocabulary was vast and I cut it down to words that occurred between 10 and 60 times. This probably cuts it down too much though, so it would be good to try some variations. Richard has suggested also cutting out the proper nouns before running sLDA in order to focus more on the semantic topics. For the Greek vocabulary, I used the words occurring between 3 and 100 times, after stripping out the accents.

Running the inference part of sLDA on the 8 books that I had saved out seemed to work quite well. It got all 8 correctly labeled as to whether they belonged to the Iliad or to the Odyssey. In a reverse run, the inference was able to again achieve 100 percent accuracy on labeling the 40 books after having been trained on only the 8 remaining books.

The raw results of the trials give a matrix of betas with a column for each word, and a row for each topic. These betas thus give a log based weighting of each word in each topic. Following this are the etas, with a column for each topic and a row for each class. These etas give the weightings of each topic in each class, as far as I understand it. Richard and I slightly altered the sLDA code to output an eta for each class, rather than one less than the number of classes as it was giving us. As far as we understand the algorithm as presented in Blei's paper, it should be giving us an eta for each class. Our modification didn't seem to break anything, so we are assuming that it worked, as the results seem to be looking nice. Using the final model data, I have a perl script that outputs the top words in each topic along with the top topics in each class. These are the results that I am giving below.

Results of my sLDA Experiments on Homer:

English Text: 10 Topics Greek Text: 10 Topics

25 Topics 25 Topics

50 Topics 50 Topics

75 Topics 75 Topics

100 Topics 100 Topics

150 Topics 150 Topics

200 Topics 200 Topics

250 Topics 250 Topics

Also, samples of the output from Blei and Wang's code, corresponding to the English Text with 100 topics:

Final Model: gives the betas and the etas which I used to output my results
Likelihood: the likelihood of these documents, given the model
Gammas
Word-assignments

Inferred Labels: Iliad has label '0', Odyssey has label '1'.
Inferred Likelihood: the likelihood the previously unseen texts
Inferred Gammas

I have not played around much with the gammas, but they seem to give a weighting of each topic in each document. Thus you could figure out for which book of the Iliad or the Odyssey a specific topic was the most prevalent. It would be interesting to see if this correctly pinpoints which book the cyclops comes in for instance, as this is a fairly easily identifiable topic in most of the trials.

Encyclopédie Renvois Search/Linker

2009-10-22T14:08:00.002-05:00

During the summer (2009), a user (UofC PhD, tenured elsewhere) wrote to ask if there was any way to search the Encyclopédie and "generate a list of all articles that cross-reference a given article". We went back and forth a bit, and I slapped a little toy together and let him play with it, to which his reply was "Oh, this is cool! Five minutes of playing with the search engine and I can tell you it shows fun stuff...". This is, of course, an excellent suggestion which we have talked about in the past, usually in the context of visualizing relationships of articles in various ways. At the highest level, visualizing the relationships of the renvois is what Gilles and I attempted to do in our general "cartography paper"[1] and, more recently, Robert and Glenn (et. al.) tried, in a radically different way, to do in their work on "centroids"[2].

The current implementation of the Encyclopédie under PhiloLogic will allow users to follow renvois links (within operational limits to be outlined below), but does not support searching and navigating the renvois in any kind of systematic fashion. Since this is something I think warrants further consideration, I thought it might be helpful to document this toy, give some examples, let folks play with it, outline some of the current issues, and conclude with some ideas about what might be done going forward.

To construct this toy, I wrote a recognizer to extract metadata for each article in the Encyclopédie which has one or more renvois. As part of the original development of the Encyclopédie, each cross reference was automatically detected from certain typographic and lexical clues. This resulted in roughly 61,000 cross-references. Accordingly, the extracted database has 61,000 records. I loaded these into a simple MySQL database and used a standard script to support searching and reporting. The search parameters may include articles headwords, authors, normalized and English classes of knowledge as well as the term(s) being cross referenced. For example, there are 39 cross-referenced article pairs for the headword estomac. As you can see from the output, I'm listing the headword, author, classes of knowledge, and the cross referenced term. You can get the article of the cross referenced term or the cross-references in that article. Thus, the second example shows the link to Digestion:

ESTOMAC, ventriculus (Tarin: Anatomie, Anatomy ) ==> Digestion || renvois
[The renvois of Digestion find 56 articles pairs, including one to intestins]
DIGESTION (Venel: Economie animale, Animal economy ) ==> Intestins || renvois
Intestins (unknown: Anatomie, Anatomy ) ==> Chyle || renvois

and so on ==>lymphe==>sang==>ad nauseum. No, there is no ad nauseum, just how you might feel after going round and round.

Now, there are problems, but please go ahead and play with this now using the submit form, as long as you promise to come back and read thru the rest of this and let me know about any other problems.

Problems

As noted above, the renvois were identified automatically. And as with most of these things, it worked reasonably well. But you will see link errors and other things which indicate problems. Glenn reported these to me and I was going to eliminate them. On second thought, this little toy lets to consider the renvois rather more systematically. Where you see a link error is (probably) a recognizer error, which either failed to get a string to link or got confused by some typography. The linking mechanism itself is based on string searches. In other words, whenever you click on a renvois, you are in fact performing a search on the headwords. This simple heuristic works reasonably well, returning string matched headwords. In some cases, you get nothing because there is no headword that has the renvois word(s), and at other times you will get quite a list of articles, which may or may not include what the authors/editors intended. It is, of course, well known that many renvois simply don't correspond to an article and many others differ in various ways from the article headwords. I am also applying a few rules to renvois searching to try to improve recall and reduce noise. So, this also adds another level of indirection.

Now, ideally, one would go through the entire database, examine each renvois and build a direct link to the one article that the authors/editors intended. But we're talking 60,000+ renvois against 72,000 (or so) articles and it is not clear that humans could resolve this in many instances. When Gilles and I worked on this, we used a series of (long forgotten) heuristics to filter out noise and errors. So, this simple toy works within operational limits and gives us a way to more systematically identify possible errors and ways to improve it.

Future Work

Aside from being a quick and dirty to way get some notion of errors in the renvois, we might be able to make this more presentable. Please feel free to play with this and suggest ways to think about. In the long haul, I would love a totally cool visualization. A clickable directed graph, so you could click on a node and re-center it on another article, or class of knowledge or author. Maybe something like Tricot's representation of the classes of knowledge. Or maybe something like DocuBurst. Marti Heast's chapter on visualizing text analysis, is a treasure-trove of great ideas.

For the immediate term, I would like to recast this simple model to allow the user to specify number of steps. So, set the number of iterations to follow, so you would get something like:


ESTOMAC, ventriculus (Tarin: Anatomie, Anatomy ) ==> Digestion || renvois
  DIGESTION (Venel: Economie animale, Animal economy ) ==> Intestins || renvois
        Intestins (unknown: Anatomie, Anatomy ) ==> Viscere || renvois
ESTOMAC, ventriculus (Tarin: Anatomie, Anatomy ) ==> Chyle || renvois
  CHYLE (Tarin: Anatomie | Physiologie, Anatomy. Physiology ) ==> Sanguification || renvois
        SANGUIFICATION (unknown: Physiologie, Physiology ) ==> Respiration || renvois
              RESPIRATION (unknown: Anatomie | Physiologie, Anatomy | Physiology ) ==> Air || renvois

Following this chains of renvois either until you run out or your hit an iteration limit. I will try to follow this up with both the multi-iteration model and see if I can recover some of what Liz tried to do using GraphViz to generate clickable directed graphs.

References

[1] Gilles Blanchard et Mark Olsen, « Le système de renvoi dans l’Encyclopédie: Une cartographie des structures de connaissances au XVIII^e siècle », Recherches sur Diderot et sur l'Encyclopédie, numéro 31-32 L'Encyclopédie en ses nouveaux atours électroniques: vices et vertus du virtuel, (2002) [En ligne], mis en ligne le 16 mars 2008.

[2] Charles Cooney, Russell Horton, Robert Morrissey, Mark Olsen, Glenn Roe, and Robert Voyer, "Re-engineering the tree of knowledge: Vector space analysis and centroid-based clustering in the Encyclopédie", Digital Humanities 2008, University of Oulu, Oulu, Finland, June 25-29, 2008

Archives Parlementaires: lèse (more)

2009-10-06T14:48:00.007-05:00

As I mentioned in my last in this thread, I was a bit surprised to see just how prevalent the construction lèse nation had become early in the Revolution. The following is a sorted KWIC of lEse in the AP, with the object type restricted to "cahiers", resulting in 38 occurrences. These are, of course, the complaints sent to the King, reflecting relatively early developments of Revolutionary discourse. Keeping in mind all of the caveats regarding this data, we can see some interesting and possibly contradictory uses:

CAHIER: (p.319)sent être, comme criminels de lèse-humanité au premier chef, et ils se joindront au
CAHIER GÉN...: (p.77)manière de juger, qui   lèse les droits les plus sacrés des citoyens, doit av
CAHIER: (p.697)r individus, cette concession lèse les et avoir eu d'autre mo dre une r {La partie d
CAHIER: (p.108)e, excepté dans les crimes de lèse-majesté au premier chef. Art. 33. Qu'aucun jugem
CAHIER: (p.791) si ce n'est pour le crime de lèse-majesté au premier chef, et réduite aux seuls c
CAHIER: (p.448)té seulement pour le crime de lèse-majesté au premier chef ou pour celui de haute t
CAHIER: (p.409)s choses saintes, et crime de lèse-majesté, dans tous les cas spécifiés par l'ord
CAHIER: (p.260)istériels, sauf pour crime de lêse-majesté, de haute trahison et autres cas, qui se
CAHIER: (p.42)e, à l'exception des crimes de lèse-majesté, de péculat et de concussion; mais, dan
CAHIER: (p.780), si ce n'était pour crime de lèse-majesté divine et humaine. Art. 9. Qu'ii soit as
CAHIER: (p.476)ée, si ce n'est pour crime de lèse-majesté divine et humaine. Art. 8. Qu'il soit as
CAHIER: (p.584)our le meurtre et le crime de lèse-majesté divine ou humaine, et que hors de ce cas
CAHIER: (p.378)ont seuls juges des crimes de lèse-majesté et de lèse-nation. Art. 8. Le compte de
CAHIER: (p.42)re précise ce qui est crime de lèse-majesté. Et que l'on établisse quels sont les c
CAHIER.: (p.117)déclaré coupable du crime de lèse-majesté etnation. et comme tel, puni des peines
CAHIER GÉN...: (p.671) excepté le crime de   lèse-majesté, le poison, l'incendie et assassinat sur
CAHIER: (p.660) les cas, excepté le crime de lèse majesté, le poison, l'incendie et assassinat sur
CAHIER: (p.532)hommes coupables elu crime de lèse-majesté nationale; l'exemple elu passé nous a m
CAHIER: (p.645)poursuivis comme criminels de lèse-majesté nationale; que visite soit faite dans le
CAHIER: (p.383)s par elle comme criminels de lèse-majesté, quand ils tromperont la confiance du so
CAHIER: (p.286)s crimes de lèse-nation ou de lèse-majesté seulement; et que, dans ce cas, l'accus
CAHIER GÉN...: (p.210)ni comme criminel de   lèse-majesté; 4° Cette loi protectrice de la libert
CAHIER: (p.35)rrémissibles comme le crime de lese-majesté. 13° 'Qu'en matière civile comme en mat
CAHIER: (p.378) crimes de lèse-majesté et de lèse-nation. Art. 8. Le compte des finances imprimé a
CAHIER: (p.359) crimes de lèsemajesté, et de lèse-nation, ce qui comprend les crimes d'Etat. 7° En
CAHIER: (p.301)ort infâme, comme coupable de lèse-nation, celui qui sera convaincu d'avoir violé c
CAHIER.: (p.536) et punis comme coupables de lèse nation. 17" De demander 1 aliénation irrévocabl
CAHIER: (p.82)x, sera déclarée criminelle de lèse-nation et poursuivie comme telle, soit par les Et
CAHIER: (p.402)tte règle seront coupables de lèse-nation et poursuivis comme tels dès qu'ils auron
CAHIER: (p.285) patrie, coupable du crime de lèse-nation, et puniecomme telle par le tribunal qu'é
CAHIER: (p.544) coupables de rébellion et de lèse-nation, favoriser la violation de la constitution
CAHIER: (p.42)lisse quels sont les crimes de lèse-nation. Le vœu des bailliages est que les ressor
CAHIER: (p.285)n user que pour {es crimes de lèse-nation ou de lèse-majesté seulement; et que, da
CAHIER: (p.402)s généraux, comme coupable de lèse-nation; que les impositions seront réparties dan
CAHIER: (p.320)e défendre, c'est un crime de lèse-nation. Qui pourrait nier que dans la génératio
CAHIER: (p.388)-mêmes; déclarant criminel de lèse-nation tous ceux qui pourraient entreprendre dire
CAHIER.: (p.249)sions. Ce serait vu crime de lèse-patrie de ne pas correspondre à sa confiance pat
CAHIER GÉN...: (p.221)i serait un crime de   lèse-patrie. 2° De demander l'abolition de la gabelle

These include "lèse-majesté nationale", "lèse-majesté et nation" (OCR error fixed), "crimes de lèse-majesté et de lèse-nation", and (my favorite) "crime de lèse-majesté divine et humaine". Kelly suggests that notions of royal authority had been trimmed over the 18th century and with this reduction came a restriction of just what would constitute lèse-majesté and to what kinds of crimes it would apply. He argues that it was only in 1787, with the Assembly of Notables, that the idea of the nation "begins to take shape in a public glare" and further suggested that the decrees of September 1789 to decree the punishments for lèse-nation (and subsequent events) show the "confused and arbitrary genesis of lèse-nation".

See also the 11 entries in our Dictionnaires d'autrefois for lese which stress lèse-majesté through the entire period with lèse-nation being left as an after-thought, such as in the DAF (8th edition): "Il se joint quelquefois, par analogie, à d'autres noms féminins. Crime de lèse-humanité, de lèse-nation, de lèse-patrie." One should not construe this as excessively conservative, however, since lèse-majesté is, by far, the most common construction in the 19th and 20th centuries (at least as represented in ARTFL-Frantext).

Topic Based Text Segmentation Goodies

2009-10-04T09:41:00.010-05:00

As you may recall, Clovis ran some experiments this summer (2009) applying a perl implementation of Marti Heart's TextTiling algorithm to perform topic based text segmentation on different French documents (see his blog post and related files). Clovis reasonably suggests that some types of literary documents, such as epistolary novels, may be more suitable candidates than other types, because they do not have the same degree of structural cohesion. Now, as I mentioned in my first discussion of the Archives Parlementaires, I suspect that this collection may be particularly well to topic based segmentation. At the end of his post, Clovis also suggests that we might be able to test how well a particular segmentation approach is working by using a clustering algorithm, such as LDA Topic Modeling, to see if the segments can be shown to be reasonably cohesive. Both topic segmentation and modeling are difficult to assess because human readers/evaluators can have rather different opinions, leading to problems in "inter-rater reliability", which is probably a more vexing problem in the humanities and related areas of textual studies than in other domains.

Earlier this year (and a bit last year), I also ran some experiments on some 18th century English materials, such as Hume's History of England and the Federalist Papers. Encouraged by these results, particularly on the Federalist Papers, I have accumulated a number of newer algorithms, packages, and papers which may be useful for future work in this area. These are on my machine (for ARTFL folks, let me know if you want to know where), but I will not redistribute here as a couple of packages require non-redistribution or other limitations. I am putting links to some of the source files, when I have them.

Since Heart's original work, there have been a number of different approaches to topic based text segmentation. Clovis and I have tried to make note of much of this work on our CiteULike references (segmentation). There is some overlap with Shlomo's list. In no particular order of preference or chronology, here is what I have so far. I will also try to provide some details on using these when I have a chance to run them up.

From the Columbia NLP group (http://www1.cs.columbia.edu/nlp/tools.cgi), we have both Min-Yan Kan's Segmenter and Michael Galley's LCSeg. These required signing a use agreement, which I have in my office. The release archives for both have papers, some test data,

I spent some time trying to track down Freddy Choi's C99 algorithm and implementation described in some papers in the early part of this decade. I finally tracked it all down on the WayBack Machine at Internet Archive (link, thank you!!), which also has some papers, software, data and implementations of TextTiling and other approaches from that period. It appears several of the packages below use C99 and some of the code from this.

I was going to reference Utiyama and Isihara's implementation (TextSeg), but in the few months since I assembled this list, the link has (also) gone dead:
http://www2.nict.go.jp/x/x161/members/mutiyama/software.html#textseg
This appears to be a combination of approaches.

Igor Malioutov's MinCut code (2006) is available from his page:
http://people.csail.mit.edu/igorm/acl06code.html

There appears to be some info on TextTiling in Simon Cozens (2006), "Advanced Perl Programming".

We also want to check out Beeferman et. al. (link) since I recall that this group had done some interesting work. I have Beeferman's implementation of TextTiling in C, but don't think I have run across anything else.

If you run across anything useful, please blog it here or let me know. Papers should be noted on our CiteUlike. Thanks!!

Archives Parlementaires: lèse collocations

2009-10-03T11:21:00.010-05:00

The collocation table function of PhiloLogic is a quick way to look at changes in word use. Lèse majesté, treason or injuries against the dignity of the sovereign or state, is a common expression. The collocation table below shows terms around "lese | leze | lèse | lèze | lése | léze" in ARTFL Frantext (550 documents, 1700-1787) with majesté being by far the most common.

It is interesting to note that the construction "lèse nation" does not appear once in this report. Searching for "lèse nation" before the Revolution in ARTFL-Frantext finds a single occurrence, in Mirabeau's [1780] Lettres écrits du donjon de Vincennes, where he complains that "toute invocation de lettre-de-cachet me paraît un crime de lèse-nation". The collocation table for lEse in the current sample of the Archives Parlementaires (there are no instances of the lEze in this dataset), shows the lèse nation construction to be far more frequent.

There have been discussions* of the transition from lèse majesté to lèse nation, which is clearly shown here. Now, a reasonable objection to this is that this report includes the entire (as much as we have at the moment) revolutionary period. But we see roughly the same rates and ranking for lèse in 1789.

It would appear -- I would not put too much credit in these numbers -- that the shift from majesty to nation, and all that this implies in terms of the way state is envisaged, was well under way by 1789. This either happened very quickly in the years leading up to the Revolution, since the construction just once in ARTFL-Frantext before, or was a development that took place in types of documents not found in the rather more literary/canonical sample in ARTFL-Frantext, such as journals, pamphlets, and other more ephemeral materials. I guess data entry projects will never end.

One other observation. I like the collocation cloud as a graphic. But if you examine the table, you may notice that the cloud does not really represent the frequency differences all that well. The second table -- all of the AP -- shows that nation occurs more than 6 times as frequently as majesté, but differences of that magnitude tend to be rather difficult to show in a cloud. So, the compromise of providing both is probably the best approach.

* G. A. Kelly, "From Lèse Majesté to Lèse nation: Treason in 18th century France", Journal of the History of Ideas, 42 (1981): 269-286 (JStor).

Archives Parlementaires (I)

2009-10-02T11:24:00.006-05:00

A couple of weeks ago, some ARTFL folks discussed the notion of outlining some research and/or development projects that we will be, or would like to be, working on the coming months. We discussed a wide range of possibilities that could involve substantive work, using some of the systems we have already developed or are working on, or more purely technical work. Everyone came up with some pretty interesting projects and proposals, and we decided that it might be entertaining and useful for each of us to outline a specific project or two and write periodic entries here as things move forward. In the cold light of sobriety, this sounds like a pretty good idea. So, let me be the first to give this a whirl.

Our colleagues at the Stanford University Library have been digitizing the Archives Parlementaires using the DocWorks system. During a recent visit, Dan Edelstein was kind enough to deliver 43 volumes of OCRed text, which represents about half of the entire collection. Dan and I very hastily assembled an alpha text build of this sample under PhiloLogic. I converted the source data into a light TEI notation and attempted to identify probable sections in the data, such as "cahiers" , "séances", and other plausible divisions using an incredible simple approach. Dan built a table to identify volumes and years, which we used to load the dataset in (hopefully) coherent order. This is a very alpha test build. It is uncorrected OCR (much of which is surprising good) without links to pages images. The volumes are being scanned in no particular order, so we have volumes from a large swath of the collection. We are hoping to get the rest of volumes from Stanford in the relatively near future and will be working up or more coherent and user friendly site, with page images and the like. So, with these caveats, here is the PhiloLogic search form.

The Archives Parlementaires are the official, printed record of French legislative assemblies from beginning of the Revolution (1787) thru 1860. We are interested in the first part of the first series (82 volumes), out of copyright, ending in January 1794 which contain records pertaining to the Constituent Assembly, Legislative Assembly, and the Convention. The first seven volumes of the AP are the General Cahiers de doléances, which are organized by locality and estate (clergy, nobility, and third). The rest contain debates, speeches, draft legislation, reports, and many other kinds of materials typically organized by legislative session, often twice daily (morning and evening).

There will be some general house keeping required to start. Some of this will involve writing a better division recognizer, particularly for the Cahiers which are currently not including the place name and estate. I will also need to decide how to handle annexes, editorial materials, notes, etc. I suspect that it may also be worth some effort to try to correct some of the errors automatically, by simple replacement rules and identification impossible sequences. I am also thinking of using proximity measures to try to correct some proper names, such as Bobespierre, Kobespierre, etc. I would also want to concentrate some effort on terms that may reflect structural divisions. Dan has suggested identification of speakers, where possible, so one could search the speeches (full and in debates) of specific individuals like Robespierre, but this appears to be fairly problematic, since it is not clear how to identify just where these might stop.

Loading this data, particularly the complete (or at least out of copyright) dataset will probably be of general utility to Revolutionary historians, particularly when linked to page images and given some other enhancements. This will be done in conjunction with our colleagues at Stanford and other researchers.

I have several rather distinct research efforts in mind. There are a series of technical enhancements which I think fit the nature of the data fairly well:

sequence alignment to identified borrowed passages from earlier works, such as Rousseau and Montesquieu,
topic based text segmentation, to split individual sessions into parts, and,
topic modeling or clustering to attempt to identify the topics of parts identified by topic based segmentation.

We have already run experiments using PhiloLine, the many to many sequence aligner which we are using for various other applications. As we have found, this works for uncorrected OCR relatively well. For example, Condorcet in the Séance du vendredi 3 septembre 1790 [note the OCR error below] borrows a passage from Voltaire's Épitres in his

Nouvelles réflexions sur le projet de payer la dette exigible en papier forcé, par M. GoNDORCET.
Un maudit Écossais, chassé de son pays, Vint changer tout en France et gâter nos esprits. L'espoir trompeur et vain, l'avarice au teint blême, Sous l'abbé Terrasson calculaient son système, Répandaient à grands flols les papiers imposteurs, Vidaient nos coffres-forts et corrompaient no s mœurs.

Un maudit écossais, chassé de son pays,
vint changer tout en France, et gâta nos esprits.
L'espoir trompeur et vain, l'avarice au teint blême,
sous l'abbé Terrasson calculant son système,
répandaient à grands flots leurs papiers imposteurs,
vidaient nos coffres-forts, et corrompaient nos
moeurs;

without specific reference to Voltaire (that I could find). This is generally pretty decent OCR. The alignments work for poorer quality and where there are significant insertions or deletions. For example:

Rousseau, Jean-Jacques, [1758], Lettre à Mr. d'Alembert sur les spectacles:

autrui des accusations qu'elles croient fausses; tandis qu'en d'autres pays les femmes, également coupables par leur silence et par leurs discours, cachent, de peur de représailles, le mal qu'elles savent, et publient par vengeance celui qu'elles ont inventé. Combien de scandales publics ne retient pas la crainte de ces sévères observatrices? Elles font presque dans notre ville la fonction de censeurs. C'est ainsi que dans les beaux tems de Rome , les citoyens, surveillans les uns des autres, s'accusoient publiquement par zele pour la justice; mais quand Rome fut corrompue et qu'il ne resta plus rien à faire pour les bonnes moeurs que de cacher les mauvaises, la haine des vices qui les démasque en devint un. Aux citoyens zélés succéderent des délateurs infames; et au lieu qu'autrefois les bons accusoient les méchans, ils en furent accusés à leur tour . Grâce au ciel, nous sommes loin d'un terme si funeste. Nous ne sommes point réduits à nous cacher à nos propres yeux, de peur de nous faire horreur. Pour moi, je n'en aurai pas meilleure opinion des femmes, quand elles seront plus circonspectes: on se ménagera davantage, quand on

Séance publique du 30 avril 1793, l'an II de la:

son tribunal n'exerce pas, d'ailleurs, une autorité aussi 1 mu soire qu'on pourrait le croire ; il se fait J"_ tice d'une partie de la violation des lois «j ciales ; ses vengeances sont terribles p l'homme libre, puisque la censure o lst "°" la honte et le mépris : et combien cle st* § dales publics ne retient pas la crainte m. châtiments ? Dans les beaux temps cle n°*ji les citoyens, surveillants nés les uns a es» s'accusaient publiquement par zèle p % justice. Mais quand Rome fut corrompu^ citoyens zélés succédèrent des oeiai •„ t fâmes; au lieu qu'autrefois les bons accu- -^ les méchants, ils en furent accuses tour . -, rla méEn Egypte, la censure ssu_ v moire des morts ; la comédie eut o*" B^^ des un pouvoir plus étendu sur la rep vivants. „ •* i„ t-Ole niani^ 1 * L'esprit de l'homme est fait ae te ut rtr-c, encore plus du ridicule que d'un ,»ïl u

The Rousseau passage is found in a speech titled Nécessité d'établir une censure publique par J.-P. Picqué, which does not appear to mention the title and possibly not Rousseau at all (as far as I can tell). As you can see, this is fair messy OCR and is significantly truncated. We have a preliminary database running and will probably release this once we have the entire set and experiment further with alignment parameters.

Based on preliminary work that I have done on Topic based text segmentation, which Clovis followed up on in more detail (link), suggests that the individual séances may be a particularly good candidate for topic segmentation, since the topics can shift around radically. Running text tends not to do as well as clear shifts in topics. There are a number of newer approaches than the Hurst TextTiling implementation (which I will blog when I run them up) that may be more effective.

Finally, on the technical side, I want to experiment with LDA topic modeling. Again, Clovis' initial work on topic identification for the articles of Echo de la fabrique, indicate that, if one can get good topic segments, the modeling algorithm may be fairly effective. Oddly enough, I cannot recall anyone doing the "topic two-step", where one would apply topic modeling to parts of documents split up by a topic based segmentation algorithm. Or, I may have missed some important papers. The idea behind all of this is an attempt to build the ability to search for relatively coherent topics, either for browsing or searching.

So far, I have been talking about some more technical experimentation to see if certain algorithms, or general approaches, might be effective on a large and fairly complex document space. While I used the AP for significant work when I was doing Revolutionary studies, my initial systematic interest was in the General Cahiers de doléances. For my dissertation, and some later articles ("The Language of Enlightened Politics: The Société de 1789 in the French Revolution" in Computers and the Humanities 23 (1989): 357-64), I keyboarded a small sample of the Cahiers (don't ever, ever do that as a poor graduate student :-) to serve as a baseline corpus to look at changes in Revolutionary discourse over time, with specific reference to the materials published by the Société de 1789. I suspect that a statistical analysis of the language in the cahiers may bring to light interesting differences between the Estates, urban/rural, and north/south. For this set of tasks, I am planning to use the comparative functions of PhiloMine to examine the degree to which these divisions can be identified using machine learning approaches and, if so, what kinds of lexical differences can be identified. It would be equally interesting to compare a more linguistic analysis to the content analysis results found in Gilbert Shaprio et al, Revolutionary demands: a content analysis of the Cahiers de doléances of 1789.

I will, as promised (or threatened) above, try to blog good results and failures -- remember Edison is credited with saying while trying to invent the lightblub, “I have not failed. I've just found 10,000 ways that won't work.” -- of these efforts here so we can all consider them.

Epub to tei lite converter

2009-09-25T13:12:00.005-05:00

This is just to let you know that we now have an epub to tei converter. It can be found here:
http://artfl.googlecode.com/files/epub_parser.tar
As you'll notice, there are three files in this archive. The first one is epub_parser.sh. It's the only one you need to edit. Specify the paths (where the epub files are and where you want your tei files to be in) without slashes and just execute epub_parser.sh. The second one is parser.pl which is called by epub_parser.sh. The third one is entities.pl which handles html entities and is also called by epub_parser.sh. Before running it, make sure all three scripts are in the same directory.
A sample philologic load can be found here:
http://artflx.uchicago.edu/philologic/epubtest.whizbang.form.html
Of course, this is just a proof of concept and will only be used only for text search and machine learning purposes. Some things will have to be tuned up. Note that I put a div1 every ten pages since there is no way to recognize chapters in the original epub files.

Text segmentation code and usage

2009-09-25T13:03:00.004-05:00

Here's a quick explanation on how to use the text segmentation perl module called Lingua-FR-Segmenter. You can find here: http://artfl.googlecode.com/files/Lingua-FR-Segmenter-0.1.tar.gz It's not available on cpan as it's just a hacked version of Lingua::EN::Segmenter::TextTiling made to work with French. The first thing to do before installing it is to install Lingua::EN::Segmenter::TextTiling which will get you all the required dependencies (cpan -i Lingua::EN::Segmenter::TextTiling). When you install the French segmenter, make test will fail, so don't run it. That's normal since I haven't changed the example which is for the English version of the module. An example of how it can be used :

#!/usr/bin/perl use strict; use warnings; use Lingua::FR::Segmenter::TextTiling qw(segments); use lib '.'; my $text; my $count; while (<>) { $text .= $_; } my $num_segment_breaks = 100000; # safe number so that we don't run out of segment breaks my @segments = segments($num_segment_breaks,$text); foreach (@segments) { $count++; print; print "\n----------SEGMENT_BREAK----------\n" if exists $segments[$count]; }

There are other possibilities, but this is the basic one which will segment the text whenever there's a topic shift. Some massaging is necessary in order to get good results, and the changes needed are different from one text to the next. Basically separate paragraphs with a newline.

Classifying the Echo de la Fabrique

2009-09-18T15:06:00.016-05:00

I've been working lately on trying to classify the Echo de la Fabrique, a 19th century newspaper, using LDA. The official website is located at http://echo-fabrique.ens-lsh.fr/. The installation I used is strictly meant for experimentation on topic modeling.
The dataset I used is significantly smaller than the Encyclopédie, which means that the algorithm has fewer articles with which to generate topics. This makes the whole process trickier since choosing the right number of topics suddenly becomes more important. I suspect that adding more articles to this dataset will yield better results. I settled for 55 topics, and found a name corresponding to the general idea conveyed by each distribution of words. I then proceeded to add those topics to each tei file and loaded it into philologic. I chose to include 4 topics per article, or fewer if topics didn't reach the mark of 0.1.
The work I've done so far on LDA has already shown several things about its accuracy in generating meaningful topics and in properly classifying text. It tends to work really well with topics that are concept driven. For instance, in the Echo de la Fabrique , the topic 'justice' works really well. Same thing goes with 'Hygiène' associated with words like 'choléra' or 'eau'. On the other hand, there are some distribution of words which were not identifiable as topics. Those topics have been marked as 'Undetermined' with a number such as 'Undetermined1' to distinguish each undetermined topic. And then, there are also topics like 'Petites annonces' or 'Misère ouvrière ' which are not as concept driven, and therefore are subject to more inaccuracies. Once again, I believe that having more articles from the same source would partially improve this problem : more documents, more training for the topic modeler, reduced dependency on concepts.
Each topic has a number attached to it. This number represents the importance of the topic for each article. To get the most prominent topic, search for e.g. 'justice 1', 'justice 2' for the second topic, 'justice 3' for the third topic, and 'justice 4' for the fourth topic. If you want a search for all four, just type 'justice'. Note that the classification tends to be more accurate with the first topic than with the other three, but that 's not always the case.
Anyway, without further ado, here is the search form:
http://artfl-project.uchicago.edu/node/95
Please let me know if you have any comments, suggestions. Any feedback is much appreciated.

Some Classification Experiments

2009-08-28T12:15:00.011-05:00

Since Clovis has running some experiments to see how well Topic Modeling using LDA might be used to predict topics on unseen instances, I thought I would back track a bit and write a bit about some experiments I ran last year which may be salient for future for comparative experimentation or even to begin thinking about putting some of our classification work into some level of production. I am presuming that you are basically familiar with some of the classifiers and problems with the Encyclopédie ontology. These are described in varying levels of detail in some of our recent papers/talks and on the PhiloMine site.

The first set was a series of experiments classifying a number of 18th century documents using a stand alone Bayesian classifier, learning the ontology of the Encyclopédie, and predicting the classes on chapters (divs) of selected documents. I have selected three for discussion here, since they are interesting and are segmented nicely into reasonable size chunks. I ran these using the English classifications and did not exclude the particularly problematic classes, such as Modern Geography (which tend to be biographies about important folks, filed under where they were from) or Literature. Each document shows the Chapter or Article, which is linked to the text of the chapter, followed by one or more classifications, assigned using the Multinomial Bayesian classifier. If I rerun these, I will simply pop the classification data right in each segment, for easier consultation. Right now, you will need to juggle between two windows:

Montesquieu, Esprit des Loix
Selected articles from Voltaire, Dictionnaire philosophique
Diderot, Elements de physiologie

PENDING: Discussion of some interesting examples and notable failures.

The second set of experiments compared K-Nearest Neighbor (KNN) classifier to the Multinomial Bayesian classifiers in two tests, the first being cross classification of the Encyclopédie and the second being multiple classifications, again using the Encyclopedie ontology, to predict classes of knowledge in Montesquieu's Esprit des Loix. The reason for these experiments is to examine the performance of linear (Bayesian) and non-linear (KNN) classifications in the rather noisy information space that is the Encyclopédie ontology. By "noisy" I mean to suggest that it is not at all uniform in terms of size of categories (which can range from several instances to several thousand), size of articles processed, degree of "abstractness," where some categories are very general and some are very specific, and a range other considerations. We have debated, on and off, whether KNN or Bayesian (or other linear classifiers such as Support Vector Machines) classifiers are better suited to the kinds of noisy information spaces that one encounters in retro-fitting historical resources such as the Encyclopedie. The distinction is not rigid. In fact, in a paper last year, on which Russ was the lead author, we argued that one could reasonably combine KNN and Bayesian classifiers by using a "meta-classifier" to determine which should be used to perform a classification task on a particular article in cases of a dispute (Cooney, et. al. "Hidden Roads and Twisted Paths: Intertextual Discovery using Clusters, Classifications, and Similarities", Digital Humanities 2008, University of Oulu, Oulu, Finland, June 25-29, 2008 [link]). We concluded that, for example, "KNN is most accurate when it classifies smaller articles into classes of knowledge with smaller membership".

Cross classification of the classified articles in Encyclopedie using MNB and KNN. I did a number of runs, varying the size of the training set and set to be classified. The result files for each of these runs, on an article by article basis, as quite large (and I'm happy to send them along). So, I compiled the results into a summary table. I took 16,462 classified articles, excluding Modern Geography, and "trained" the classifiers on between 10% and 50% of the instances. I put "trained" in scare quotes because a KNN classifier is an unsupervised learner, so what you are really doing is selecting a subset of comparison vectors with their classes. The selection process resulted in 276 and 708 classes of knowledge in the information space. As is shown in the table, KNN significantly outperforms MNB in this task. We know from pervious work, and general background, that the MNB tends to flatten out distinctions among smaller classes, but has the advantage of being fast.

The distinctions are at times fairly particular and many times the classifiers come up with quite reasonable predictions, even when they are wrong. A few examples (red shows a mis-classification):

Abaissé, Coat of arms (en terme de Blason)

KNN Best category = CoatOfArms
KNN All categories = CoatOfArms, ModernHistory
MNB Best category = ModernHistory
MNB All categories = ModernHistory, Geography

AGRÉMENS, Rufflemaker (Passement.)

KNN Best category = Ribbonmaker
KNN All categories = Ribbonmaker
MNB Best category = Geography
MNB All categories = Geography

TYPHON, Jaucourt: General physics (Physiq. générale)

KNN Best category = Geography
KNN All categories = Geography, GeneralPhysics, Navy, AncientGeography
MNB Best category = Geography
MNB All categories = Geography, AncientGeography

I applied the comparative classifiers in a number of runs using different parameters for Montesquieu, Esprit des Loix. All of the runs tended to give fairly similar results, so here is the last of the result sets. The results are all rather reasonable, with in limits, given the significant variations in size of chapters/sections in the EdL. The entire "section" 1:5:13 is

Idée du despotisme. Quand les sauvages de la Louisiane veulent avoir du fruit, ils coupent l'arbre au pied, et cueillent le fruit. Voilà le gouvernement despotique.

which gets classified as

KNN Best category = NaturalHistoryBotany
KNN All categories = NaturalHistoryBotany
MNB Best category = NaturalHistoryBotany
MNB All categories = NaturalHistoryBotany, Geography, Botany, ModernHistory

In certain other instances, KNN will pick classes like "Natural Law" or "Political Law" while the MNB will return the more general "Jurisprudence". I am particularly entertained by

PARTIE 2 LIVRE 12 CHAPITRE 5:
De certaines accusations qui ont particulièrement besoin de modération et de prudence
KNN Best category = Magic
KNN All categories =
MNB Best category = Jurisprudence
MNB All categories = Jurisprudence

Consulting the article, one finds a "Maxime importante: il faut être très circonspect dans la poursuite de la magie et de l'hérésie" and that the rest of the chapter is indeed a discussion of magic. While the differences are fun, and sometimes puzzling, one should also note the degree of agreement between the different classifiers, particularly if one discounts certain hard to determine differences between classes, such as Physiology and Medicine. The chapter "Combien les hommes sont différens dans les divers climats" (3:14:2) is classified by KNN as "Physiology" and MNB as "Medicine". Both clearly distinguish this chapter from others on Jurisprudence or Law.

I have tended to find KNN classifications to be rather more interesting than MNB. But I don't think the jury is out on that and one can always perform the kinds of tests that Russ described in the Hidden Roads talk.

All of these experiments were run using Ken Williams' incredible handy perl modules AI:Categorizer rather than PhiloMine (which also has a number of Williams' modules) just because it was easier to construct and tinker with the modules. I will post some of these shortly, for future reference.

Collocation Notes

2009-08-27T13:40:00.008-05:00

Since we are planning a proposal that will use collocation as a main component for yet another grant/project proposal, I thought I would give some background notes for future reference. One of the more popular reporting features in PhiloLogic is the collocation table. This is a very simple mechanism. It counts the words around a search term or list of terms (the user sets the span and can turn of function word filtering) and reports the frequencies of terms to the left, right and total in a table. Richard recently added the "collocation cloud" feature to the current production version at ARTFL. The following is the collocation table and cloud for "tradition" in the current release of ARTFL-Frantext:

Collocation is a well established approach in Digital Humanities and other domains. Susan Hockey, for example, has a nice discussion of collocation in Electronic Texts in the Humanities, (Oxford, 2000), pp 90-91. She describes some work from the early 1970s and brings out the distinction between statistical calculations of collocation and very simple counts.

Berry-Rogghe (1973) discusses the relevance of collocations in lexical studies with reference to an investigation of the collocates of house, from which she is able to derive some notion of the semantic field of house. [...] Her program counts the total number of occurrences of the node, and the total number of occurrences of each collocate of the node within a certain span. It then attempts to indicate the probability of these collocates occurring if the words were distributed randomly throughout the text, and can thus estimate the expected number of collocates. It then compares the expected number with the observed number and generates a 'z-score', which indicates the significance of the collocate. The first table she presents shows the collocates of house based on a span of three words and in descending order of frequency. First is the, which co-occurs thirty-five times with house, but the total number of occurrences of the is 2,368. The is followed by this, a, of, I, in, it, my, is,have, and to, before the first significant collocate sold where six of the seven occurrences are within three words of house. Four words further on is commons, where all four occurrences collocate with house, obviously from the phrase House of Commons. When reordered by z-score, the list begins sold, commons, decorate, this, empty, buying, painting, opposite.

She goes on to suggest that "[f]or the non-mathematical or those who are suspicious of statistics, even simple counts of collocates can begin to show useful results, especially for comparative purposes." Which is, of course, precisely what PhiloLogic does now.

I have made extensive use of collocations over the years for my own work, both the zscore calculation and the very simple collocation by counts (filtering function words). These studies include American and French political discourse for my dissertation and subsequent papers, gender marked discourse, and comparisons of notions of tradition over time and in English and French. Breaking collocations down over time gives a pretty handy way to look at changing meanings of words. I have an ancient paper "Quantitative Linguistics and histoire des mentalités: Gender Representation in the Trésor de la langue française, 1600-1950" in the Contributions to Quantitative Linguistics: Proceedings of QUALICO 1991, First Quantitative Linguistics Conference (Amsterdam: Kluwer 1993): 351-71. which gives a write up on the method, some math :-), and references to some salient papers, including Berry-Rogghe (1973). In more recent work, I have used pretty much the same working model. Build a database split into 1/2 century chunks and do collocations by half century periods, using the z-score calculation (outline the paper). Indeed, I have a hacked version of PhiloLogic that does this.

As Hockey indicates, the statistical measure gives a rather different flavor for the collocates, since it attempts to measure the degree of relatedness between the two words. For example, the top collocates of "Platon" in a subset of Frantext shift around significantly.


Word   Rank ->  by zscore    by freq
Speusippe:          1             78
Aristote :          5              2

The reason for this is clear. 4/8 occurrences of Speusippe occur near Platon while 51/793 occurrences of Aristote are near Platon. I think both techniques are valid, and have used them to illuminate various tendencies. The z-score measures the relatedness of two words while the simple counts shows how in general the keyword s typically used. There is, of course, some overlap between the two, but the z-score tends to privilege to more unique constructions and associations.

Now, the obvious question is: "why don't we have the z-score calculation as an option in the standard collocation function in PhiloLogic?" And the answer is speed. The z-score (and other statistical models which I will mention below), attempts to compare expected frequencies of the word distribution against the observed frequencies, where the expected frequency assumes random distribution of words across a text, taking into account differences in frequencies. [Caveat, we know that "Language is never, ever, ever, random", but it is a useful heuristic, particularly for the kinds of simplistic comparisons I am doing.] The bottle neck for a real-time version of z-score collocations has been calculating baseline frequencies for any arbitrary range of documents. This may no longer be a significant problem. In a recent experiment, I built a script to sum the counts from arbitrary documents selected by bibliographic data (ARTFL Frantext word frequency report). While we have had a few users express interest in having more global counts, it would appear that our latest servers have more than enough horsepower to do these kinds of additions very quickly, certain fast enough to be bolted on to a collocation generator as an option. Certainly something to think about for a future revision of the old hopper.

There are, of course, a huge number of ways to calculate collocations. I suspect that there are two major areas: 1) how to identify spans and 2) how to measure the relationships between words. I had this notion that rather than simply look at spans as N words to the right and left, one would count words in pre-identified constructions (such as noun phrases, verb phases, or even clauses). Given the power of modern NLP tools, this is certain an option to think about. Related is the notion that one would rather do collocations on either lemmas or even "stems" (the results of a stemmer which basically strips various characters) which are not words, but can be related to sets of words. The other area of work is the possibility of using other statistical measures of association, such as log-likelihood and mutual information.

I'm pretty sure I've seen standalone packages that support more sophisticated statistical models. If we were going to do anything serious, the first place to start is reading. Reading? What? Yes, indeed. The chapter on Collocation in Chris Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press. Cambridge, MA: May 1999 is a great place to start. Other titles may include Sabine Bartsch, Structural and functional properties of collocations in English: a corpus study of lexical and pragmatic constraints on lexical co-occurrence (Gunter Narr Verlag, 2004). There is also software. Of course, Martin's WordHoard has an array of collocation measures (documentation) and we should not forget other goodies, such as Collocate (commercial) and the Cobuild Collocation Sampler.

Finding related articles using topic modeling

2009-08-26T17:15:00.000-05:00

While still working on the topic inferencer, I started hacking at another possibility which is made possible by topic modeling, that is finding closely related texts within a corpus. There are several ways of doing this. What I chose to do was to consider the top three topics in each article and their respective proportion, and weigh it against the whole corpus. Here's a link to a search form where you can search for similar articles in the Encyclopedie :
http://robespierre.uchicago.edu/topic_modeling/search.form.html
In order to use it, you should paste the url of the article you're looking at. You'll then get a list of links to various articles that should be similar in content to the one you selected. A lot of tinkering can be done with the calculation of similarity, therefore I very well might have made some bad jugement here and there. This is therefore work in progress, therefore you might get strange results. But if you go through the whole list of results you might see some interesting things.
I would like to give you two examples I've tried that work really well. The first one is the article Economie by Rousseau ( which gives very good results), and if you look at link 24, which is according to my (flawed) calculation the 24th closest article, you'll see an example of an article that would have been hard to find and link to Rousseau. The second example is Question by Jaucourt. Among the top 20, a lot concern various methods of torture, spread out in different classes of knowledge. Let me know what you think.

Some Notes on Theme-Rheme in PhiloLogic

2009-08-26T13:46:00.011-05:00

One of the more arcane, and probably rarely used, functions in PhiloLogic is an experimental reporting scheme that I rather tentatively named "word in clause position analysis" or "theme-rheme," which is briefly described in the PhiloLogic user manual. I proposed this in talk titled "Making Space: Women's Writing in France, 1600-1950," which I gave at the ACH-ALLC and COCH/COSH conferences in 2004 (and drafted a good chunk of a paper about), and implemented in PhiloLogic around that time. Since we are now thinking of using this kind of analysis as a possible way to identify "interesting" or "illustrative" uses of words as part of another project, I thought it might be helpful to back-track a bit, give a bit more overview of how it works, outline some of the theoretical background as I understand it, and provide some useful links and papers.

As noted in the user manual entry, the "theme-rheme" function generates a standard concordance which it then attempts to sort out by where your search term occurs in a clause, where a clause is defined by punctuation. It segregates the occurrences by front of clause, back of clause, middle of clause, and instances where the clause is too short. By default, it displays only those occurrences that are clause initial. In the current implementation of ARTFL-Frantext a search for "tradition" results in 4,962 occurrences, which roughly break down as follows:

Front of Clause: 571 out of 4692 [12.16%] Avg. Clause length: 9.58
Last of Clause: 1056 out of 4692 [22.50%] Avg. Clause length: 8.68
Middle of Clause: 2348 out of 4692 [50.04%] Avg. Clause length: 9.56
Too Short: 717 out of 4692 [15.28%] Avg. Clause length: 2.40

The system further identifies specific documents in which your search term exceeds, by a certain percentage, the front of clause rate (in this case 12.16%), such as

55.55% (10/18): Montalembert, Charles Forbes, [1836], Histoire de Sainte Elisabeth de Hongrie, duchese de Thuringe...
28.20% (11/39): Bossuet, Jacques Bénigne, 1627-1704. [1681], Discours sur l'histoire universelle

and it, of course, displays these in different colors, such as:

L'Europe ainsi déracinée s'est plus tard déracinée davantage en se séparant, dans une large mesure, de la tradition chrétienne elle-même sans pouvoir renouer aucun lien spirituel avec l'Antiquité.

Oui, sans doute, si cette tradition était tout entière dans Aristote et dans l'enseignement péripatéticien de la scolastique.

La tradition attribue à Pythagore un séjour à Babylone.

The basic notion is that clause initial instances of words are probably more important, since they tend to be the "subject"of the rest of the clause. And authors who tend to use your favorite word in more clause initial positions than is average, might be doing something of particular note. In other words, can we use the machine to try to isolate, from the thousands of hits, those that might be particularly noteworthy. In this case, we have isolated a small subset (12%) of the occurrences of "tradition" in a clause initial position and some authors/documents who tend to privilege this word. I also identified clause ending uses, since (I suspect) end of clause words provide a bridge to the next clause (or sentence).

I set two "intertwingled" problems in the paper, women's writing and, more salient to this post, the increasing need to arrive at high orders of generalization to make sense of the results coming from ever increasing datasets. Obviously, one solution to this is work we have been doing over the last few years in the areas of machine learning, document summarization, and text data mining (see PhiloMine and related papers). What I proposed in this paper was a move toward from traditional text analysis techniques towards analytical notions based on functional linguistics or functional grammar, which are related in various ways to text linguistics or discourse analysis. This is a huge area of work and I would not begin to characterize it. Helma, of course, is a functional linguist and proposes that this is a branch of "linguistics that takes the communicative functions of language as primary as opposed to seeing form as primary." And as you might imagine, there are schools and competing views. I have to admit I like the name "West Coast Functionalists. :-)

My take on this is that meaning arises from choices, or chains of choices, with sets of goals and objectives. I also suspect that many "functionalists" would agree on a few other basic notions, such as lexis and grammar are inseparable in meaning creation, and indeed the term "‘lexico-grammar’ is now often used in recognition of the fact that lexis and grammar are not separate and discrete, but form a continuum." (cite) It also appears that many functionalists would agree with the notion that the clause is the building block unit. There are probably other points of general agreement about just how different layers might work or be defined. For example, Simon Dik (not related to Helma) identified three layers in his Functional Grammar:

SEMANTIC FUNCTIONS (Agent, Patient, Recipient, etc.) which define the roles that participants play in states of affairs, as designated by predications.
SYNTACTIC FUNCTIONS (Subject and Object) which define different perspectives through which states of affairs are presented in linguistic expressions.
PRAGMATIC FUNCTIONS (Theme and Tail, Topic and Focus) which define the informational status of constituents of linguistic expressions. They relate to the embedding of the expression in the ongoing discourse, that is, are determined by the status of the pragmatic information of Speaker and Addressee as it developes in verbal interaction.

Of course, other folks will carve these things up differently. Robert de Beaugrande, whose extensive web site and papers are well worth the visit, represents the various levels of functional linguistics from nerves to text, as outline in the image, taken from his "Functionalism and Corpus Linguistics in the ‘Next Generation." In another paper, he argues "Corpus data are so eminently suited to informing us about 'networks' because they offer concrete displays of the constraints upon how sets of choices can interact. In the 'lexicon' part of the 'lexicogrammar' of English, these constraints constitute the collocability in the virtual system, and the textual actualisations are the lexical collocations. In the 'grammar' part of the 'lexicogrammar', these constraints constitute the colligability in the virtual system, and the textual actualisations are the grammatical colligations" and goes on to represent the following image the series of "dialectics" running between text and language.

Ok, they are fun images ... now back to work... and I wanted to see how embedding images would work...

It is the level of pragmatics that I suspect interests us in this particular case. As I noted above, I borrowed the "theme-rheme" nominclature from MAK Halliday's Introduction to Functional Linguistics. Again:

Theme: "starting point of the message, what the clause is going to be about".
Rheme: everything not the Theme: new information/material

Theme contains given information i.e. information which has already been mentioned somewhere in the text, or is familar from the context. There is an accessible description of this, with some nice examples in Theme and Rheme in the Thematic Organization of Text.

In English (and French), identification of the Theme is based primarily on word order. Thus, the theme is the element which comes first in the clause. (Eggins, An Introduction to Systemtic Functional Linguistics, p. 275) Plenty of problems identifying the exact boundaries of different kinds of themes.

The take way point, from all of this, is that the theme/rheme distinction is important because it is the way you get thematic development across a longer span of text. Obviously, the Rheme in one clause can become Theme in the next.

One other take away: Halliday makes the argument that one can use punctuation in written texts to identify clauses, which is not the same for spoken texts.

More later????? I can track down a few more bibliographic entries....

Topic inference using the Encyclopédie trained model

2009-08-18T13:46:00.000-05:00

While trying to use the Encyclopédie trained topic model on the Mémoires de Trévoux, something quite unexpected happened, the topic modeler was finding it hard to find topics that matched the Trévoux articles. You can see those results here:
http://robespierre.uchicago.edu/topic_modeling/inference/encyclo2trevoux.txt
Since the topic inference feature in mallet is relatively new, I though of creating a model out of the Trévoux, and then compare the topic proportion generated from the topic trainer with the one generated using the model. So basically, I tested the model against the corpus of articles from which it originated. In all likelihood, the results were going to be excellent. Well, they weren't, therefore showing that the topic inferencer is not yet operational (it is a new feature after all). On the other hand, I did notice something, that if you compare the results, you'll notice that the same topics (mostly) are prominent in both, only the proportion measure is off, approximately divided by ten when using topic inference. Here are those results:
when using topic training:
http://robespierre.uchicago.edu/topic_modeling/inference/proportions.txt
when using topic inference:
http://robespierre.uchicago.edu/topic_modeling/inference/proportions_itself.txt
The question is, can I trust those results. My initial analysis tends to show that it does work, but it's definitely not as accurate as the first experiments I did with topic modeling. Some more digging is needed, eventually getting in touch with the Mallet developers.

Proportions of topics in Encyclopédie articles

2009-08-14T11:55:00.005-05:00

This is a follow-up to my previous blog entry about topic modeling in the Encyclopédie. As the title of this post suggests, I will be showing here the proportions of topics per article. Instead of just posting those results without any further comment, I would like to focus on 12 random articles to see what kind of results one could get. My feeling about this is that the best results are in the 300 topic model. What do you think? Note that there is still a lot of room for some refinement.

Examples from the 42 topic model :
http://docs.google.com/View?id=dgrbcw9z_69gk9w5tgc
Examples from the 100 topic model:
http://docs.google.com/View?id=dgrbcw9z_70c2n79kgv
Examples from the 150 topic model:
http://docs.google.com/View?id=dgrbcw9z_71cx73tsch
Examples from the 200 topic model:
http://docs.google.com/View?id=dgrbcw9z_724t5x9mfm
Examples from the 250 topic model:
http://docs.google.com/View?id=dgrbcw9z_73fvznkb7j
Examples from the 300 topic model:
http://docs.google.com/View?id=dgrbcw9z_74chqfgsct
Examples from the 350 topic model:
http://docs.google.com/View?id=dgrbcw9z_75chsw8gcp

If you wish to look yourself at the results, here they are, the first number is the topic with the proportion measure in parentheses. The article number is the div number of the article :

http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_42.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_100.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_150.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_200.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_250.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_300.txt
http://robespierre.uchicago.edu/topic_modeling/topics_in_articles_350.txt

the PhiloLogic Data Architecture

2009-08-11T09:51:00.014-05:00

For the last year or so, I've been arguing that it's time for a round of maintenance work on PhiloLogic's various retrieval sub-systems. In a later post, I'll examine some of the newer data store components out there in the open-source world. First, however, I'd like to enumerate what PhiloLogic's main storage components are, where they live, and how they work, for clarity and economy of reference.

The Main Word Index:

PhiloLogic's central data store is a GDBM hashtable called index that functions, basically, the same way as a Perl hash, but on disk, rather than in memory. It has a set of keys, in this case each unique word in the database. Each key corresponds to a short-ish byte-string value, which can come in two different formats:

For low-frequency words, each key word corresponds to a packed binary data object that contains three components:

A short header that says, "I'm a low-frequency word!"
Total frequency for this word. This is used by the query optimizer.
A compressed binary hitlist for the word, containing the byte offset and object address of every occurrence of the word.

For high frequency words, the structure is similar. A type header is followed by the total frequency, which is followed by an address into the raw block index, called index.1. If you've ever looked at a database directory, you may have noticed that this index.1 file is typically two or three times the size of the main index. That's because it contains the binary hitlists for all the high-frequency words in the database, divided into 2-kilobyte chunks. That's important, because, as Zipf's law will tell us, the most frequent words in a language can be very, very frequent, and thus the hits for a single word could go on for tens or or hundreds of megabytes. By dividing large hitlists into chunks, we can put a limit on memory usage. In a modern system, we could set a higher ceiling- 64k might be reasonable. But architecturally, the chunking algorithms are vital for frequent words or large databases.

The upside of this admittedly complex architecture is PhiloLogic's raison d'etre: its blindingly fast search performance. The downside is that GDBM doesn't support some of the features that we expect, particularly ones that involve more complicated searches than the simple keywords.

Thus, we added a plain-text token table, words.R, that we can grep through quite quickly to get a list of all valid keys that match a specified pattern, and a tab delimited token table, words.R.wom, that we can grep through for various secondary attributes and normalizations of the indexed tokens.

Both of these functions are very fast, due to the high throughput of GNU grep. The only downside is the opacity of the index construction process, which can make modifications to this structure very difficult. That said, it's capable of handling unexpectedly rich data if you understand where everything goes. I'll go into this in more depth in my Perseus whitepaper.

Document Metadata:

Traditional 3-series PhiloLogic keeps the most important information about it's XML document store in a file called docinfo, which contains the filename, size, date, and a few other book-keeping tidbits. The reporting systems use this file for the basic tasks of opening an XML file and reading a section out of it, whether for search results context, or for browsing with getobject.

All other data go in a file called bibliography, which has about 20 fields for author, title, publisher, language, etc., and which the gimme utilities search for bibliographic queries. Traditionally, this is done with GNU egrep, but more recent releases have preferred MySQL for its more sophisticated query language. The result of any query, regardless, is a list of binary document id's to pass through to the search engine as a corpus file.

Text Object Metadata:

PhiloLogic tracks all objects below the document level as either division or paragraph objects, and stores them in two different tables: divindex.raw and subdivindex.raw respectively, and uses the subdocgimme utilities to query the metadata. As before, query results, via SQL or egrep, are pushed off to search3 as a packed binary corpus file. And again, the reporting and retrieval subsystems have their own data structure, in this case the toms, for contextualizing hits, or for retrieval with getobject. Finally, the loader builds several derived data structures called navigation, pagemarks, references, and dividxchild.tab for various internal functions.

As the reader may have noticed, the document and text objects are not as clean or as optimized as the main word index, and even harder to hack coherently. I'll detail my first attempt at a more dynamic object structure for the Perseus corpus in a later post. For now, though, I'll pose a question:

Is it possible to devise a single data structure that can handle all of the functions that our current gang of tables and packed binaries does? In short, these are:

Query objects for arbitrary combinations of properties
Efficiently retrieve file paths and byte offsets for retrieval
Maintain the logical relationships of all these objects
Resolve internal and external references to objects at any depth

My current prototypes fulfill about half of these requirements, #2 & 3. But a new object architecture would ideally be a single data structure that does it all. Can anyone think of needed features that I've missed? What about the kind of metadata that ASP or IWW use? Can anyone think of a component that's totally unnecessary and redundant, or notoriously buggy? Please, let me know.

Preliminary results on topic modeling in the Encyclopédie

2009-08-07T14:29:00.019-05:00

Following up on Mark's comments on topic modeling using Latent Dirichlet Allocation, or LDA, I went on to explore some implementations of this algorithm to see what type of results we would get on some of the data sets we have. I first started using David Blei's code, but it ended being to complex to use, the documentation was very elusive. So I starting to look at another tool, Mallet, which also includes an implementation of LDA.
Here are the first results I've come up with when running it against the Encyclopédie. The main issue when using topic modeling is, as described in this article, coming up with the right number of topics as the results differ quite a bit depending on this number. I haven't quite settled yet for a particular number. Below are the topics I've come up with. Let me know what you think, which version(s) seems the more accurate. I would argue that the question comes down to how focused do we want each topic to be, or how broad do we want those topics to be without losing any accuracy. Please let me know if there are some words you think I could eliminate (less noise, more accuracy). Several hints would be useful, such as pinpointing a topic that doesn't make sense, a word that seems out of place somewhere (probably some noise to be eliminated during another run). Note that the list of words that I delete from the articles (so far a little over 300) could very well be used for other 18th century French texts, if not for different periods from 1650 to today with some tweaks here and there. Thanks.

Version with 42 topics:
http://robespierre.uchicago.edu/topic_modeling/42topics-encyclo.txt
Version with 100 topics:
http://robespierre.uchicago.edu/topic_modeling/100topics-encyclo.txt
Version with 150 topics:
http://robespierre.uchicago.edu/topic_modeling/150topics-encyclo.txt
Version with 200 topics:
http://robespierre.uchicago.edu/topic_modeling/200topics-encyclo.txt
Version with 250 topics:
http://robespierre.uchicago.edu/topic_modeling/250topics-encyclo.txt
Version with 300 topics:
http://robespierre.uchicago.edu/topic_modeling/300topics-encyclo.txt
Version with 350 topics:
http://robespierre.uchicago.edu/topic_modeling/350topics-encyclo.txt

These results are just the preliminary step. The interesting part is the topics proportions per document. I'll show some results in another post.

Looking at different implementations of fuzzy matching

2009-07-27T15:29:00.003-05:00

While thinking of maybe renovating philologic, one of the possibilities we would look into would be fuzzy matching. A couple of implementations exist. I looked at what each one had to offer. Please let me know if some things are unclear. Here are the results of this investigation.

An experiment on text segmentation

2009-07-27T15:13:00.005-05:00

What is text segmentation?
The whole point of text segmentation is to be able to divide texts into meaningful segments by using an algorithm that will analyze the text and automatically subdivide it by identifying topic shifts. This is really the first step towards a larger goal, that is being able to run a classifier on each identified segment and therefore be able to determine automatically what topic each segment is about. I therefore started investigating the possibilities of one implementation of text segmentation to see if the results were encouraging.
The results of this experimentation can be found here.

Fast Latent Dirichlet Allocation

2009-07-20T14:40:00.003-05:00

Porteous, Ian, David Newman, Alexander Ihler, Arthur Asuncion, Padhraic Smyth, and Max Welling. "Fast collapsed gibbs sampling for latent dirichlet allocation." KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2008, 569-577. (Link)

This describes Fast LDA and suggests that this may be helpful in "real time" topic modeling of a few thousand documents returned by a search engine. The introduction to section 3 gives a nice "intuitive" description of LDA, helpful for those, like me, who are significantly math challenged, as well as some algorithm descriptions. The paper has links to code and David Newman has posted links to some earlier code which may be of considerable interest. Newman has done some interesting work on topic modeling of 18th century American newpapers (link and link).

Dynamic Topic Models

2009-07-08T16:46:00.006-05:00

I just had a look at David Hall, Daniel Jurafsky, and Christopher Manning. "Studying the History of Ideas Using Topic Models." Proceedings from the EMNLP 2008: Conference on Empirical Methods in Natural Language Processing. October 2008. [link] This is a very interesting article, using Latent Dirichlet Allocation [link wikipedia] and some extensions, examining changing publication trends in computational linguistics. As noted on the Wikipedia entry, this approach [LDA] is described in David Blei, Andrew Y. Ng, and Michael I. Jordan. "Latent Dirichlet Allocation." Journal of Machine Learning Research 3 (January 2003) [link]. David Blei has released code [link] and has a number of samples, a listserv, etc. on his site. He also gave a great presentation of his work as a Google talk "Modeling Science: Dynamic Topic Models of Scholarly Research" in May 2007 [link video and paper]. This appears to be a powerful technique, which has the ability to handle changing vocabularies over a century of scientific writing.

In trying to run it on OS-X, I am able to currently get topics for the sample AP collection provided by Blei, but not able to get inferences as it throws malloc errors. I'm looking at the mailing list to see if there are any hints about OS-X.

Blei lists several implementations on his site, including one part of Mallet, which I think we installed here at one point. See also http://gibbslda.sourceforge.net/
for another implementation and some samples run on large Wikipedia and Medline (abstract) collections.

Also noticed a Ruby module described at
http://mendicantbug.com/2008/11/17/lda-in-ruby/

Scribal Publication and Undiscovered Public Knowledge

2009-07-07T15:54:00.004-05:00

In thinking about another project, I ran across Harold Love's Scribal Publication in Seventeenth-Century England (Oxford: Clarendon Press, 1993. Pp. xi+379). [Google Books]

This has an interesting discussion regarding scribal publication as being a "perfect example" of Don Swanson's notion of "Undiscovered Public Knowledge". "By this he [Swanson] means knowledge that exists 'like scattered pieces of a puzzle' in scholarly books and articles, but remains unknown because its 'logically related parts ... have never become known to one person." The reference is to Don R. Swanson, 'Undiscovered public knowledge', Library Quarterly 56 (1986). Professor Swanson's work is aimed primarily at bio-medical research using a system that he and his colleagues call Arrowsmith, which is available on http://kiwi.uchicago.edu/ (currently in Charlie's office) which has links to recent papers and more references.

It may be interesting to think about how this might be applied to research in the humanities. Other work in the same area suggests that latent semantic indexing, a variation on the general vector space model, may be of use.

A few more papers to think about:

Xiaohua Hu, et al. "Mining undiscovered public knowledge from complementary and non-interactive biomedical literature through semantic pruning", Proceedings of the 14th ACM international conference on Information and knowledge management (2005) [
Link] and Supercomputing Approach to Undiscovered Public Knowledge
[Link] from, UIUC (of course).

I will post more related articles on the ARTFL CiteULike and, if I remember, use the tag UDPK to cluster the papers.

Textual Re-use of Ancient Greek Texts

2009-06-25T11:20:00.004-05:00

Textual Re-use of Ancient Greek Texts: A case study on Plato’s works

Marco Büchler & Annette Loos (eAqua Project, Leipzig)

Digital Classicist/ICS Work in Progress Seminar, Summer 2009 Link

See abstract of workshop presentation. Appears to use ngrams with with a mechanism to "relax word order" and a kind of semantic association. Russ and I have talked a bit about both as future extensions to PhiloLine/PAIR to improve recall, but at the risk of introducing less precision.

PhiloLogic: Ubuntu 64 bit compilation failure

2009-06-25T10:02:00.001-05:00

Damir Cavar reports:

After evaluations with various Linux distributions we came to the conclusion: Philologic index generation (the C-code) breaks on 64-bit (various versions) with a segmentation fault. We didn't manage to let it run in a 32-bit changeroot environment on Ubuntu and Debian.

It works perfectly well on the newest release of the 32-bit Ubuntu server, and also on 32-bit Debian Lenny. On a 32-bit system the default is most likely that one has a memory limitation, i.e. max. 3.5 GB RAM, even though there might be more RAM available physically. If you install the Ubuntu "server kernel" on a 32-bit system, you get large memory support (i.e. more than 3.5 or 4 GB RAM), i.e. you need a PAE enabled kernel. On Debian it is the bigmem kernel you need to install. A 32-bit system is somewhat slower, there are various other disadvantages (if one uses other code or software that makes use of advanced 64-bit CPU features), but, well, we seem to have no other choice now for a solution with Philologic right now.

We have a version running, now on Debian Lenny with the bigmem kernel, and we're putting the bits and pieces together, i.e. our Croatian localization, some scripts for statistics etc. Once this is up, I'll place some more docu, scripts, localizations and adaptations at the Croatian Language Corpus site: http://riznica.ihjj.hr/ (this is still the old system, we are just migrating the infrastructure to new servers, using Lenny)

More can soon be found on the pages of the Linguistics dept. at the University of Zadar: http://ling.unizd.hr/

Should somebody have a fix for a 64-bit Linux environment, hints would be very much appreciated.

ASV Toolbox project

2009-06-25T09:37:00.003-05:00

http://wortschatz.uni-leipzig.de/~cbiemann/software/toolbox/

ASV Toolbox is a modular collection of tools for the exploration of written language data. They work either on word lists or text and solve several linguistic classification and clustering tasks. The topics covered contain language detection, POS-tagging, base form reduction, named entity recognition, and terminology extraction. On a more abstract level, the algorithms deal with various kinds of word similarity, using pattern based and statistical approaches. The collection can be used to work on large real world data sets as well as for studying the underlying algorithms. The ASV Toolbox can work on plain text files and connect to a MySQL database. While it is especially designed to work with corpora of the Leipzig Corpora Collection, it can easily be adapted to other sources.

Many of these appear to be described in recent papers by Beimann and his collaborators.

Thanks to Alain Guerreau for the pointer.