Paul Dix Explains Nothing

Initial notes on Corpus Crawler

I've had a busy week so progress has been slow on CorpusCrawler.  However, I did  get a few things done so here's my writeup on what I've accomplished so far.  It's been quite the adjustment trying to write in Python.  I haven't yet learned how to think in Python so things are a little slow right now.  I did take advantage of the interactive shell.  It was nice to be able to work with and manipulate the data on the fly.  I created a few modules to store my code, but found this caused a little problem with the whole "on-the-fly" concept.  Every time I made a change to one of the modules to fix a bug or extend the functionality, I had to restart the shell and re-import them to force a recompile.  I wonder if there's an easier way to do this.  Anyway, let me stay on the topic of CorpusCrawler.
The two modules I wrote can be downloaded here.  The code is rough since I'm writing this whole thing as a proof of concept project.  The code I wrote to provide the numbers and analysis was all done in the interactive shell after I ran through a test crawl.
At this point the only thing this really does is the crawling portion.  To kick it off, I give it a starting web site and the number of pages to download.  It downloads the raw HTML for each one and parses through it looking for URLs to go to.  I add it to the queue of sites to check if it's one that hasn't already been crawled and it's not already in the queue.  I used a queue so that the crawl would be breadth first (get the links closest to the source).  I also pull out all the text outside of HTML tags and add it to a list of data for the site object.  Once the crawl is complete I have everything in memory and I can play around with it a little bit to see how everything turned out.
For my initial run, I told it to go to http://news.google.com and to download 500 pages.  I didn't time the operation, but I'd guess it took around 10 minutes.  I know this isn't very fast and I'm sure most of the time was spent connecting to sites or downloading the HTML.  The processor utilization didn't even come close to maxing out during this whole process.  Four of the pages it tried to download produced errors.  I'll have to look into those further to figure out what happened.  Anyway, here are the initial numbers:

• pages crawled: 496
• unique links in queue: 34063
• unique words: 42176
• occurrences of "the": 17581
• occurrences of "obtuse": 0

As you can see, there's no shortage of sites to crawl.  I ensure that all of those in the queue are unique so I can be pretty sure that I'm getting new content each time.  The numbers on words are really just trash at this point.  I need to come up with methods of pulling the meaty sections of text out of a page, or just discarding the page completely if there's nothing useful there.  I'm not sure how to do that at this point but that should be my primary focus for the next few weeks.  Some other interesting numbers to note.  The word "bush" shows up 715 times.  I guess that's a symptom of crawling mostly news sites.  There are 15776 words that only show up once.  I'm calling them words, but they could be anything at this point.  Here's one example of a so called word: "=42968d1df378b715".  Obviously, I'm going to have to do some work to get this thing to be more intelligent.  Also, I said that I was only worried about English, but I noticed that some of the words pulled back were in other languages.  Another thing I'll have to worry about.
Other than the intelligence of the program, a large problem I'll have to tackle is performance.  I'm currently keeping everything in memory for these test runs.  This will have to change if I'm ever going to get this thing to crawl a large number of sites (100,000+).  Another thing about performance that worries me is that I may be spending to much time just connecting to different sites.  Would the program benefit from multi-threading so that multiple connections are being brought up simultaneously?  I can't be sure without running through some timed test runs on a consistent set of data.  This means I'd have to set up a series of sites to loop through on a local web server.  It's the only way I can be sure that I'm getting the same sites for every timed test run.  I'm going to put that idea on hold for now.  In the near term, it's ok if I have to run the program for a 24 hour period to pull back a large enough set of data.  As long as I store the data locally to manipulate it later.  At this point I just want to pull back enough pages so that I can start figuring out how to pull out the meaningful text.
Ok, now I have to give myself some homework to get done in the following week.  Here it is in bullets:

• get the crawler to store data locally
• give the crawler a resume capability so it can pick up where it left off
• run a test crawl of at least 20,000 pages

I think that's conservative enough to get done by next Wednesday.  I'll post all about it then.

And So It Begins...

I've decided what I'm going to do for my first Python project.  You'll need a little background information before I get into the project specifics.
I've become very interested in the field of Natural Language Processing.  Specifically, I want to start working with statistical approaches to NLP and corpus-based computational linguistics.  For a little information on the field check out this article.  To aid me in all this, I've recently picked up Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition.  Since I've just started with the book, it may be a little early to write a program that accomplishes something interesting in NLP.  However, there is a program that I can write which will help me prepare for my endeavors in this area.
One of the things that a statistical approach requires is a large corpus of written English (or whatever language but I'm currently only worried about English).  There are some corpora available for purchase that come on CD-ROM but there doesn't seem to be anything on-line.  Two problems I have with this are that a CD-ROM corpus is static and I don't really want to pay for it.  I want my program to be able to incorporate new material dynamically and be able to research subjects/words/language on-line.  Well in that case it sounds like this is a job for Teh Intar-Web!!1
So begins my project.  I'll call it CorpusCrawler for now since my goal is to gather together a corpus of written English and I'll be doing this by crawling the web.  The following will be very general and I may be able to refine it more as I work on the problem, but for now let's think about what the corpus should consist of.  What do I want to use it for?  Well I want the corpus to model the vocabulary of an average person.  I know "average" is very loose definition so I'll refine it a little further.  I don't need this corpus to contain domain specific vocabulary such as that found in various fields of scientific, medical, or post-baccalaureate studies.  This site claims that the average educated person has a vocabulary of about 20,000 words and uses about 2,000 in any given week.  I want to do analysis of each word and how they're used in context.  Given that, I think the corpus will have to be considerably larger than 20,000 words.  Let's say for now that I want to encounter each word about 50 times.  I expect that some words will be used much more than others.  A word like "the" will show up many, many more times than a word like "obtuse".  Well I'm not sure how to pad it out so let's just look at what that first bit gives us:

• 20000 words * 50 instances of each = 1 million words

Now I don't think  that's nearly enough and this site shows corpora with word counts at 100 million.  Well I'm not that ambitious so let's just try to get 10 million words total.  That should give me something interesting to work with.  Now comes the question of how much data that is.  Can I do this on my laptop or desktop?  Let's make some assumptions and do some basic math.

• assume 7 characters per word on average.
• store in ASCII since we're working with English so 1 byte per character
• 10,000,000 words * 7 characters per word * 1 byte per char = 70 million bytes

That's not much!  We're only talking about 0.0651926 GB.  Well there are some other factors to consider.  I'm sure I'll be adding tagging information to this data so let's just multiply that number by 10 to 0.651926 GB.  Still seems small and manageable, but while that may be all I store on my system, I'll have to download much more than that to build the corpus.  First we have to consider all of the HTML tags I'll be stripping out.  I'm sure that will increase the amount I have to download by at least 10 times.  The other problem, and this is the real tough one, is the idea that I want to work with intelligible written English.  I don't want to end up downloading bulletin board posts or advertisements that are mostly nonsense.  I figure the best stuff I'll get to work with on-line will be news articles.  News articles are generally understandable and don't have overly technical or specific language in them.  I'll have to come up with some ideas for weeding out worthless data.
Well at this point I think I'm ready for a few homework assignments.  First, I'll have to make the basic crawler program.  Once that's built, I'll have to start thinking about how to separate decent blocks of written English in web pages versus stuff that just makes no sense.  I think for now I'll just approach it with a "trial and error" approach.  I'm sure this will get better over time but for now I'm just too excited to get started.  One thing I'll need to include is specific numbers about my findings.  So here it is, in bullets:

• write basic crawler application
• write first model to separate acceptable material from that which is worthless
• show numbers from first attempts with ideas about how to improve the approach

I'll post about these while I'm working on it and hope to have the final writeup for these three things in a week or two.

A Software Idea

I had an idea today.  First, let me provide a little background information.  Like many people, I like to listen to music while I work at my computer.  I've got my entire collection in MP3s and set my audio player to play whatever I want.  I often get tired of picking what to listen to so sometimes I listen to stuff randomly.  The problem is that depending on my mood, I may not want to listen to every random track selected.  At that point I either need to task switch to the audio player and skip to the next track or just listen to the one playing and wait for it to end.  What I'd like is to be able to just say "Next" while I'm working and have it switch to the next random track.  That way I'd be able to keep my focus on my work and just issue a voice command to have the player move on.  Taking it even further, it would be nice if my audio player could remember this listening session and start selecting random tracks that match a certain style that I seem to be enjoying.  That's the idea.  A small thing, but I would pay good money for this capability.
This seems like it's a matter of two different pieces of functionality.  The first is the ability to issue voice commands and have the computer do things in the background of my work.  I see that Apple is coming close and word is that Longhorn will also feature similar technology.  The thing I don't see with these is the ability for the OS to do it in the background.  It looks like this stuff happens interactively.  I want my system to work with me behind the scenes while I'm working on other stuff.
The other part is a feature for the audio software.  It's really just an extension of the random functionality.  I'm just asking for it to be a little more intelligent.  The simplest method would be to have the user tag each track with information, like genre, which would let the player determine which tracks are like each other.  That's too much of a pain for me and it's not very adaptable.  A better method would be to have the player examine the tracks for other features, somewhat like this mentions, and tag the tracks itself.  As your tastes change and the audio software learns more about you, it can readjust the meta-data attached to each track for better song selection in the future.
This is just one idea of many in which I want my computer to work better for ME specifically.  The only way it's going to happen is if my computer starts learning about me instead of the other way around.  How long will we have to wait for computers that learn about us?  10 years? 20 years?  I wonder if I can help this become a reality quicker...

Update: It occurred to me that having the player software examine the audio track is overly complex.  You're giving the player all the information it needs when you skip from track to track.  The player could know absolutely nothing about the audio files themselves other than your reaction to one vs. the other during various listening sessions.  Obviously, it would be more random at first since it wouldn't have knowledge of your listening preferences.  It would also have to make some random choices to make sure that its decisions about what music to give you don't become stale.  Either way, this requires your computer to learn about your specific likes/dislikes and adjust its behavior accordingly.

Python vs C# homework

Earlier I posted about some of the things I thought were cool about Python.  In that post I gave myself the homework of researching similar capabilities in C#.  Here were the two things I assigned myself to do:

1. See if C# has lambda function support
2. Python allows you to pass functions around just like any old object and let you get a reference to a function by its name at runtime.  Write some code to examine this functionality in C#.

When I started to look into the first item I found that the C# 2.0 spec has support for anonymous functions.  Let's dig into this a little bit.  Here's a sample line from Mark Pilgrim's book on Python, Dive Into Python:

processFunc = collapse and (lambda s: " ".join(s.split())) or (lambda s: s)

And the description of what that does:

processFunc is now a function, but which function it is depends on the value of the collapse variable. If collapse is true, processFunc(string) will collapse whitespace; otherwise, processFunc(string) will return its argument unchanged.

How would we do this in C#?  Since C# 2.0 comes out in a few short months (I think), I'll just worry about that since I'm sure this would be hard if not impossible in 1.0.  Well I think we'd do it like so:

delegate string ProcessFunc(string s);
ProcessFunc processFunc = collapse ? delegate(string s) { ***func def*** } : delegate(string s) { return s; };

Some thoughts about the differences:  Python lambda functions can only contain one expression while anonymous functions in C# have no such limitation.  C# requires defining/typing the delegate beforehand which is something that Python's dynamic typing allows you to avoid.  I left out the function code in C# for removing all the whitespace chars in a string.  I don't think the built in string library has a function for doing this and writing that code wasn't the point of this exercise.

The second item points to a fundamental difference between the two languages.  Functions aren't first class citizens in C#.  C# uses delegates and reflection to bypass this shortcoming.  After a bit of digging and research I found this article on MethodBase.Invoke().  Although I said I wanted to write sample C# code, I'm too lazy to do it at this point and the article shows it anyway.  Here's the python snippet to do the same thing in the "Main" method of the MethodBase.Inoke() article assuming that the classes have already been defined:

print "First Method - " + str(getattr(A(), "method")())
print "\nSecond Method - " + str(getattr(B(), "method")())

Needless to say, the process was much easier in Python.  This whole bit got me to thinking about functions and the definition of "first class".  Actually, I wonder how first class they are in Python.  One thing mentioned in this wiki of first class functions is the ability to write and modify the functions themselves during program execution.  At this point I have no clue how to do that in either language and I'm not even sure that you can.  I assume that this kind of functionality is offered in Lisp but I'd have to research that too.  I'm going to shelf this issue for now, but I'll have to make sure I revisit it again in the coming months.

I'm comming to Denver!

Just in case my friends are still checking this thing I wanted to let you know that I'll be in Denver soon!  I'll be there the 13th to the 15th.  As you all know (or should know)  Saturday the 14th is my birthday!  I'm thinking it would be fun to have a party at Lounge.  Let me know what you think and if you can join me in a celebration of me!  Just kidding, we can celebrate you too.  Also, I'll be back in town from the 24th to the 29th.  That gives me a bit more time to hang out and I hope to see everyone while I'm there!  I can regale you with tales of Manhattan apertment ludicrocity, crazy ass people, and the best nightlife that anywhere I've been has to offer.

Sink or Swim with Linux

My fun with Python continues and I'm happy to say that I'm doing it all from Linux.  I decided to up the ante with my commitment to Linux.  I've loaded it on my main desktop.  It was too easy while working in a VM to just go back to the host OS and do things that I was unsure how to do in Linux.  I figure the only way I'm going to get a decent level of expertise is through total immersion.  I was a bit worried that I might corrupt my main system trying to get a dual boot configuration going, but I'm happy to say that it was a breeze.  The one problem I did encounter was getting my dual head (two monitor) configuration set up properly.  Luckily I found this article and after following its advice everything worked great!  It's a small win that I only get to enjoy for the next few days since I'm going to be away from home for the next three weeks.  I've made a decision on what project to start with Python but I'll save the details for when I get closer to starting it...

Goooooo Puritans!

As this article states, the Texas house "has approved a bill that would allow state education officials to prohibit "overtly sexually suggestive" cheering and drill team routines".  I believe this is the text of the bill and an earlier version can be found here.  Shouldn't it be the parent's job to ensure that their children are engaged in activities they deem appropriate?  Besides, one person's "overtly sexually suggestive" could just be showing too much ankle to many others.  This is completely worthless trash.  It can be interpreted so many different ways that most anything could be banned.  Notice that the earlier version gave the commissioner the ability to reduce the funding a district receives if they're in violation.  Again, what in the hell?!!  I swear that the religious right won't be happy until we're living like the Puritans.  Then we can all look forward to burning and drowning witches!
Now I just want to point out something I find incredibly funny.  The quote at the very end of the article: "We've already been looking into this thing, since our focus has been not just on technical skills but on grooming tomorrow's leaders."  Holy shit that's great! LMAO!!!1
<sarcasm>
Ahhh yes, the cheerleaders of today become the leaders of tomorrow.  That's exactly who I want leading things.  People who focus on appearance and conformity.  I think intelligence and ability are highly overrated.
</sarcasm>

P.S.  Complete side note:  I had to do a bit of digging to find the text of the bill.  Why in the hell don't on-line articles link to the source material of a story?  It's teh Intar-web for fuck sake!  Link references and source material and you may be able to actually keep your readers well informed!

First Impressions on Python

Well I didn't get as far as I'd like over the last few weeks (too much work, sick, etc...)  , but I started my foray into Python.  For now I've decided to just use IDLE since it comes with Python.  I'll dig into other IDEs when I get a little more experience.  IDLE seems like a decent environment but I must say that I miss Visual Studio.  I'm reading Dive Into Python by Mark Pilgrim to get started.  I'm five chapters in and I like the format of the book.  It assumes that you already know how to program so it doesn't waste any time and you start working with the language right away.
As I go through the features of Python I keep comparing it to Java or C#.  Dynamic typing is a bit different but I like that fact that you can't reference something you haven't assigned to (damn you VBScript!).  It's still a strongly typed language so that's the same.  Introspection is cool but the aforementioned languages have Reflection to mirror that.  Functions, and everything else for that matter, are objects so you can pass them off to anything.  I like that and my first guess about mapping that functionality to C# would be through delegates.  I'd have to write some test code and play around with both to make any determinations.  Maybe I'll make that a personal assignment over the next week.  Lambda functions look like a great tool and to be honest I'm not sure that C# has an equivalent.  Another thing that I'll have to do a little research on.  The one feature that stood out as a definite advantage over C# is the interactive shell.  I do like being able to test and run code on the fly without compiling.  This feature seems like an invaluable tool for developing stuff fast while keeping it free of obvious bugs.  I've heard this as a major argument for Lisp.  In fact, certain Lisp hackers will say that the languages of today are only trying to catch up with the functionality that Lispers have enjoyed for decades.  But for now, back to Python.  List comprehension and lists in general are sweet.  Fewer lines of code and quicker to work with than ArrayList.  All in all, I like what I'm seeing.  At the very least, this Python effort is causing me to look at C# in different ways.  At this point there are two little homework projects I'd like to assign myself.

• I want to see if C# supports anything like lambda functions.  Produce sample code in Python and C# with an examination of both methods.
• Python supports easy mapping to functions and in fact you can call to a function at runtime without knowing its name beforehand.  Is there a way to do this in C#?  Again, produce sample code in both languages.

I also need to start thinking about a project that I can implement in Python.  I have two projects that I want to start right now but I'll save that discussion for another post...