aicoder

Software pattern for proportional control of QPS in a webservice

2012-01-07T09:13:00.001-08:00

Problem Statement

Imagine you are writing a webservice that must call a back-end service, such as a data store. Let's assume (with out loss of generality) that the data store (and your hardware supporting it) has some limit in QPS that it can handle. We'd like the client system (your web service) to impose a limit on the QPS to the back-end service. Also assume that this is a distributed webservice, lots of worker threads on lots of different machines.

Requirements

Given a goal in QPS manage the maximum outgoing requests per second to that goal.
Be fast. Maintain a fast controller settling time when the goal or queries change.
Be adaptive. Respond to swings of incomming requests that need to be queried against the service.
Be distributed. Locally active against global numbers without knowing the number of workers.
Be robust. Handle additions and subtractions of worker/clients to the system without coordination. Minimize overshoot.

Design

Assume that querying this backend service, while valuable and mostly needed, is optional under duress. It's far more important for your front-end service to be responsive and return some error or 'No Content' than hang on a busted back-end. As result we'll use a sampling rate 'r' to denote the % of time that the web service should query the back-end. Under normal conditions this rate is 1 (100%). Also assume that the goal in QPS to the back-end is set in some configuration area in your system. Under duress the rate r will be adaptively tuned to obey the QPS goal. Also assume you have smartly implemented some monitoring system like Ganglia/Nagios/Cacti and are emitting events to it when you call the back-end service.

Inputs

G = Goal QPS
M = Current measured QPS (from Ganglia).
r = Current sampling rate [0,1]

Outputs

r_new = A sampling rate [0,1]

Adaptive Mechanism

r_new = r * (G/M)
r_new = MAX(0,MIN(1,r_new)) //clamp r_new between [0,1]

Benefits

Needs only global G and M as inputs.
No-coordination needed between workers/servers other than the globally observed M.
Adaptively moves the per-worker sampling rate independent of all other worker's rates.
Workers can have different incoming QPS rates from a load balancer, the controller will adapt.

Failure Modes

If the sensor for M fails to be updated then the controller is blind
If the Goal is set or re-set to zero, then the controller will stop traffic
Both of these can be addressed easily.

Desired Response

The overshoot/undershoot is called 'ringing'
The time to approach the goal is called the 'settling time'

Implementation Notes

Emit a ganglia/graphite/XXX counter for both requests sent and skipped
Use a smoothed average of the measured QPS to smooth out controller jitter.
(Optional) Each worker should do a bit of randomization of when it performs its sampling-rate-update to smooth out any startup/restart ringing.

Invertability

This design could be inverted for a server implementation. If your webservice has a set of APIs that are heavy to execute, then this controller could be used to control the incomming QPS that are delegated to the heavy work.

Receive request
Submit to sampling rate
If Yes then delegate the request to the executor
If No then respond to the client with 'HTTP 204 No Content' or equivalent empty reponse.

Standford's Introduction to Computational Advertising course

2011-12-27T09:10:00.001-08:00

Andrei Broder and Vanja Josifovski, of Yahoo! Research, have wrapped up their Stanford course again this fall. As always the lecture slides are a great intro to the area.

MS&E 239: Introduction to Computational Advertising

Computational advertising is an emerging new scientific sub-discipline, at the intersection of large scale search and text analysis, information retrieval, statistical modeling, machine learning, classification, optimization, and microeconomics. The central problem of computational advertising is to find the "best match" between a given user in a given context and a suitable advertisement. The context could be a user entering a query in a search engine ("sponsored search"), a user reading a web page ("content match" and "display ads"), a user watching a movie on a portable device, and so on. The information about the user can vary from scarily detailed to practically nil. The number of potential advertisements might be in the billions. Thus, depending on the definition of "best match" this problem leads to a variety of massive optimization and search problems, with complicated constraints, and challenging data representation and access problems. The solution to these problems provides the scientific and technical foundations for the $20 billion online advertising industry.

This course aims to provide a good introduction to the main algorithmic issues and solutions in computational advertising, as currently applied to building platforms for various online advertising formats. At the same time we intend to briefly survey the economics and marketplace aspects of the industry, as well as some of the research frontiers. The intended audience are students interested in the practical and theoretical aspects of web advertising.

Posted via email from aicoder - nealrichter's blog

Summer Program on Computational Advertising

2011-12-27T09:04:00.001-08:00

Deepak Agarwal of Yahoo Research is organizing a summer program on Computational Advertising. It appears to be geared for grad students.

http://www.samsi.info/programs/summer-program-august-6-17-2012-computational-advertising

This two-week program will run from August 6 to August 17, 2012. The first week will be at the Radisson RTP in the Research Triangle Park, NC. The location is in close proximity to SAMSI. The first three days will be spent on technical presentations by leading researchers and industry experts, to bring everyone up to speed on the currently used methodology. On the fourth day, the participants will self-organize into working groups, each of which will address one of the key problem areas (it is permitted that people join more than one group, and the organizers will try to arrange the working group schedules to faciliate that). The second week will be spent at SAMSI headquarters in Research Triangle Park.

Posted via email from aicoder - nealrichter's blog

What Software Engineers should know about Control Theory

2011-11-15T08:24:00.001-08:00

Over the years I've noticed an interesting lack of specific domain knowledge among CS and software people. Other than the few co-workers that majored in Electrical Engineering, almost no one has heard of the field of 'Control Theory'.

From Wikipedia

Control theory is an interdisciplinary branch of engineering and mathematics, that deals with the behavior of dynamical systems. The desired output of a system is called the reference. When one or more output variables of a system need to follow a certain reference over time, a controller manipulates the inputs to a system to obtain the desired effect on the output of the system.

Let's imagine that you write internet web services for a living. Some Rest or SOAP APIs that take an input and give an output.

Your boss walks up to you one day and that asks for a system that does the following:

Create a webservice that calls another (or three) for data/inputs, then does X with them.
Meters the usage of the other web services.
Your webservice must respond within Y milliseconds with good output or a NULL output.
Support high concurrency, ie not use too many servers.

The problem is that these other third-party webservices are not your own. What is their response time? Will they give bad data? How should your webservice react to failures of the others?

Does this sound familiar? It should to many. This is the replicated-and-shared-connector problem (MySQL, memcached), the partitioned-services problem (federated search, and large scale search engines) and the API-as-a-service problem (Mashery, etc).

There are two basic types of controls relevant here:

Open Loop, Feed-forward: Requires good model of system inputs and response of the system.

Closed Loop, Feed-back

Types of adaptive control are as follows:

Linear Feedback
Stability Analysis
Frequency response
response time

Adaptive Schemes

Gain Scheduling
Model Reference Adaptive Systems
Self-tuning regulators
Dual Control

Here's one survey deck from a lecture. Unfortunately for software engineers, most of the presentations of the above are in linear system form rather than an algorithmic form.

Dr. Joe L Hellerstein of Google and co-workers taught a course at U of Washington in 2008 that was more software focused. He's also written a textbook on it and a few papers.

http://research.microsoft.com/en-us/um/people/liuj/cse590k2008winter/
Joseph L Hellerstein et al "Feedback control of computing systems" 2004 Wiley Google Books Amazon
Hellerstein 2003 IBM Tech Report "Challenges in Control Engineering of Computing Systems"
Hellerstein et al "Research challenges in control engineering of computing systems" Volume: 6 Issue: 4, 2010 IEEE Trans on Network and Service Management

The course page has a collection of great links to applications papers on controllers for software systems.

I'd like to see a 'software patterns' set created for easier use by software engineers. I'll attempt to present a couple common forms as patterns in a future blog post.

Open RTB panel - IAB Ad Ops Summit 2011

2011-11-10T10:23:00.000-08:00

Monday November 7th I was on an IAB Ops panel on OpenRTB.

The clip shows an exchange after Steve from the IAB asked a question about how webpage inventory is described in RTB. I described an example of differentiating a simple commodity, barley.

Two of the major uses of barley in the US are animal feed and malting for making beer. Malting barley has specific requirements in terms of moisture content, protein percentage and other factors. Farmers don't always know what quality their crop will finish at. They count on having two general markets, if the tested quality meets malting standards then the premium over feed prices can be healthy. A 2011 report noted that malting barley provided a 70% premium over feedstock barley. Growing specific varieties and/or using organic farming methods can provide additional premiums over generic feed barley. The curious can follow the links below.

How does this relate to publishers and advertising and OpenRTB? In my opinion we need several things standardized:

1) Inventory registration and description API. Allows publishers influence on how their inventory is exposed in various demand-side and trading-desk platforms. Publishers should fully describe their inventory in a common format. Buy-side GUIs and algorithms will benefit from increased annotation and categorization. This can also harmonize the brand-safety ratings that are not connected between the sell and buy sides.

2) Standardization of the emerging 'Private Marketplace' models in RTB. A set of best practices and trading procedures for PM needs to be defined such that the market can grow properly.

While the main bid request/response API of OpenRTB has been criticized as being 'too late' given the large implementations in production, it is not too late to define standards for the above. These things will help the buy-side better differentiate quality inventory.

SchemaMgr - MySQL schema management tool

2011-07-12T22:49:00.001-07:00

SchemaMgr is a simple perl tool to manage schema change in MySQL DBs. I wrote this in 2007/2008 and it has been used in production for many years.

https://github.com/nealrichter/schemamgr

Each change is assigned a version number and placed in a file. When the SQL in the file is executed successfully, a special table is set with that version number. Subsequent runs install only the higher versioned files.

It can also be used to reinstall views and stored procedures.

The best practice is to copy the file and change X in the filename and in the $DB_NAME variable.

$ ./bin/schemamgr_X.pl
Usage: either create or upgrade X database
schemamgr_X.pl -i -uUSERNAME -pPASSWORD [-vVERSION] [-b]
  updates DB of to current (default) or requested version
schemamgr_X.pl -s -uUSERNAME -pPASSWORD
  reinstalls all stored procedures
schemamgr_X.pl -w -uUSERNAME -pPASSWORD
  reinstalls all views
schemamgr_X.pl -q -uUSERNAME -pPASSWORD
  Requests and prints current version
Optional Params
 -vXX -- upgrades upto a specific version number XX
 -b   -- backs up the database (with data) before upgrades
 -nYY -- runs the upgrades against database YY - default is X

By convention you create ONE create_X_objects_v1 file with a date.
All other files are update files with greater than v1 numbers.

build/
|-- create_X_objects_v1_20110615.sql
|-- update_X_objects_v2_20110701.sql
`-- update_X_objects_v3_20110702.sql

Posted via email from aicoder - nealrichter's blog

Managing yourself to tasks and finishing them.

2011-06-28T09:02:00.001-07:00

I saw these two short articles from HBR come across my twitter stream and read them. They stuck with me for more than a week as they triggered some connections with proof methods.

Treat Every Task as Three Steps, Not One

The essence of the advice is "Prep-Do-Review". For each task you do make and review a plan for it before starting. Once the task completed review the plan. Did you finish? What did you learn? What would you do differently next time?

How to Become a Great Finisher

The essence of this advice is to think in terms of "to-go" versus "to-date" performance on a task. When you entertain to-date thinking it's very easy to see how much you have accomplished so far. This can lead to a lowering of ongoing effort or allow yourself to become distracted and work on other tasks.

So the optimal algorithm that combines the two is:

PrepForWork();

Do {

IncrementalWork();

X = DistanceToFinish();

} Until (X == 0)

ReviewResults();

Don't look back until you are done!

Note that there is a formal method of proof in mathematics and CS that goes something like this:

1) Define an integral metric f(x) measuring the distance to the goal

2) Define the starting distance

3) Show that your "algorithm/method" monotonically decreases f(x)

4) Infer that the goal will be reached

5) (Optional) Calculate the minimum number of steps required to reach the goal.

The important point is the rigor of the mathematical proof version. Your idea gets no partial credit for so-far progress, the algorithm either gets to the goal or it fails. The proof is either true or it is false. Thus you are either Done or you are NOT Done.

Posted via email from aicoder - nealrichter's blog

JSON parsing speed in various Node.JS versions

2011-04-07T14:21:00.001-07:00

We use Node.JS for a very high capacity service at the Rubicon Project. It often drives or handles in excess of 10B HTTP requests per day sending or receiving JSON data.
Out of curiosity I ran some tests on JSON parsing speed in different versions of Node.JS

node.js code:

var sys = require('sys');
var data = "{ \"item_uuid\": \"8ec56438-d3cf-442a-bbf7-7f076f229f35\", \"return_code\": 0, \"data\": [ { \"valid\": true, \"votes\": 2345, \"date\":\"Thu, 07 Apr 2011 15:17:17 EDT\", \"headline\": \"Senate Majority Leader Harry Reid indicates there likely will be a government shutdown on Friday. Lawmakers have been unable to agree on a new federal budget\", \"source\": \"Yahoo News\", \"published\":{\"hour\":\"19\",\"timezone\":\"UTC\",\"second\":\"17\",\"month\":\"4\",\"minute\":\"17\",\"utime\":\"1302203837\",\"day\":\"7\",\"day_of_week\":\"4\",\"year\":\"2011\"} } ] }";
try {
for(var i = 0; i < 1000000; i++)
{
var tmp = JSON.parse(data);
}
} catch(e) { sys.puts("ERROR: on parsing JSON with v8 parser"); }
sys.puts(data);
var tmp = JSON.parse(data);
sys.puts(JSON.stringify(tmp));
sys.puts("\n DONE \n");
process.exit();

Essentially this re-parses the same example JSON (I created a fake RSS like JSON pacakge) 1M times.

Here are the results:

Node 0.1.3x: real 0m30.050s
Node 0.2.6: real 0m30.050s
Node 0.3.8: real 0m9.915s
Node 0.4.5: real 0m9.999s

For reference I ran the same test against a very fast tokening parser in C called jsmn, and a C++ one called vjson.

jsmn: real 0m2.276s
vjson: real 0m7.465s Note that vjson is a destructive parser, and I had to fix that first.

Interestingly the JSON parser in node 0.4.5 and prior versions appears to be written in pure Javascript. See the file: node-v0.4.5/deps/v8/src/json.js

It's unclear if the speed improvements are a result of improvements to the parser implementation or in some efficiency/speed leap in versions of V8 included in Node versions.

Node 0.1.33: v8: 2010-03-17: Version 2.1.5
Node 0.2.6: v8: 2010-08-16: Version 2.3.8
Node 0.3.8: v8: 2011-02-02: Version 3.1.1
Node 0.4.5: v8: 2011-03-02: Version 3.1.8

Posted via email from aicoder - nealrichter's blog

Pamela Samuelson on startups and software patents

2011-03-22T21:26:00.001-07:00

Following up on my last post here is the view from Pamela Samuelson:

Why software startups decide to patent ... or not

Two-thirds of the approximately 700 software entrepreneurs who participated in the 2008 Berkeley Patent Survey report that they neither have nor are seeking patents for innovations embodied in their products and services. These entrepreneurs rate patents as the least important mechanism among seven options for attaining competitive advantage in the marketplace. Even software startups that hold patents regard them as providing only a slight incentive to invest in innovation.

She also lists a variety of reasons why these software entrepreneurs decided to forgo patenting their last invention. It's a very interesting write up.

Posted via email from aicoder - nealrichter's blog

Comments re "The Noisy Channel: A Practical Rant About Software Patents"

2011-03-10T14:30:00.001-08:00

The Noisy Channel: A Practical Rant About Software Patents - [My comments cross-posted here]

Daniel, nice writeup.

I worked for a BigCo and filed many patents. It was a mixed bag. The time horizon is so long that even after I’ve been gone for 3.5 years many of them are still lost in the USPTO. Average time for me to see granted patents was 5+ years.

Here are my biased opinions:

1) Patents really matter for BigCos operating on a long time horizon. It’s a strategic investment.

2) Patents are nearly worthless for a Startup or SmallCo. The time horizon is way past your foreseeable future, and thus the whole effort is akin to planning for an alternate reality different than the current business context. Throwing coins in a fountain for good luck is about as relevant. You simply are better off getting a filing date on a provisional design writeup and hiring an engineer with the money you’d spend on Patent lawyers.

3) As an Acquiring company looking at a company to acquire, Provisional or Pending Patents are a liability not an asset. They take time and resources to push to completion for a strategy of deterrence.

4) Patents are mostly ignored in the professional literature. Take Sentiment Analysis as one example. Sentiment Analysis exploded in 2001 w.r.t. Academic publishing, yet there are more than a few older patents discussing good technical work on Sentiment Analysis. I’ve NEVER seen an algorithm in a patent cited in a paper as previous work. And I have seen academic papers with algorithms already 90% covered by an older patent… and the papers are cited as ‘novel work’.

5) Finding relevant patents is ludicrously hard. It might be the most challenging problem in IR w.r.t. a corpus IMO. Different words mean the same thing and vise versa due to the pseudo-ability in a Patent to redefine a word away from the obvious meaning. With two different lawyers rendering the same technical design into a writeup and claims results in wildly different work product.

6) I’ve seen some doosey granted Patents. Things that appear to either be implementations of very old CS ideas into new domains.. or worse stuff that would be a class project as an undergrad.

It’s just plain ugly in this realm.

Posted via email from aicoder - nealrichter's blog

On Strategic Plans

2011-03-10T01:20:00.001-08:00

This needs absolutely no comment.

“We have a ‘strategic plan.’ It’s called doing things.” ~ Herb Kelleher

Posted via email from aicoder - nealrichter's blog

Hilarious system calls in the BeOS

2011-03-06T10:20:00.001-08:00

These system calls in the BeOS still make me smile.

int32 is_computer_on(void)

Returns 1 if the computer is on. If the computer isn't on, the value returned by this function is undefined.

double is_computer_on_fire(void)

Returns the temperature of the motherboard if the computer is currently on fire. If the computer isn't on fire, the function returns some other value.

#include <stdio.h>
#include <be/kernel/OS.h>
int main()
{
printf("[%d] = is_computer_on()\n", is_computer_on());
printf("[%f] = is_computer_on_fire()\n", is_computer_on_fire());
}

These functions serve a similar purpose to getpid() in Unix, essentially no-op calls that can be used to test the kernel's intrinsic response time under load.

Write up of BeOS history is here, Haiku is an open source clone of the BeOS that is curiously under active development.

Posted via email from aicoder - nealrichter's blog

Contractor Needed: HTML/CSS/Javascript Ninja

2011-03-04T09:21:00.001-08:00

The Rubicon Project is looking for an in-browser HTML/CSS/Javascript Ninja to restructure the workflow of an application GUI. The server side code is perl/mod_perl. Please contact me if you are interested and available. The contract is 4-6 weeks.

Posted via email from aicoder - nealrichter's blog

Job Post: Software Engineer/Scientist: Ad Serving, Optimization and Core Team

2011-03-03T12:26:00.001-08:00

LOCATION: the Rubicon Project HQ in West Los Angeles or Salt Lake City

the Rubicon Project is on a mission to automate buying and selling for the $65 billion global online advertising industry. Backed by $42 million in funding, we are currently looking for the best engineers in the world to work with us.

Team Description

The mission of the Core Team is to build robust, scalable, maintainable and well documented systems for ad serving, audience analytics, and market analysis. Every day we serve billions of ads, process terabytes of data and provide valuable data and insights to our publishers. If building software that touches 500+ million people every month is interesting to you, you'll fit in well here.

Some of the custom software we've built to solve these problems include:

A patented custom ad engine delivering thousands of ad impressions per second with billions of real time auctions daily
A real time bid engine designed to scale out to billions of bid requests daily
Optimization Algorithms capable of scheduling and planning adserving opportunities to maximize revenue
Client side Javascript that performs real-time textual analysis of web pages to extract semantically meaningful data and structures
A web-scale key value store based on ideas from the Amazon Dynamo paper used to store 100s of millions of data points
Unique audience classification system using various technologies such as Solr and Javascript for rich, real-time targeting of web site visitors
Data Mining buying and selling strategies from a torrent of transactional data
Analytics systems capable of turning a trillion data points into real business insight

Job Description

Your job, should you accept it, is to build new systems, new features and extend the functionality of our existing systems. You will be expected to architect new systems from scratch, add incremental features on existing systems, fix bugs in other people's code and help manage production operations of the services you build. Sometimes you'll have to (or want to) do this work when you are not in the office, so working remote can't scare you off.

Most of our systems are written in Perl, Java, and C, but we have pieces of Python, Clojure and server-side Javascript as well. Hopefully you have deep expertise in at least one of these; you'll definitely need to have a desire to quickly learn and work on systems written in all of the above.

You should also have worked with and/or designed service oriented architectures, advanced db schemas, big data processing, highly scalable and available web services and are well aware of the issues surrounding the software development lifecycle. We expect that your resume will itemize your 3+ years experience, mention your BS or MS in Computer Science and be Big Data Buzzword Compliant.

Bonus points for experience with some of the technologies we work with:

Hadoop
NodeJS
MySql
Solr/Lucene
RabbitMQ
MongoDB
Thrift
Amazon EC2
Memcached
MemcacheQ
Machine Learning
Optimization Algorithms
Economic Modeling

Apply Now! Click the Apply button!

Posted via email from aicoder - nealrichter's blog

A note on software teams and individuals

2011-02-28T13:06:00.001-08:00

I'm currently running a loosely coupled team of people all working on a common initiative. While this is not my first time running a team, the same set of things seem to happen with all 'new' teams. Here's a quick set of observations.

The first major observation is that teams of engineers can quickly fall into operating like a "golf team" versus a "football team". In Golf, each team member generally competes against all other players (and their different teams) as an individual. A given team wins if it's individual players collectively do better than some other team's players. Football (or Soccer or Basketball) is very different. A team wins in the face of good opposition only if it plays as a team.

For software teams, done means one thing: the team is done with the milestone or project. Done means finished, tested and shipped code. Does does not mean "my part works", or "my tasks are done".

IMO each team member should answer these questions to the group every day:

What direction I am going relative to team goals.
What specific items I am working on today.
Does anyone need any help from me?
Do I need any help with my work?

Team managers, both the overall and functional leads, should ask or answer these questions for the group every day:

Are we as a group going the right direction (towards the goal)?
Will we meet the timeline and/or functional goals?
Is there any functional or task ambiguity that needs working out?
Are any course corrections needed?

The second observation is that there are two major indicators of if a given individual is a good addition to the team:

Does this person communicate well and often?
Does this person have the capability and desire to resolve ambiguity on their own when possible?

The second skill, resolving ambiguity, is in my opinion the primary question that a software hiring manager needs to answer in the affirmative about a given candidate... assuming of course the candidate has the needed skills.

Much of this also circles back on a blog post that Jordan Mitchell wrote years ago when I was hip-deep in code at Others Online.

Actual vs. Perceived Progress

Posted via email from aicoder - nealrichter's blog

RightNow - Our cowboys ride code

2011-02-07T15:13:00.000-08:00

This is a neat little ad in the January Delta Sky Magazine for RightNow Technologies, where I worked from 1999-2007.

RightNow Technologies serves about 10 billion [customer interactions] a year through he companies and institutions it works with. “Every person in North America has used one of our solutions about 25 times,” says Gianforte.

Why RightNow keeps its headquarters in Bozeman, MT

The quality of life here is a huge advantage, but more importantly, says Gianforte, “there’s a ranch saying around here that goes,‘When something needs to get done, well then, we’re just gonna get ‘er done.’ In many environments, they have to form a committee, pull in consultants and such to make things happen, but our clients appreciate that when something needs to get done, we can easily make that hap pen because of the work ethic here.”

The Provenance of Data, Data Branding and "Big Data" Hype

2011-01-30T23:45:00.001-08:00

The credibility of where data comes from in all these "big data" plays is absolutely crucial. Waving hands re "algorithms" won't cut it. @nealrichter Jan 27, 1010 Tweet

To expand on this tweet here's the argument: If one of your key products as a startup or business is to "crunch data" and derive or extract value from it then you should be concerned about data provenance. This is true whether you are crunching your own data or third-party data.

Some examples:

Web analytics - crunch web traffic and distill visitation and audience analytics reports for web site owners. Often they use these summaries to make decisions and sell their ad-space to advertisers.
Semantic Web APIs - crunch webpages, tweets etc and return topical and semantic annotations of the content
Comparison shopping - gather up product catalogs and pricing to aggregate for visitors
Web publishers - companies who run websites
Prediction services - companies that use data to predict something

In each of the above categories the provenance of the input data and brand of the output data is key. For each of the above one could name a company with either solid-gold data OR a powerful brand-name and good-enough data. Conversely we can find examples of companies with great tech but crappy data or a weak brand.

For web publishers, those that host user-generated content have poor provenance in general compared to news sites (for example). A notable exception is Wikipedia who has a pure "UGC" model but a solid community process and standards to improve provenance of their articles (those without references are targeted for improvement).

In comparison shopping Kayak.com has good data (directly from the airlines) and has built a good brand. The same is true of PriceGrabber and Nextag. TheFind.com on the other hand appears to have great data and tech, but no well known brand.

(I'm refraining from going into specific examples or opinions on big data companies to avoid poking friends in the eye.)

The issue of Provenance and Branding is especially important in sales situations where you are providing a tool (analytics) that helps your customer (a sales person) sell something to a third-party (their customer). If the input data you are using either has a demonstrable provenance or a good brand you'll have an easier time convincing people that the output of your product is worth having (and reselling).

The old saying for this in computer science is Garbage In, Garbage Out.

In "big data" world of startups that is blowing by Web 2.0 as the new hotness there is a startling lack of concern about data provenance. The essentially ethos is that if we (the Data Scientists) accumulate enough data and crunch it with magical algorithms then solid-gold data will come out... or at least that's what the hype machine says.

The lesson from the financial melt down is that magical algorithms making CDOs, CMOs and other derivatives should be viewed with a lens of mistrust. The GIGO principle was forgotten and no one even cared about the provenance (read credit quality) of the base financial instruments making up the derivatives. The credit rating agencies were just selling their brand and cared little about quality.

In my opinion, there is a clear parallel here to "big data". Trust must be part of the platform and not just tons of CPUs and disk-space. A Brand is a brittle object that is easily broken, so concentrate on quality.

Posted via email from nealrichter's posterous

Finance for Engineers

2011-01-14T00:23:00.001-08:00

Last summer I took a great mini-course at MIT Sloan on Finance. It's essentially a breadth-first review of the MBA course complete with three case studies and a review of project evaluation methods via net present value analysis. Approximately 80% of the attendees were engineers/techies with 10+ years experience.. and maybe 25% w/ PhDs.

Fundamentals of Finance for the Technical Executive

TextBook was: Higgins - Analysis for Financial Management

The first case study is Wilson Lumber from Harvard. The material is copyrighted, yet these links look like accurate distillations by business students.

The initial position is that Wilson Lumber growing small business with good suppliers and loyal customers. Volume and revenue are all up period over period. Question is should the bank increase is line of credit to fund the business. Once you break down the financial statements and model the business, the answer is No. Essentially Mr Wilson is over extended by many measures and is growing at the expense of his balance sheet, loaning him money will only make the problem bigger down the road. His basic options are to take in a partner as co-owner for cash, go broke or raise prices to lower volume and improve margins and slowly rebuild the balance sheet.

We then went through two NPV exercises. The first was a basic analysis of go/no-go on an engineering project with a bottom up analysis via putting all cost/benefit assumptions in a model and iterating though possibilities. The second was an analysis of a joint-venture between two biotech companies. Everything from external capital, deal structure to market penetration projections were worked in. Very informative and pretty interesting work for engineers to do once the terminology and methods were explained.

Professor Jenter shared two amusing anecdotes:

His MIT and Stanford MBA students often run off to found start-ups and forget the basic Wilson Lumber case. By the time they approach him for help it's too late and they are in Mr Wilson's position: shut-down, take in $$ and lots of equity dilution (and loss of control) or slow growth dramatically.
Also a quote along the lines of "Startups founded by MIT PhDs fail at a rate above far average".

This certainly hammered home the lesson that strategic planning for growth is very important, even for what look like non hyper-growth (software) companies. I'd recommend this course to any engineer wanting a quick structured intro to basic financial management.

Posted via email from nealrichter's posterous

List of Best Paper awards in CS/AI/ML conferences

2010-12-30T09:34:00.001-08:00

The below is a great list of best paper awards for WWW, SIGIR, CIKM, AAAI, CHI, KDD, SIGMOD, ICML, VLDB, IJCAI, UIST since 1996

http://jeffhuang.com/best_paper_awards.html

Interesting thing to note: Google is ranked last in frequency, Microsoft first.

This needs NIPS and possibly UAI added to it.

http://nips.cc/ConferenceInformation/PaperAwards

Posted via email from nealrichter's posterous

Managing Open Source Licenses

2010-12-29T11:18:00.001-08:00

From time to time I have helped companies do Open Source code audits in their own source code. Basically this consists of auditing their code to find open source code.

These code audits are particularly important during software releases and M&A events. I've helped companies do this for releases and been on both sides of M&A event driven audits.

If the developers have kept the attributions with any open source code they have re-used then grep is a fine tool for auditing. However this is a big IF. If your developers are sloppy and do not keep the attributions (ie copyright and license notices) with code they lift from open source you have a problem. A software tool needs to be used to scan the corporate source for hits in open source repositories.

There are at least three companies providing software to do this:

Ideally the outcome of this process is as follows:

A clear company policy is set on what open source licenses are allowed and how developers can use open source come or components.
The corporate code is cleanly annotated with any third party attributions (see below).
Open Source code that has bad licenses for commercial usage is identified and removed before release.
A Bill of Materials is created for each release listing third-party software in the release.
Necessary copyright or other notices appear in About dialogs, manuals or product websites.

Example comment block:

/*

* XYZ.com Third-party or Open Source Declaration

* Name: Bart Simpson

* Date of first commit: 04/25/2009

* Release: 3.5 “The Summer Lager Release”

* Component: tinyjson

* Description: C++ JSON object serializer/deserializer

* Homepage: http://blog.beef.de/projects/tinyjson/

* License: MIT style license

* Copyright: Copyright (c) 2008 Thomas Jansen (thomas@beef.de)

* Note: See below for original declarations from the code

*/

If the above were upgraded to be in a javadoc style comment then a tool could be built to auto-magically generate a Bill of Materials for each release.

There is one grey area in all this: how to handle developers using code from discussion sites like PHP.net, CodeProject, StackOverflow and similar sites. Generally code put in these type of forums has no defined license. In this case the code is either copyrighted by the site or the author of the post... and developers should not use the code without getting an explicit license. However developers generally feel like people put the code up there to share. This conflict means the company policy on usage of this type of code must be clearly communicated to all developers.

This is a nice review article of other considerations for open source auditing:

Dr Dobbs: Managing Open Source Licensing by Kamal Hassin

Posted via email from nealrichter's posterous

Stochastic Universal Sampling/Selection

2010-12-17T09:11:00.001-08:00

Stochastic Universal Sampling is a method of weighted random sampling exhibiting less bias and spread that classic roulette wheel sampling. The intuition is a roulette wheel with n equally spaced steel balls spinning in unison around the wheel. This method has better properties and is more efficient that doing repeated samples from the wheel with or without replacement of the selected items.

Baker, James E. (1987). "Reducing Bias and Inefficiency in the Selection Algorithm". Proceedings of the Second International Conference on Genetic Algorithms and their Application (Hillsdale, New Jersey: L. Erlbaum Associates): 14–21.

Reference implementations on the web are scare, so here are a few:

Christian Borgelt

http://fuzzy.cs.uni-magdeburg.de/studium/ga/src/sus.c

Dan Dyer

https://github.com/dwdyer/watchmaker/blob/master/framework/src/java/main/org/uncommons/watchmaker/framework/selection/StochasticUniversalSampling.java

University of New Mexico

http://epr.adaptive.cs.unm.edu/asm/code.html

GMU's ECJ

http://cs.gmu.edu/~eclab/projects/ecj/docs/classdocs/ec/select/SUSSelection.html

See the SUSSelection.java buried in the latest tarball.

Posted via email from nealrichter's posterous

Computing, economics and the financial meltdown (a collection of links)

2010-11-22T15:58:00.001-08:00

This editor's letter from CACM last year is interesting: The Financial Meltdown and Computing by Moshe Y. Vardi

Information technology has enabled the development of a global financial system of incredible sophistication. At the same time, it has enabled the development of a global financial system of such complexity that our ability to comprehend it and assess risk, both localized and systemic, is severely limited. Financial-oversight reform is now a topic of great discussion. The focus of these talks is primarily over the structure and authority of regulatory agencies. Little attention has been given to what I consider a key issue—the opaqueness of our financial system—which is driven by its fantastic complexity. The problem is not a lack of models. To the contrary, the proliferation of models may have created an illusion of understanding and control, as is argued in a recent report titled "The Financial Crisis and the Systemic Failure of Academic Economics."

Krugman's essay at the time How Did Economists Get It So Wrong? gave a nice history of economic ideas, the models behind and his interpretations of their correctness.

The theoretical model that finance economists developed by assuming that every investor rationally balances risk against reward — the so-called Capital Asset Pricing Model, or CAPM (pronounced cap-em) — is wonderfully elegant

[snip]

Economics, as a field, got in trouble because economists were seduced by the vision of a perfect, frictionless market system.

[snip]

H. L. Mencken: “There is always an easy solution to every human problem — neat, plausible and wrong.”

I read this months ago and it's been percolating in my thoughts since then. My Manhattan Project - How I helped build the bomb that blew up Wall Street by Michael Osinski. Osinski wrote much of the software and models used to form CMOs and CDOs. Essentially the software aggregates debt instruments from mortgage and other debt markets and allowed a bond designer to issue tailor-made portfolio of debt while mitigating default risk of the debt via that aggregation. He called it his sausage grinder.

“You put chicken into the grinder”—he laughed with that infectious Wall Street black humor—“and out comes sirloin.”

Here's a large collection of links from that period that are worth reading. My thought at the moment is this nugget from Twitter:

Poormojo "Any sufficiently advanced financial instrument is indistinguishable from fraud."

Recipe for Disaster: The Formula That Killed Wall Street

Wall Street’s Math Wizards Forgot a Few Variables

Tales From Lehman’s Crypt

Economic View: Flaw in Free Markets: Humans

Andrew Low: This is your brain on prosperity

A crisis of politics, not economics: Complexity, Ignorance, and policy failure.

Revenge of the Nerd: Paul Wilmott is out to save Wall Street's soul—one dork at a time.

A Conversation with David E. Shaw

Don't Blame The Quants by Steven Shreve

http://www.nytimes.com/2009/10/14/opinion/14trillin.html?em=&adxnnl=1&adxnnlx=1255543552-DPpTSk3i4f5lEJZALsigRA

Sciam: Does Economics Violate the Laws of Physics?

Systemic Risk and Fannie Mae

Geeks trump alpha males as algos dominate Wall St

Posted via email from nealrichter's posterous

Review of "Learning to Rank with Partially-Labeled Data"

2010-10-27T00:02:00.001-07:00

I've been attending the University of Utah Machine Learning seminar (when I can) this fall. PhD student Piyush Kumar Rai is organizing it.

I volunteered to take the group though Learning to Rank with Partially-Labeled Data by Duh & Kirchhoff. I have some experience researching and implementing LTR algorithms, mostly using reinforcement learning or ant-system type approaches. Some general intro here.

The paper presents the main Transductive Learning algorithm as a framework, then fills in the blanks with Kernel PCA and RankBoost. Several Kernels are used: Linear, polynomial, radial basis function and knn-diffusion. RankBoost learns a kind of ensemble of 'weak learners' with simple thresholds.

The main reason to read the paper if you are already familiar with LTR is the use of the transductive algorithm.

Note the DISCOVER() & LEARN() functions. These are the unsupervised and supervised algorithm blanks they fill with Kernel PCA and RankBoost. What the first actually does is learn a function we could call EXTRACT() that can extract or create features for later use. They do show that the basic idea of layering in unlabeled data with labeled data is a net gain.

There are some issues with the paper. First the computational time performance, as they admit, is not good. The other is that their use of Kernel PCA in an information retrieval context is a bit naive IMO. The IR literature is full of hard-won knowledge of extracting decent features from documents. See this book for example. This is mostly ignored here.

The more confusing thing is the use of K-Nearest Neighbor diffusion kernels. Basically they take the vector of documents, form a matrix by euclidean distance and then random-walk the matrix for a set number of time-steps. The PCA then takes this 'kernel' output and solves the eigenvalue problem, to get the eigenvectors. This all seems a round-about way of saying they approximated the Perron-Frobenius eigenvector (sometimes call PageRank) by iterating the matrix a set number of times and zeroed out low order cells. Or at least I see no effective difference between what they did and what I just described. Basically they just make the matrix sparse to solve it easier (ie this is the dual).

Their use of various classic IR features like TFIDF, BM25 etc needed help. There's pleny of IR wisdom on how to use such features, why let the DISCOVER() wander about attempting to rediscover this? The results were also muddled with only one of the three data sets showing a significant improvement over a baseline technique.

All that aside, it's worth a read for the intro to the transductive alg used with an IR centric task.

Posted via email from nealrichter's posterous

Stanford Computational Advertising course - Fall 2010

2010-10-26T23:07:00.001-07:00

Andrei Broder and Vanja Josifovski of Yahoo Research Labs are again offering a Fall course on Computational Advertising at Stanford.

Great intro to the area.

Posted via email from nealrichter's posterous

Strategic Marketing

2010-08-16T12:44:00.001-07:00

I highly recommend this ExecEd course at MIT Sloan: Strategic Marketing for the Technical Executive.

Duncan Simester taught it. The course looks to be a condensed form of this course: 15.810 Marketing Management

Key takeaways:
1) Making decisions by experimentation versus meetings+intuition is crucial.
2) Don't assume your role is to know the answer. Your role is really to work out how to find the answer as quickly as possible.
3) Brand is unimportant when customers can observe you are meeting their needs.
4) Brand is important when they can't search/observe and must reason with less data.
5) Don't price your products based upon cost or competition, work out your true value to the customer.

6) Your actual efficiencies might be different than you assume

7) Experiment and iterate as often as you can

Posted via email from nealrichter's posterous

Dissertation done!

2010-07-27T17:44:00.001-07:00

The big event of the spring was defending and completing the below.
Really happy to be done.

Advice for working professionals attempting a PhD:
1) pick something relevant to your work.
2) think twice about a theoretical topic.
3) don't make it longer/bigger than necessary.
4) don't grow your family during this time

I did not follow this advice and this likely resulted in a 4 year delay. The outcome was great and the topic is now relevant to the new job at Rubicon.

http://nealrichter.com/research/dissertation/

On Mutation and Crossover in the Theory of Evolutionary Algorithms

Abstract:
The Evolutionary Algorithm is a population-based metaheuristic optimization algorithm. The EA employs mutation, crossover and selection operators inspired by biological evolution. It is commonly applied to find exact or approximate solutions to combinatorial search and optimization problems.

This dissertation describes a series of theoretical and experimental studies on a variety of evolutionary algorithms and models of those algorithms. The effects of the crossover and mutation operators are analyzed. Multiple examples of deceptive fitness functions are given where the crossover operator is shown or proven to be detrimental to the speedy optimization of a function. While other research monographs have shown the benefits of crossover on various fitness functions, this is one of the few (or only) doing the inverse.

A background literature review is given of both population genetics and evolutionary computation with a focus on results and opinions on the relative merits of crossover and mutation. Next, a family of new fitness functions is introduced and proven to be difficult for crossover to optimize. This is followed by the construction and evaluation of executable theoretical models of EAs in order to explore the effects of parameterized mutation and crossover.

These models link the EA to the Metropolis-Hastings algorithm. Dynamical systems analysis is performed on models of EAs to explore their attributes and fixed points. Additional crossover deceptive functions are shown and analyzed to examine the movement of fixed points under changing parameters. Finally, a set of online adaptive parameter experiments with common fitness functions is presented.

Finalized April 19, 2010

Posted via email from nealrichter's posterous

RFP: Bounding memory usage in Tokyo Cabinet and Tokyo Tyrant

2009-11-02T17:47:00.001-08:00

I'm soliciting proposals to implement an absolute (or at least soft) bound on memory usage of TT + TC. The reward is cash. Send me a proposal. The patch needs to work, not crash TT/TC or corrupt data.

Here's a start: http://github.com/nealrichter/tokyotyrant_rsshack

I've attempted to do this myself and have not had the time to finish or fully test it. I've asked Mikio for feedback/help finishing this and he's been nearly silent on the request.

At the moment we (myself, Sam Tingleff and Mike Dierken) work around this issue by continuing to play with various parameter TC settings and restarting the daemon when the memory usage grows beyond a comfort level.

I'm a C coder and have hacked the internals of BerkeleyDB in the past, so can help review code, trade ideas, etc. We (as a team) don't have the time to work on this at the moment.

If you are interested contact me! We've got a few other ideas for TT enhancements as well...

Posted via email from nealrichter's posterous

Current Computational Advertising Course and Events

2009-10-28T23:11:00.001-07:00

Andrei Broder and Vanja Josifovski of Yahoo Research Labs are offering a Fall 2009 course on Computational Advertising at Stanford. The lecture #1-#4 slides are up and it looks to be an interesting course. Will definitely continue to follow along remotely.

National Institute of Statistical Sciences is holding a workshop on CompAdvert in early November. The upcoming WINE'09 conference in Rome contains a few accepted papers in CompAdvert. SigKDD 2010 mentions it in the CFP..

Luckily the search engine results on 'Computational Advertising are still free of noise. Google, Yahoo, Bing

Prior Events:

Posted via email from nealrichter's posterous

References for mining from streaming data

2009-09-18T23:21:00.003-07:00

While reading a lower quality paper on the subject I found these references worth tracking down. Essentially the idea is that you can make one-pass through the data and must produce statistics of the data that are approximate in nature, ideally with bounded approximation error.

Gibbons et al 1997: Fast Incremental Maintenance of Approximate Histograms
Incremental maintenance of histograms primarily for database query planners

Manku and Motwani 2002 Approximate frequency counts over data streams.
They show algorithms called sticky sampling and lossy counting with proven error bounds.

Zhu et al. 2002 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time
Basic stats and high correlations between all pairs of data streams

Cormode and Muthukrishnan's 2003 What's Hot and What's Not: Tracking Most Frequent Items Dynamically
Introduced groupTest probabilistic Monte Carlo algorithm for frequent item tracking

Metwally et al 2005 Efficient Computation of Frequent and Top-k Elements in Data Streams
Uses counters to monitor data streams with a new stream-summary data structure

Cheng et al 2005 Time-Decaying Bloom Filters for Data Streams with Skewed Distributions
Dampened Bloom-filters for frequent items

Three papers on frequent itemsets (different than frequent items):

Jiang and Gruenwald have a pair of 2006 papers
Research Issues in Data Stream Association Rule Mining
Survey paper of issues and previous results

CFI-Stream: Mining Closed Frequent Itemsets in Data Streams
New stream based itemset miner

Tsai and Chen 2009 Mining Frequent Itemsets for data streams over Weighted Sliding Windows
Apriori like itemset miner on windows of data with differential weighting

Langford et al. 2008 Sparse Online Learning via Truncated Gradient
Induced sparsity in the weights of online learning algorithms with convex loss functions

(9/19) Corrected the StatStream link - hat tip @dataspora
Added Langford - hat tip @gappy3000

Posted via email from nealrichter's posterous

Others Online acquired by the Rubicon Project

2009-09-17T12:30:00.001-07:00

I'm thrilled to say that Others Online has been scooped up by the Rubicon Project. Press release here. I'm joining as a Data Scientist. Jordan authored a wrap-up post here: http://blog.othersonline.com/

Update: Nice Forbes article on the opportunity in front of us.
For Advertisers Drowning In Data, A Lifeguard

Posted via email from nealrichter's posterous

Google AdWords now personalized

2009-09-14T11:54:00.001-07:00

Hat Tip: Found via Greg Linden's blog: Google AdWords now personalized. Below are my thoughts and questions:

Google is now reaching back into your previous search history and presumably choosing a better previous search if the current one is not sufficiently monetizable.

Questions:

Is the goal of Google to increase the fill-rate of ads or to show more valuable ads in general?
What criteria is used to reach back into a user's history? Boolean commercial/non-commercial then select last commercial search versus choosing based upon some selection algorithm from the last N searches (see previous point).
Will the reach-back cross a topic boundary or is it only to enhance context for an ambiguous search?
What effect will this have on the Google Keyword Tool that helps advertisers forecast demand and price for a keyword? The volume numbers must now be adjusted by the amount of time the impressions are shifted to alternate keywords.
How much will this starve the long-tail of searches? Depending on the aggressiveness of the selection then long-tail searches may suffer a decrease in volume for adwords.

Even the most modest change of merely using recent previous searches only 'about' the current search to augment the adwords auction query should have a dramatic effect on the auction process. By definition it expands the number of bidders for a particular query. It may also curtail the effectiveness of arbitrage done by some adwords buyers who buy ambiguous lower value keywords as proxies for high value ones due to user sessions with query reformulations. Why? It should have the effect of driving up prices for the penny keywords if they are sufficiently related to high value keywords.

It will be interesting to watch what happens. This is likely not a non-trivial change in the keyword market.

Posted via email from nealrichter's posterous

The GPL and scripting languages

2009-08-28T15:36:00.001-07:00

I was recently asked by an associate about how the GPL and LGPL impacts scripting languages. The short answer is that it's not clear.

My general take on the LGPL and scripting languages is that if one cut-and-pastes LGPL code A into code B, then code B falls under the LGPL. However if one script-includes code A into code B in the only real mechanism scripting languages allow then code B does not fall under the LGPL.

php: include 'Foo.php';
perl: require Foo::Bar;
python: import Foo
ruby: require "foo"
javascript: <script type="text/javascript" src="external.js"></script>

This differs from the application of the LGPL to compiled languages like C/C++ as the programmer decides how the machine code is combined: static versus dynamically linked. In Java if one has an LGPL jar file, the the code can be used in the standard way. If your code is combined with the contents of the LGPL jar file in a new jar, then your code falls into the LGPL.

What does the scripting language really do under the hood? It's different in each language. Some may physically include the file and parse-interpret it as one block of code, others may parse-interpret separately and resolve references between them much like a dynamic linker. Do the details matter? Unknown, yet one could reasonably assume the author of a piece of script code under the LGPL must have intended others to make script-include style uses OK. If in doubt check with the author and save that email.

What about the GPL? More clear.. no mixing of any kind can be done. One could argue that interpreted script is not linked in the way that compiled languages are... yet conservatively this is a "thin reed" to stand on.

What does this mean about the myriad of GPL javascript out there intermingling with non-GPL and proprietary javascript within browsers visiting script heavy websites everywhere? It's a dog's breakfast of legal issues.

The post Twenty questions about the GPL is pretty informative of the issues, worth a read... deeper than the above.

Posted via email from nealrichter's posterous

What can we learn from the Google File System?

2009-08-20T23:59:00.001-07:00

I found this via my twitter herd and I've been thinking about it for days. Kirk McKusick interviews Sean Quinlan about the Google File System. Fascinating stuff.

We're very fortunate to have storage scalability challenges ourselves at 'Undisclosed' (formerly OthersOnline). We're amassing mountains of modest chunks of information via a set of many many hundreds of millions of keys. We've evolved thusly:

MySQL table with single key and many values, one row per value.
MySQL key/value table with one value per key
memcachedb - memached backed by Berkeley DB
Nginx + Webdav system
Our own Sam Tingleff's valkyrie - Consistent Hashing + Tokyo Tyrant

#5 is the best performing, yet we still aren't going to escape the unpredictable I/O performance of EC2 disks. To my understanding this serves a role much like the chunk servers of GFS. We need low latency read access to storage on one side, and high throughput write access on the other side.

Combining the insights with the above interview and the excellent Pathologies of Big Data, I'm left with the impression that one must absolutely limit the number of disk seeks and do some 'perfect' number of I/O ops against of X MB chunks.

Random questions:
What is X for some random hardware in the cloud? How do we find it? What if X changes as the disk gets full? What kind of mapping function do we send the application key into to return a storage key to get the best amount of sequential disk access on write and best memory caching of chunks on read? What about fragmentation?

It does seem as though the newish adage is very true.. web 2.0 is mostly about exposing old-school unix commands and system calls over HTTP. I keep thinking this must have been solved a dozen times before. cycbuf feature of usenet servers?

Posted via email from nealrichter's posterous

Response to Dr Lance Fortnow's CACM opinion

2009-08-02T08:13:00.000-07:00

Dr. Lance Fortnow published a strong argument against the current 'strong conference' CS system in the August issue of CACM. His essential desire is that CS move to a system similar to the hard sciences and engineering. Conferences should accept any paper of reasonable quality, not publish proceedings and hold Journals as the sole vehicle for publications.

My Questions:

While CS should have a stronger Journal system, why should that come at the expense of quality conferences?

within

Is this problem really that acute in all communities? Can't it be solved at the community level?

conference

Why would industrial researchers and scientists participate in publications with such long time cycles?

Why do we want ANY such top-down forcing of CS organization?

Obviously the current system is serving a need, doesn't that speak for itself?

While Dr. Fortnow is correct on his points w.r.t. the problems faced by conference 'PC' committees... the correct response is best done within that community. Found some Journals and compete with the conferences for publications and reputation. I don't accept that a strong Journal system can only be created by first wiping away a very fluid and successful conference system.

My personal solution to strengthening the Journal system? I'll set a goal of submitting a Journal publication or two in the next year. I am completely remiss in not yet submitting anything to a Journal.

As a counter point to the above arguments.. if I could have a wish it would be a Journal system with fast review times, immediate publication of accepted papers and that markets itself by cherry picking great papers from conferences and encouraging those authors to submit to the Journal. Something like the Journal of Machine Learning Research. The publishing of referee reviews also sounds interesting.

Hacking Apache's mod_proxy_http to enforce an SLA

2009-07-14T09:41:00.000-07:00

Following up on the last post about HTTP SLAs, let's say you have a web-service exposing ReST APIs for your awesome data miner/processor. It has data input/output APIs of various kinds. The software architecture consists of front-end apache servers and back-end tomcat plus various data stores. Apache's mod_proxy and some load balancer (HAProxy, mod_proxy_balancer) pushes the incoming requests to backend servers.

A client wants a guarantee that your APIs will accept requests and return valid data and response codes within XXms for 95% of requests (see Wikipedia's SLA for other examples of service guarantees). How can one be absolutely sure that the SLA is met? Now add in the wrinkle that there might be different SLAs for the various APIs. In addition, the SLA could specify that as close to 100% as possible of the requests return HTTP codes within the 2xx range.. suppressing any 3xx, 4xx or 5xx codes from coming back to the outside world.

The issues with making apache do this are as follows:

ProxyTimeout is global or scoped to the particular vhost
ErrorDocuments still return the error code (503, 404, etc)
No way to tie ErrorDocuments and ProxyTimeouts to particular requests.

A key insight from Ronald Park is to use mod_rewrite and then pass various environment arguments to mod_proxy that are specific to the URL being addressed by mod_rewrite. This was the approach taken by Ronald Park in his attempts to solve this problem in apache 2.0.x here and here.

The below example is a rewrite rule that makes no changes to the URL itself for a JS API presumably returning data in JSON.


RewriteRule ^/api/(.*).js\?*(.*)$ http://backendproxy/api/$1.js?$2 [P,QSA,E=proxy-timeout:900ms,E=error-suppress:true,E=error-headers:/errorapi.js.HTTP,E=error-document:/errorapi.js]

With the SLA enforcement modifications enabled, the URL will return data from the backend system within 900ms or a timeout occurs. At this point apache will stop waiting for the backend response and serve back the static files /errorapi.js.HTTP as HTTP headers and /errorapi.js as contents.


$cat /var/www/html/errorapi.js.HTTP
Status: 204
Content-type: application/javascript

$cat /var/www/html/errorapi.js
var xxx_api_data={data:[]}; /* ERR */

There are four environment variables the SLA hack looks for:

proxy-timeout: - time in seconds or milliseconds to wait until timing out
error-suppress: - true/false switch on suppressing all non 2xx errors from the backend.
error-headers: - file of syntax correct HTTP headers to return to the client
error-document: - file of content body to be returned to the client

Leaving off the proxy-timeout will only suppress errors from the backend after the global timeout occurs. Leaving off error-suppress:true will ensure that the 5xx timeout error from mod_proxy_http is returned intact to the client.

Source code here

There are two versions checked into github for Ubuntu 9.04's apache2 2.2.11 and Centos el5.2's httpd 2.2.3-11. It's advisable to diff the changes with the 'stock' file and likely re-do hack code in your version of apache 2.2. See Ron Park's code for 2.0.x and fold in the other mods supporting error-suppress etc.

The hack is being tested in a production environment, stay tuned. This will get posted to the apache-dev list..hopefully with responses suggesting improvements.

Update for 2011: This has handled billions of requests per month at this point and works great. No issues.

HTTP request with SLA

2009-07-03T10:18:00.000-07:00

Here's a (nonAI) problem I'd like to solve. Configure apache to receive a request and proxy/forward it off to a backend app server (tomcat) .. wait a specified period of time ... if no response is received send back a static file or a return code like 204.

Essentially it's a combination between the below mod_rewrite and mod_alias directives with a timeout. Below example uses solr without loss of generality.


RedirectMatch 204 /search/(.*)$
RewriteRule ^/search/(.*)$ http://backend:8080/solr/$1 [P]

Logic below:


If url matches rewrite-rule regex then
{
        set timer for 500ms with timer_callback()
        force proxy to second url after rewriting it
        if(response from proxy is > 199 and < 300)
           return response
        else
           return 204 or static default file
}

timer_callback()
{
       return 204 or static default file
}

Instead of returning 204 one could also serve back a static file like /noresults.xml

The general idea is to expose a url that has a near-guaranteed response time limit (assuming apache is alive) where a 204 or a static default is acceptable behaviour. I suspect that we'll need to write an apache module to do this, yet surely this question has been asked and solved before!

Copyright, Licenses and First Sale doctrine

2009-03-07T16:12:00.000-08:00

Very interesting 'Legally Speaking' article in the March 2009 CACM, When is a "license" really a sale? by Pamela Samuelson. She covers the principle of 'first sale' and the recent decisions on the UMG v. Augusto and Vernor v. Autodesk. Essentially both Augusto and Vernor were selling used CDs and Software on eBay and the copyright owners of the products went after them for these sales. Both parties are using the first-sale doctrine to defend their rights to sell the media. The copyright owners are trying to use contract law and the licenses to restrict transfer of the physical media and right to use it. Samuelson predicts that both will end up on the 9th Circuit appeals court.

I hesitate to issue an opinion here, I see both sides. More debate here, here and here. A nice little post on first sale here. From the perspective of books and music, I side with the first sale doctrine.. and mostly think the 'one click' license notices as having many problematic issues. If you receive a physical copy of something for $$ or as a gift, you should be allowed to resell it at your whim.

It's worth hunting down the previous articles in this series.. they stretch back many years.

In memoriam - Prof. Dr. Ingo Wegener, 1950-2008

2009-03-05T22:36:00.000-08:00

Ingo Wegener passed away last November, see his obituary here: Nachruf/Obituary. He taught at University of Dortmund/TU Dortmund and ran a group of Evolutionary Algorithm researchers looking into the basic theory and run-time analysis of EAs. His papers and the basic approach of his 'school' have been very influential in my PhD research and he was quite encouraging of my proposed ideas. If at the end of our lives we are professionally remembered half as fondly as he will be then that is success.

Predicting search engine switching behavior

2009-02-22T21:48:00.001-08:00

Following up on the previous post, I found a few interesting papers (via Google) on user switching behavior of search engines.

An Analysis of Search Engine Switching Behavior Using Click Streams
Juan & Chang of Yahoo Inc
Making Sense of Search Result Pages by Pedersen of Yahoo
Defection detection: predicting search engine switching
Heath & White of Microsoft
Enhancing web search by promoting multiple search engine use
White, Heath and co-workers at Microsoft
Stream Prediction Using A Generative Model Based On. Frequent Episodes In Event Sequences by Laxman, Tankasali and White of Microsoft

Definitely worth reading in detail as the ways of building the models might be applicable to other behaviorally driven events.

Can we measure Google's monopoly like PageRank is measured?

2009-02-22T16:32:00.000-08:00

Jeremy Pickens posted an interesting note on his IR new blog:

Is it really true that Google is competing on a click-by-click basis? In the user studies that Google does, which of the following happens more often when the user types in a query to Google, and sees that Google has not succeeded in producing the information that they sought (fails):
Does the user reformulate his or her query, and click “Search Google” again (one click)? Or,
Does the user leave Google (one click), and try his or her query on Yahoo or Ask or MSN (second click), instead?

His points about actions 1 versus 2 are very astute. I’d guess that #2 happens a LOT on the # 2-10 search engines. Meaning people give that engine a try.. maybe attempt a reformulation.. then abandon that engine and try on Google. And I’m betting that people ‘abandon’ Google at a far less rate than other engines.. ie asymmetry of abandonment.

I’d love to do the following analysis given a browser log of search behavior:

Form a graph where the major search engines are nodes in the graph

For each pair of searches found in the log at time t and time t+1 for a given user, increment the counter on the edge SearchEngine(t) -> SearchEngine(t+1). Once the entire log is processed normalize the weights on all edges leaving a particular node.

We now have a markov chain of engine usage behavior. The directional edges in the graph represent probability of use transference to another engine, self-loops are the probability of sticking with the current engine.

If we calculate the stationary distribution of the adjacency matrix of probabilities, we should have a probability distribution that closely matches the market shares of the major engines. (FYI - this is what PageRank version 1.0 is - the stationary distribution of the link graph of the entire web)

What else can we do? We can analyze it like it’s a random walk and calculate the expected # of searches until a given user of any internet search engine will end up using Google. If the probabilities on the graph are highly asymmetric.. which I think they are.. this is a measure of the monopolistic power of people’s Google habit.

This should also predict the lifetime of a given ‘new’ MSN Live or Ask.com user.. meaning the number of searches they do before abandoning it for some other engine.

Predicted End Result: Google is the near-absorbing state of the graph.. meaning that all other engines are transient states on the route to Google sucking up market share. Of course this is patently obvious unless one of the bigs changes the game.

Scalable Analytics - random notes

2009-02-21T21:37:00.000-08:00

As long as I'm posting about 'rethinking' any reliance on an RDBMS for 'big data' systems, here are a few more notes:

This post on highscalability.com about Rackspace and MapReduce is highly enlightening. The post takes you through a failed use of MySQL for large scale analytics and their conversion to Hadoop.

I can't say I know (yet) the pros and cons of putting structured bigdata on a 'column store DB' versus Hadoop+HDFS. Will probably end up using both systems in various ways. Currently exploiting Sam Tingleff's DGrid and poking at LucidDB for "row filtering and aggregation" style analytics apps.

Looking forward to setting up Hive and Pig next.

On the plus side for MySQL, the federated engine has been quite useful for accumulating data from a sharded/partitioned MySQL setup.. as long as the data being accumulated is less than 100K rows, then it seems to hit a wall. It's also quite brittle if your MySQL instances are having any performance issues.. failed connection can cause other ETLs that depend on that connection to fail in odd ways.

Scalable data storage for model learning

2009-02-20T15:38:00.000-08:00

I'll admit it, sometimes as an AI & Data wonk you want all your data structured and easily accessible via slicing a dicing, thus SQL databases and relational schemas look like a great idea. And it works for a while... until you're dealing with a torrent of incoming data.

This should not be unfamiliar, the UC-Irvine datasets look like a great place to cut your teeth with Machine Learning .. until you realize that many algorithms and software packages written and litmus tested against such data totally fall down on 'big data'.

This quote from Dave Cancel on Twitter stuck with me: "Databases are the training wheels of software development. Fly free brother, fly free. - University of Sed, Grep, & Awk". My first reaction was, meh.. databases are meant for storing lots of data. I love and use tools like those for prototyping.. but then moved to compiled code + SQL for 'production'.

Mental sea change! Let's say you are building a massive scale system for absorbing click data, processing it and turning it into a recommender system. These are the problems you will see using MySQL at scale. Hint: it tips over at 1K read/write operations per second against the same table.

Don't try and make your read store also your write store. You may not /really/ need a low latency (for model updates) system.

More tips from Dave:

As for storage of [models], I suggest storing them in text file (format up to you), 1 per profile, then stick them behind a reverse caching proxy like Varnish. Infinite scale. For extra points store the text files on S3 and use the built-in webserver to serve them to your reverse proxy. HTTP is your friend as is REST SOAs.

Here's another dead simple storage mechanism:
http://etherpad.com/9JrpcyvXyK

"simple DB" projects like Voldemort and Tokyo Cabinet and MemcacheDB are options as well.

If you can't depend on a room full of DBAs making your SQL DBs not be dog slow, (or buying $$$ systems from Oracle and Microsoft) you must think differently. Pull yourself out of the Math and AI thinking and simplyify. Big Data will eat you alive otherwise.

TunkRank Scoring Improvement

2009-02-18T21:27:00.000-08:00

Recently Daniel Tunkelang blogged about an influence rank for Twitter. Jason Adams took up the implementation challenge and coined it TunkRank.

After some poking at it, I'm suggesting a scoring improvement. At the moment the primary rank is percetile in the UI, however the raw score is given as well. I checked a few users and put together the table below, and it feels wrong. It saturates @ 100 too quickly and there is not enough differentiation between people with healthy versus massive influence.

Why 'feel'? Human interpretable numbers need a tactile sense to them in my opinion. One critique of the metric system is that the English system just feels more human compatible, an inch is not too small, a foot is reasonable, a mile is a long way and 100 miles per hour is darn fast.

I'm proposing two new scoring possibilities. Both are based upon logarithms and span from 1-100. The slight difference between them is how 'linear' the resulting rank feels across the accounts I compared.

LEAST(100,ROUND(POWER(LN( tunkrank-raw-score +1);1.82)))

LEAST(100,ROUND(LN( tunkrank-raw-score+1)/LN(3.5) * 10))

What are the constants? They are magic numbers to map Barak Obama to a TunkRank of 100 as well as provide an interesting spread between the test accounts below. Comments welcome! Which is my choice? I can't decide.. #1 is smells more accurate, #2 tastes more natural.

Yes this is an inexact science.

Possible Tunkrank Bug? Check out dewitt's rank.. looks off given his number of followers and that he's an influential guy from Google.


NAME       PERCENTILE RAW SCORE  NEW SCORE #1 NEW SCORE #2
BarackObama        100     277770        100        100
wilw               100      79118         82         90
guykawasaki        100      62543         79         88
JasonCalaca        100      59075         78         88
THErealDVOR        100      43207         74         85
anamariecox        100      38177         73         84
WilliamShat        100      13932         61         76
fredwilson         100      13340         60         76
abdur              100       1351         36         58
johnhcook           99        407         26         48
johndcook           94         61         13         33
gutelius            84         20          8         24
nealrichter         81         16          7         23
ealdent             80         16          7         23
dtunkelang          79         15          6         22
dewitt               1          2          1          9

response to Noisy Channel post on Lucid Imagination

2009-01-27T07:22:00.000-08:00

Cross posted to my blog since it's a long response ;-)

To: Daniel Tunkelang

RE: Noisy Channel blog post on Lucid Imagination

I don’t think it’s their aim to compete with Enterprise search directly (business suicide), though I suspect they might pressure the pricing in the mid-market of search. The small market has been mostly eliminated by Google/Yahoo/MSN site search and open source engines.

Note also that they do not seem to (yet) provide support for Nutch or Droids.. meaning that they are missing a spidering/crawling engine. Same with Tika (office document support). Search result clustering may be coming soon via SOLR-769. No content-management or versioning. (These are fixable pieces given all the open source out there)

There is no good native support for rich taxonomies in Solr/Lucene, nor is there native support for some of the interesting semantic-web data driven features. No self-learning or auto-personalization of results. No analytics (though one could go elsewhere for that).

Lucid is also not offering a hosted Solr service .. so they are not an SaaS play either.

All that said, they obviously have some huge wins within the software industry.. but it’s a tough road to go after accounts like Home Depot, Albertson’s, or the government entities.

Enterprise search is mostly about finished feature sets and a near full admin GUI for non-programmers. The question is in these lean economic times if a given customer considering “build versus buy” is willing to risk starting a professional services engagement to build what they want for cheap, versus purchase a commercial ES product with way more features than they think they need.

I do think that a smart customer will have new leverage during the sales cycle to credibly threaten the ‘build’ option and get the ‘buy’ price down. And Lucid certainly should affect the ability of the ES companies from getting a customer bought in then milking them for professional services, integration and customization fees… Lucid provides a credible switching threat to cut bait and start over.

Google, Yahoo and open source projects like Lucene have commoditized basic search, so ES is about value-added features, innovative R&D and taking away customer pain and complexity.

Some of the people in Lucid have big plans (Grant Ingersoll comes to mind), and there is absolutely no question that Lucene has made some search vendors look like dinosaurs with slow engines and archaic index structures.

It will be some time before open source catches up to ES.. but it just might not be as long as some would hope.

Disclaimer: The above is my opinion and some fact-looking statements might be wrong.. so Lucene guys jump in!

Lucid Imagination and Sematex

2009-01-26T14:28:00.000-08:00

Kudos to the Solr/Lucene gang for launching Lucid Imagination. Grant Ingersoll's announcement. People involved here and here. Some time ago Otis Gospodnetić launched Semtext. Good luck to Lucid and Sematext!

Both of these companies are in the 'support and consulting' model. This is wise, as going into Enterprise search directly is a tough road competing with Endeca, Verity(Autonomy), FAST(Microsoft), GoogleBox and the other vendors would be suicidal.

Aside:
Long ago (2003) I thought of hanging up a shingle for supporting HtDig (a once popular CGI based search engine), but wisely decided that would be a mistake given that even then I could see that Doug Cutting's Java Lucene and Nutch were going to smoke the creaky 8+ year old C++ indexing kernel. Ended up getting RightNow Tech to sponsor conversion of the guts to CLucene, where it still runs today indexing many many tens of millions of documents. Then Solr was announced .... and HtDig development died and I started using Solr.

Just touched base with Geoff Hutchinson the other day and we're going to release the 4.0 CLucene branch of HtDig, and put up an announcement of HtDig end-of-life and encourage people to migrate to Solr.

Text Classification with Solr

2009-01-26T09:32:00.000-08:00

Starting to look at using Solr/Lucene for text mining. Between OpenNLP, the Python Natural Language Toolkit and various other projects it's time to toss my ad-hoc mishmash of tools and start over.

Looks like Grant Ingersoll is working on similar things in his Taming Text project. This is a nice beginner's overview of the area as Grant sees it, Search and Text Analysis PPT. Also looks like others are scheming about blending Mahout and Solr in some future version.

The basic idea is to take an ontology/taxonomy like Dmoz or FreeBase of {label: "X", tags: "a,b,c,d,e"}, index it and then classify documents into the taxonomy by pushing parsed document into the Solr search API. Why? Lucene/Solr's ability to do weighted term boosting at both search and index time has lots of obvious uses here.

Now that my readership (by data-mining and semantic-web geeks) is up slightly (ie above zero!) due to Twitter traffic, I'm hoping people contact me with ideas, code, etc. Heh.

Initial ideas:

Use More-Like-This code to 'pass in' a term vector without storing it
Write Solr plugin to execute search and post-process hits and do any outgoing classification and biasing math.

Once this is proven out, then the obvious next step is to figure out how to index the various RDF/OWL datasets out there. Much of these parts has probably?? been done before, I just need to find them, examine their merits and do some LEGO style layering to get a prototype up.

New Year's Resolutions and Goals

2009-01-02T10:01:00.000-08:00

Here are this year's technical/career goals & resolutions. Most of these are general and many encompass specific current and forward looking work projects. Others are just motivational resolutions.

Goals and Resolutions:

Turn in Dissertation. It's 75% complete and the rest is all typewriter work. Be done.
Be a better Numerati. The point of modeling is to predict... so this goal is a lifelong career goal with a new label.
Practice at Done and Get Things Smart and Teach Yourself Programming in Ten Years
Make damn sure that OthersOnline.com doesn't have any Fail Whale events (technical or business).
Read more tech (academic, business and research blogs) - Seed and water the creative juices.
Economy willing, hire a full-time minion.
See if I can practice some 'startup karma' (hat tip Todd Sawicki) for other startups.

Specific items:

Suck down more 'computational advertising' research and write some myself.
Cherry pick new Semantic techniques from the rat's nets of the Semantic Web.
NLP and Extraction
Sharpen skills from classic modeling/filtering/sampling methods.
Column DBs
Modern Map-Reduce
More Scalability
Data mining from VLDB
Contribute to open source projects again
File patent(s) and publish a paper(s)
Clean the Garage

Thank heavens I have all year. This is really a post that should evolve all year.. why can't some blog posts be Wiki-like and not so time ordered? I reserve the right to violate blog-etiquette laws and edit this post.

Statutory Inventions and the Public Domain

2008-12-28T19:26:00.000-08:00

This is interesting: USPTO Statutory Invention Registration

Basically it's a way of publishing an invention to the public via the USPTO. Rarely used for obvious reasons.

Question #1: Why don't open source people apply for these USPTO invention declarations? It seems to be the patent law equivalent of a BSD/MIT license.. ie "use/extend it for any purpose but it's still my work and you can't claim it as your own work."

The more interesting tidbit on there is, while obvious, a potential source of great technical material. Since 1999 when you file a patent it is published 18 months after the file date. Once an application is abandoned the application and is published by the USPTO and it becomes public domain.

Question #2: Are rejected patents whose appeals have run out then public domain? I can't seem to find a clear answer.

How many rejected/abandoned software patents etc out there from Microsoft, Oracle, IBM, etc are there that contain very valuable algorithms and techniques that are now public domain? Yes this is a bit like looking for gold in the trash can...

Notes:

The European Patent Office by treaty publishes many USPTO patent apps.. and honestly has a better interface for getting the status of your patent than I have yet found at the USPTO.

The Patent Reform Act of 2005 (Republican sponsored) was an attempt to close the publication 'loophole'. The Patent Reform Act of 2007 (Democrat sponsored) keeps the current publication system in place. Neither is law (yet).

New Year's Resolutions - Blog more

2008-12-27T20:39:00.000-08:00

New Years resolution - blog more. I've been very busy doing cool stuff at Others Online and in the process developed some tunnel vision to stay on task.

Here's to hoping that more blogging will cause me to see things in a different light more easily as well as get me more in 'writing mode' to finish the PhD before summer 2009.

Twittering has replaced blogging as my outlet for the second half of the year.. yet the 140 char format isn't much good for a personal musing and research blog.

Marshall Kirkpatrick and Data Mining

2008-12-27T20:30:00.000-08:00

[somehow this got lost in drafts in my blog - back in August]

Marshall KirkPatrick's RRW post Four Ad-Free Ways that Mined Data Can Make Money is interesting.

In approx 2002 I wrote version 1.0 of the RightNow Tech sentiment analysis software to analyze the positive versus negative overall tone of incoming support requests/emails in the CRM system. I called it 'Emotix', but the Marketing people renamed it SmartSense. Later Steve Durbin and I bolted on a POS tagger to get a bit more accuracy given language forms like 'I am not very happy' and 'I am very angry' require the modifiers be taken into account.

Basically Emotix was tasked to attach a numerical positive/negative emotional score to each incoming request.. such that the queue of requests could be ordered to service angry customers first. We weren't interesting in extreme accuracy.. just a decent ordering that was fairly predictive.

There were two interesting stories to version 1.0. The first concerned the negative/neutral/positive word dictionary. Basically my office mate and I sat down and compiled a list of every positive and negative word we could find and put them on a wide numerical scale. When it was time for swear words, we shut the door and howled in laughter as we threw mock insults around the room. The Wicked Words book was an invaluable source of inspiration.

When it came time to litmus test our word ratings we put co-workers in front of a terminal that would put random words from the list and ask them to agree to disagree with the rating. Needless to say we had to forewarn everyone that it WOULD be offensive and that this did not constitute any form of harassment. Watching the process was excruciating and hilarious.

The second humorous story concerned testing and training the system on real support messages. My favorite data set was from a well known customer that made specialty ice cream. Their customers tended to begin each service contact with a large block of text extolling the virtues of the company and its ice cream.. with the negative comments on their experience with the ice cream last... usually written in apologetic terms. Obviously the creamery wanted to get the custmers with real negative experience problems to the top of the queue.. ice cream is all about the eating experience. But how do you filter out and bias for the overall 'fan mail' tone of 90% of the requests? Fun stuff to work on. Some details here, others here.

Recently Steve extended it to work with both the RNT Voice product and the marketing-automation product as well. The big lesson here as an engineer is that good enough can be just fine and often it will be used in unexpected ways down the line. The largely un-refactored code is still running and processing billions of textual contacts every year. Ok this is exagerated a bit.. but it hasn't really been rewritten, just optimized frequently.

A story about Don Haskins and my father

2008-09-08T00:02:00.000-07:00

This is not about AI, but a personal story.

Don Haskins died yesterday at 78 years old. AP Obituary

I grew up for the first 14 years in El Paso, Texas before moving back to the family home in Montana. Don Haskins and UTEP basketball were a big deal. Coach Haskins is of course the guy who coached UTEP (then Texas Western College) to the 1966 NCAA championship with five black players... which was wonderfully rendered into the movie Glory Road. It's hard to overstate what an effect he had on El Paso and UTEP.

I've always been more of a fan of coaches than players, and Haskins was at the top of my biased list of basketball idols. Years ago my father and I finally met him at my grandmother's 70th birthday party. [Photo of me bringing in flowers he brought to the party] I'd read every book, and article about him but managed to mostly stutter upon meeting him. My dad gave me some crap about that.

When Glory Road opened on Friday the 13th 2006, the family went to see it. Great flick even with the inaccuracies. After the movie Dad asked me how I liked it, I said "It was great". He then said "A movie about your hero Don Haskins", I said "yep.. but oh Dad you are my hero". We both snorted and chuckled as grown men do about emotions. A few minutes later we parted ways with 'I love you' and hugs.

Dad died the next day and those were the last words we exchanged. I didn't watch Glory Road again till a couple months ago.. too much emotion. When I heard the news that Haskins died, time stopped a bit as I thought about him, my childhood idols and my father.

The stories about this man that circulated in El Paso and in the family were legendary. Here's an example, or two.

RIP Coach Haskins (and I still miss ya Dad!)

Open Source Search Engine Rodeo: Solr v. Sphinx v. MySQL-FT

2008-08-29T13:44:00.000-07:00

Last summer Anthony Arnone and I did a study on the performance of three open source search engines.

We chose these three as two of them have close ties to MySQL and the other is a well used and performant offering from Apache. There are many that we skipped.

Here's the Report in PDF.

Solr was the clear winner. Sphinx was in a close second with blindingly fast indexing times.

At this point the report's results are somewhat dated as both Sphinx and Solr are readying new releases. So your mileage may vary, and I'm sure Peter Zaitsev and the Sphinx team could show us how to improve the performance of their engine.

Updates: The Sphinx team contacted me and suggested some ways to improve Sphinx performance. New results will be published some time soon. They will likely also publish a test using Wikipedia as the document repository.

More Updates: I have started a new Solr project and may test Sphinx again.

Great comment on MapReduce

2008-08-12T21:58:00.000-07:00

Spot on comment from Iván de Prado on the Database People Hating on MapReduce blog post.

I think this document is comparing things that are not comparable. They are talking about MapReduce as if it were a distributed database. But that's completely wrong. Hadoop is a distributed computed platform, not a distributed database prepared for OLAP.

MapReduce is a re-implementation of LISP's map and reduce in a parallel setting. Now the function/task that you give to Map is where the rubber meets the road of reading data from some data store.

MapReduce versus RDBMS - Round 2

2008-08-12T20:32:00.000-07:00

Round 2 (for me anyway - this discussion has been raging for a while). Nice read on how Rackspace Now Uses MapReduce and Hadoop. They started with shell scripts, evolved to remote RPCs of shell scripts, moved to MySQL, interated on MySQL and then jumped to a heterogeneous Hadoop + Solr + HDFS. Terrabytes of data.

The MySQL evolution was interesting as I'm going through a similar process of attempting/planning to continually refine MySQL performance. We need UPDATE statements in a big way, so it's a bit different than appending to log structures.

I've been playing with a daily summarizing and distributed ETL with MySQL. Basically with creative use of Views and the Federated Engine one can do a scheduled daily map and reduce. I hold no hope that this is a solution for adhoc queries, it's not at all that flexible. Wiki page describing this system coming soon.

Still trying to find a solution other than a 'union view' across the federated tables from the n data partition servers as the Map. The Reduce will be a set of stored procedures against the union-view. Perhaps this post and hacked code holds promise for gluing Hadoop to JDBC/MySQL storage engines. This would better enable ad-hoc queries.

I also wonder if MySQL Proxy is useful here.. looking into it.. but at first glance it doesn't inherently pattern the distributed Map operation well.

Open question: If one could publish MySQL stores to a column oriented DB like MonetDB or LucidDB and then do Hadoop map-reduce operations then do I have what I want for ad-hoc queries?

MapReduce versus RDBMS

2008-08-11T14:02:00.000-07:00

I managed to stumble upon an interesting article while looking for a MySQL multi-database federated query tool.

David DeWitt and Michael Stonebraker write: MapReduce: A major step backwards.

They rightly point out that MapReduce is a 25 year old idea. Lisp has had this functionality for decades.. and it's actually at least 30 years old. Griss & Kessler 1978 is apparently the earliest description of a parallel Reduce function. That said, it's only in the last 10 years that an idea this great could have been implemented widely with the advent of cheap machines.

Their second point is that MapReduce is a poor implementation as it doesn't support or utilize indexes.

One could argue that value of MapReduce is automatically providing parallel execution on a grid of computers. This feature was explored by the DBMS research community in the 1980s, and multiple prototypes were built including Gamma [2,3], Bubba [4], and Grace [5]. Commercialization of these ideas occurred in the late 1980s with systems such as Teradata.

In summary to this first point, there have been high-performance, commercial, grid-oriented SQL engines (with schemas and indexing) for the past 20 years. MapReduce does not fare well when compared with such systems.

Great point and point taken. However, where are the open source implementations of the things you mention? This is a bit of the 'if a tree falls in the woods and no one is there to hear it' problem. A major reason MapReduce has seen uptake (other than being a child of Google) is that an example implementation is available for the Horde to steal, copy, improve & translate.

The modern user generated content web is mostly built on Open Source these days, so the fact that I can get the above technology in commercial databases is a non-starter.

I'm a SQL junkie and am searching in vain (it seems so far) for decent extension to MySQL that does cross-database query and reduction of tables I know to be neatly partitioned. No luck so far. Starting to look into other SQL engines as their maybe a ODBC wrapper for the federation layer. It's got to be mostly functional and EASY to adopt.. or you'll continue to have people spouting the MapReduce dogma.

Post scripts:

Nice summary of Dr. Stonebraker's accomplishments here
Funny link to comp.lang.lisp some newbies asking about if Lisp has Map Reduce.

Improving Software Release Management

2008-08-04T08:50:00.000-07:00

I just found this in my inbox, 7 Ways to Improve Your Software Release Management. It's an excellent overview of 'doing things differently'. Pretty similar to the change that I experienced at the last job... and something that Mike Dierken at the current job just seems to know instinctively.

I need to find some stuff on the best ways to do personal lightweight processes. I'd like to be more efficient in producing software... especially software that is based upon speculative ideas. So much of the time data mining and machine learning coding is subject to the vagaries of the data set you are working against and it's difficult to know ahead of time if a given algorithm will work well.. how much data cleaning needs to be done... etc.

How can you adapt lightweight processes and the things mentioned above for producing software that is not so cut and dried in what needs to be done? In those situations I tend to ping-pong between little process (seat of the pants coding) and too much (excessive research and design before coding start).

Post script: Had to add this:

Five Things Linus Torvalds Has Learned About Managing Software Projects

How not to launch software

2008-07-29T23:55:00.000-07:00

From cnet:

Cuil shows us how not to launch a search engine

Google challenger Cuil launched last night in blaze of glory. And it went down in a ball of flames. Immediately after launch, the criticism started to pile on: results were incomplete, weird, and missing.

The various articles on Cuil's failure revealed much about their architecture. Apparently they are categorizing a user query into a topic and shipping that out to topical servers. While this sort of 'topical partitioning' is interesting, it has zilch to do with relevance ranking... and suffers from a failure-point issue.. if that topic server goes down then queries against that topic will get junk results or zero results

Questions and points of discussion:

Is it really true that a data schema partition results in a better engine than Google? No, a better engine is made by better relevance. Perhaps this is what the PR/Marketing people focused on rather than relevance.
How do you simulate load post launch load when you have no idea how widely the free press will be distributed?
Free post launch press is invaluable to your buisiness.. squandering it might be a deathblow.
Why not launch more quietly in early adopter tech-press and then go try and get mainstream press when you have proven the system?
Trading on your status as ex-Googlers (and not early ones at that) seems VERY dubious. Stand on your own feet rather than someone else's.
The absolute hottest area of information retrieval research right now is using user click-streams to improve the relevance live and on-line (learning to rank), as well as personalize results. These are differentiating features (if they result in improved relevance).
Cuil keeps ZERO user history or assigns session/user-ids. This will make it very difficult to follow this trend.. unless they are using someone else's cookies to do the identification via analytics partner (no evidence of this).
The other hot area of IR research is using semantic analysis and NLP to break away from simple keyword based inverted indicies. Hakia still seems to be doing it better than Cuil... or at least will appear to as long as the topical partitions keep crashing under the load.
Risk analysis is a fantastic tool in organizing and prioritizing your work on new products.. it seems they missed that part before deciding to launch.

I feel bad for these guys, Anna Patterson et al. have done some great work in the past and I just hate to see good people stumble like this.

I still think they are wrong to go out as a consumer engine... Enterprise is a better play.. however if their leading market differentiator is a topical partitioning of back end servers.. then they aren't even considering this as individual Enterprise customers may not be big enough to need hundreds of servers to distribute the index like that.

Hindsight is always 20/20 and hope to hell I am not standing there redfaced as software I helped create fails upon high volume launch.

Dubious results from Cuil .. and the Majors

2008-07-27T23:17:00.000-07:00

I searched for 'evolution recombination mutation' on cuil.com

The first 2 times, I got a no results page. After a few variations and an hour or so, I tried again and got a nice result set. One really jumped out at me: 'What's Driving Evolution; Mutations or Genetic Recombination'. The problem is that it links to an intelligent design group disputing Evolution in general.

http://nwcreation.net/geneticrecombination.html

After trying the same search on Google, Yahoo, Live.com, Ask and Hakia.. that same page shows up in the top ten.

Really? This is authoritative and the best that modern world-class search can do? I was hoping from some kind of page summarizing epic battles between Ernst Mayr and Motoo Kimura.

While this is likely caused by both keyword matches via good SEO and the fact that this page is probably highly linked to... this is a semantic failure! Imagine if a query to the Holocaust had anti-Holocaust propaganda links appearing above genuine factual information!

At least Hakia and Yahoo put up a page refuting the author of the above link in the top 10 results. Google and the rest fail to do so.

Admittedly, not everyone believes in evolution.. and that is fine with me.. but I'm not sure that fact refutes the semantic/authoritative failure of the engines.

Anna Patterson's new company - cuil.com

2008-07-27T21:47:00.000-07:00

Just spotted a NYT article on a new search engine called cuil from Anna Patterson and Tom Costello. A while back I read Dr. Patterson's article "Why Writing a Search Engine is Hard". Nice quick read on the issues. I also stumbled upon several patents she wrote.

So the recent challengers of note are Ask.com, Powerset, Hakia, Wikia, Mahalo and now Cuil. I'm rooting for the algorithmic ones, not really sure how Wikia and Mahalo can scale to be non-niche engines.

While I hope Cuil is successful (I like to see Academics go out and build companies), I'm not sure that it's possible to beat Google at this point. It seems far more likely that Microsoft will just try and swallow Hakia and Cuil and attempt to brew something out of the parts.

I recommend reading Danny Sullivan's post on Cuil, he hit most of the obvious points.

My thoughts:

I still think building intelligence on top of an existing index/engine is the way to go and I'm not sure that bragging about your index size or your back end architecture is going to get you any meaningful marketshare.

Also, Enterprise Search is still far behind in NLP technology vis-a-vis the big 4 and the NLP startups. It's still 1999 there, enterprises are just now figuring out how to expose their vast document sets to an internal crawler and provide a UI that is not overly simplistic for savy users. They've tried the classic approaches of commodity engines and found them wanting. Link analysis doesn't help either as most of the these documents are not web documents with links. This just cries out for an approach like Vivisimo's clustering + Hakia's semantics + Delicious' user driven tagging.

Corporate searchers need a good advanced interface and results that can be grouped by things like time and originating department.... but not be forced to drown in overly similar hits. That is a market worth getting into with a $33M VC investment. The landscape is littered with vendors that over-promised during the sales cycle and Enterprise customers will switch products if it solves the problem better.

Look at the $500M acquisition of Verity by Autonomy in 2005. That's 5X more than Powerset (in 2005 dollars) and they actually had loads of paying customers.

I worry that going directly at Google with a consumer search engine is just so much tilting at windmills. Sometimes just selling a product to people willing to pay for it is easier.

Others Online news and welcome Rance and Vik!

2008-07-27T16:06:00.000-07:00

I've been busy in the last few weeks getting new products launched at Others Online. We've deployed a set of new 'Audience Affinity Analytics'. By adding a simple Javascript tag to your webpages, our software delivers free audience summary reports that detail at a keyword/phrase level what people are paying attention to on your site! Short video here.

We've also hired Rance Harmon (MS student at Montana State U) and Vik Jakkula (MS student at Washington State U) as interns for the summer. Rance will be working on general web and Java coding as well as testing frameworks. Vik will be working on some new data mining algorithms. Welcome guys!

Looking for an intern

2008-05-15T22:13:00.000-07:00

I'm looking for resumes for a possible internship this summer with a startup company I work for - Others Online

Min 20 hours per week, possibly 40 hours.

Job Description:

Assist with Java servlet, SQL and Ajax UI coding. Data mining and search engine work possible if background allows.
Potentially assisting with highly scalable system work using partitioned architecture migrating to Amazon EC2 & S3 system.

Required Skills (4+ out of 6)

Java/JSP proficiency
SQL knowledge (MySQL)
Ajax experience (YUI, Google Web Toolkit, or from scratch javascript)
Some Sys Admin skill in Linux
Perl, Ruby or Python scripting
Familiarity with VMWare, Tomcat/Resin & Apache

Preferred Skills

Data Mining, NLP or Search Engine experience/coursework
WordNet or other taxonomy experience

Text processing, clustering and classification
On-line model building
Ant System methods

Partitioned high-availability system knowledge

Design fundamentals of this type of architecture
Amazon EC2/S3 experience

Firefox browser extensions

If you've taken a data mining or AI course, there is a very real possibility of doing some interesting work this summer with a conference research paper a likely outcome.

If you want to assist with the high-availability partitioned architecture implementation and migration, you'll be learning cutting edge design patterns that I have yet to see in a textbook. The other software engineer (Mike Dierken) worked at Amazon for a few years implementing very scalable systems.

Splitting time between the above two work areas is possible and in fact likely. Either way you'll come out with some real world skills desirable in industry.

We're a startup trying to explode on the scene this summer and the outcome post-summer is unknown. It could turn into a full-time salary job or continued part-time work in the fall.

A Subtle Art

2008-05-08T08:48:00.000-07:00

I loved this quote from a NYT Blog post:

"By attracting a commanding share of the search advertising activity, Google also has the best data with which to create equations that maximize the money it makes from each search. It turns out that picking which ad to display when is a subtle art that can have a great effect."

I've been working on effectively harvesting and choosing keywords to best power and adnetworks like Google/Yahoo/MSN. I believe it's much harder than simply producing good search results. Search results are targeted at people explicitly looking for information, so in that sense it's like an auto-generated yellowpages entry, people want to click on something. The adverts on these pages benefit from the explicit nature of the search.

How do you do the same for display advertising on the rest of the non-SERP pages of the web? You get one shot at providing value, a bit like trying to hit the green from the rough and through a stand of trees. A subtle art indeed, and great fun to work on.

AI Luminaries and their claims

2008-04-24T23:31:00.000-07:00

This is a bit of a rant. In our weekly AI colloquium we have covered two high profile AI people, Dr. Robert Hecht-Nielsen and his Confabulation theory and Jeff Hawkins and his book On Intelligence plus his ideas around Hierarchical Temporal Memory.

Neither of the two above people are terribly famous in AI academic circles per se, but they do get some press. They are both founders of very successful business in HNC (Now FairIssac) and Palm/PalmPilot. Particularly in the case of HNC's use of AI for fraud detection in financial transactions, I am very impressed. Yet this is where it gets ugly.

If you read Hawkin's book or listen to a Youtube lecture of Dr. Hecht-Nielsen you would think these guys have invented the next great AI of the 'I have modeled the brain' variety. They both demonstrate very interesting neural network inspired architectures and basic computation. They are both complete with deep layering, feedback loops and other structures that NN people have known will work for years.

Yet both of them will just repeat similar claims that this is how the brain actually works and with this architecture real cognition is possible, even potentially trivial? Hogwash. Batshit Insanity.

These aren't my words, they were used to describe Stephen Wolfram's work on Cellular Automata and his claims that his flavor of CAs can build anything and describe all physics. He makes lots of strong claims against a theory he spend decades toiling on nearly alone.

Would Peter Norvig ever make these types of claims? I tend to think no way.

First, how can you make the claim that this architecture is really how the brain works and as such will lead to cognition or reasoning? To me that is what they are.. architectures of computation.

Where are the programs? Where is the embedded/encoded/learned method that can actually reason in some logical or nearly logical fashion? Ie chaining facts together to create derived knowledge? Picking apart disparate background statements/data to answer queries for information? How does this architecture answer the question of what are necessary and sufficient conditions to produce computerized general reasoning?

It's a massive leap of faith for me to take for granted that a neural architecture, with all it's bells and whistles, will just lead to reasoning. Doesn't it take just one counter-example of something that such an architecture and associated learning methods can not learn correctly to break the bold claims?

To me that is a central lesson of genetic algorithm theory, people for years went around insisting that the GA was a better optimizer (mousetrap) than all that had come before. They invented theories to describe it's behavior and made bold claims. Yet Wolpert and Macready come along and show the No Free Lunch theorems. It basically blew many of the bolder claims of GA superiority to hell. It has now spread into general Machine Learning as well.

I think people, particularly ones in AI with monster egos, need to exercise some humility and not make such strong claims. Didn't that type of behavior contribute to the AI Winter?

Every time I hear or read these types of claims my mind sees an image of Tom Hanks in Cast Away dancing around his fire and saying "Yes! Look what I have created! I have made fire!! I... have made fire!". The horrible irony of the scene is that he remains fundamentally lost, couldn't find his island on a map and is no closer to finding home as a result of making his fire.

Series of Economist Stories on Digital Nomads

2008-04-20T23:08:00.000-07:00

During a flight to Silicon Valley last week for AdTech I read a special report in the Economist on Digital Nomads. The intro article sets the tone and talks about how the mobility of cellular devices are obviously quickly changing the world. I love the description of early digital nomads as more akin to astronauts who must carry everything with them (cables, disks, dongles etc).

My comments:
I do tend to carry a good inch of paper everywhere I go, 90% of which are CS/AI research papers or dissertation notes to work on as I have the time. Opening the notebook is way to0 much of a hassle as a mobile reading device (on an airplane). He also states that engineers at Google tend to carry only a smart phone of some kind and no laptop when traveling. Is this true? I find this a bit hard to believe unless they are managers and not active coders.. I can't imagine writing code on a blackberry or worse and iPhone.
I'll admit I have no smart phone and do carry a laptop everywhere. I'd like it to be smaller, but not at the cost of horsepower or decent display size. I tried using a Microsoft powered Samsung smart phone and hated it, what it gave me in increased cool functions I sacrificed in phone function.

The next article in the series discusses the new found benefits and costs of our ability to work everywhere and anywhere.

My comments:
My laptop is definitely a desktop replacement for me, I want mobility.. but I am old fashioned enough to want a regular desk to work at.. even if that is my current count of three different ones at different times of the week. I have tried the coffee shop thing.. it works to a point but I find myself only being efficient for the first 2-3 hours then it goes to hell as I start hearing and being distracted by the conversations around me. I suppose it would be fine if I needed to do mostly emailing and short attention span coding. I also think that most business conversations are sensitive enough that talking in a public space is not acceptable in my mind... nothing to hide, yet why broadcast every mundane and not so mundane detail to the people around you?
The parts about culture clashes from old cubical work and new mobile work are spot on. It points to the need to trust every employee and set a tone that what matters is production and not the act of working.

The third article in the series explores the need for new types of spaces and architecture for this new way of working.

My comments:
I loved this one, even if it assumes that I 100% embrace the nomad ethos. Perhaps if I had such a space to work, and people to work with in that space I'd abandon some of my older ways. The closest thing I can imagine these 'third places' being is a combination of a student-union building and a college library. Very non uniform places with nooks and crannies for every type of 'work'. The Bozeman paper just had an article on a new business for 'on demand offices' and I saw two others described in a Seattle tech magazine at the airport. Winning idea.. 50% of the reason I go to campus two days a week is for socialization.

Great quote:
These places are "physically inhabited buy psychologically evacuated" ... leaving people feeing "more isolated that if the cafe where merely empty".

Great food for thought in the articles. I do notice that in my travels I see one thing that disturbs me. It is some people's inability to ignore their cell phone or crackberry when the are engaged in a face to face conversation or meeting. I was very appreciative of one executive's recent demonstration of 100% ignoring his device when it rang or vibrated.. he didn't even flinch. This was the exception to the rule over the past week.

I need to let this brew more.. at some point I am sure it will spur some good ideas. Perhaps there is an algorithm or platform waiting to be discovered that will spur us to look up from our devices and engage each other again. I suspect a big part of our addiction to them is that it's a much more high bandwidth information pipe that simple conversations are.

Using human relevance judgements in search and advertising

2008-04-18T12:05:00.000-07:00

This is old news on a couple of dimensions. Read Write Web had a post on how Google uses human relevance studies to help judge/QA their search results. This resulted from an interview that Peter Norvig gave to MIT Technology Review and caused some commenting in the blogosphere (NewYorkTimes Tech Blog, Goolge Blogoscoped). Old news on old news.

We now know that both Yahoo and Microsoft are using (to some degree) human studies to evaluate computational advertising algorithms (see this and this). Evaluating the correlation of what informational item an algorithm predicts, vs what humans think, is relevant to a context is the performance metric of your algorithm.

Question: When will TREC have a computational advertising contest?

Text Summarization and Advertising

2008-04-17T15:57:00.000-07:00

Recently read another CompAdvert paper (CIKM'07) from the Yahoo group, Just-in-Time Contextual Advertising. They describe a system where the current page is scraped on-line via a javascript tag, summarized and then that summary is passed to servers to match with Ad listings. Interesting points are:

5% of page text carefully chosen can yield 97+% of full-text advert matching relevance
Best parts of the document are URL, referring URL, title, Meta and headings.
Adding in a classification against a topical taxonomy adds to the accuracy of the ad matches.
They judged the ad matching relevance against human judgments of ad to page relevance.

I found these papers within the last few months as OthersOnline focused on behavioral based advertising. In many ways their finding are interesting, affirming and unsurprising. Interesting in that they are pushing the state of the art in advert matching, and affirming in that we @ OO are on the right track. Unsurprising in that using the document-fields about is the classic approach to indexing webpages and documents.
Of course internet search engines used this for years (it defines the SEO industry's eco-system), and the old/retired open source engine HtDig has had special treatment of those fields since the late 90s. The difference now is the direction, the documents are the "query" and the hits are the ads. Best part about the method is that it's cheap... javascript + the browser becomes your distributed spider and summarizer of the web.
I do love finding these papers.. we just don't have the time or resources to have a study like this and confirm the approach with a paid human factors study. Just go forward on gut educated feel day to day and the human measure is if we get clicks on the ads.
This approach is similar to the one we outlined and implemented before finding this paper. The difference is what we do with the resulting "query", using the signal to learn a predictive interest model of users.
Still no mention of any relative treatment of words within the same field... one would assume this would move the needle on relevance as well.
I still believe that this type of summarization approach can be used to make an implicit page tagger and social recommender like del.icio.us ... if you can filter the summary based upon some knowledge of the users real (as opposed to statistical) interests. Key route to auto-personalization of the web.

Itemset mining in data streams

2008-04-04T07:24:00.000-07:00

We covered a nice paper by de Graaf et al of Leiden University in the AI colloquium. Clustering Co-occurrences of Maximal Frequent Patterns in Streams. It deals with the problem of finding frequent itemsets in a datastream. Ideally you want an incremental algorithm for this with an 'updatable model' rather than being forced to reprocess the entire data/transaction sequence when adding new data. The paper's approach has the extra benefit that the itemsets are clustered by similarity as well. I really enjoy using and learning about algorithms that have nice side-effects.

A rough overview of the algorithm is that it does three basic operations with incoming data. First it builds a support model of patterns encountered. It does this with a with a reinforcement and decay technique, reinforcing support for patterns encountered in the current transaction and decaying those that don't. Second it maintains a geometric organization of itemsets according to a distance metric in a boxed 2-D area. As new data is processed itemsets' coordinates in the (x,y) box move and shift around according to their similarity with other patterns. Third it performs a pattern merging/splitting mechanism to derive new patterns for the model to track. new patterns get a random (x,y) position.

At the termination of processing some amount of data, you are left with a list of itemsets and their support/frequency as well as a nice grouping by similarity.

One advantage of his presentation is that it is stripped of all excess complexity. They well note that it learns an approximation of what you would get from a full-data-scan of a traditional itemset miner. Fine with me.. I don't get hung up on exactness and have lots of faith that incremental model building works well in practice.

The minor flaw of the paper is that they fail to point out (or notice??) that what they have built is a hybrid of a Swarm Intelligence and a Self Organizing Map. The Swarm/Ant portion comes from the reinforcement & decay of the support model, and the SOM from the geometric clustering of the itemsets. On could duplicate this algorithm in spirit by implementing Ant System + SOM with the merging/splitting for new pattern production. By 'Ant System' here I refer to the spirit of an ant system where you use pheromone reinforcement and decay of a model, actual ants traversing a path in a graph are not necessary. The cells in the SOM would contain a sparse vector of itemsets and apply the standard rules for updating.

Yet, even as I see the connection, this is a pointy-headed comment. The paper is nice in that the algorithm is presented without flourish in a straight forward way... sometimes using the word 'hybrid' and casting your work that way is just a form of academic buzzword bingo.

I'll definitively look to implement something similar to this ASAP. I may skip the merging/splitting and use a standard itemset miner offline over the 'last X transactions' and form a itemset pattern dictionary. Only itemsets in the dictionary will be tracked and clustered with the data stream, and every so often run the offline algorithm to learn new patterns and support to merge into the dictionary.

OpenOffice and LaTeX

2008-03-30T22:31:00.000-07:00

I am stunned. I am working on the dissertation and need to make a LaTeX monograph out of some publications. The biggest pain is that I had written two of the papers in MS Word, and previous experience cut-and-pasting from Word to a text file was horrible. I also no longer have MS Word installed on my new machine (didn't come pre-installed from Dell), so I have been using OpenOffice. So how do I get from Word to LaTeX when I only have OO?

More as procrastination I did a search and found Writer2LaTeX. Some saint named Henrik Just created this to convert OO docs (either swx or odf format) to LaTeX. Looks like he has been working on it for a while with a set of faithful followers submitting feature requests. Between OO 2.4 being able to flawlessly open the MS Word docs and save to ODF plus Writer2LaTeX, I probably saved myself 2 days of irritating work.

It's not perfect as I need to convert some equations images to proper LaTeX, yet the mind-numbing job of cut and paste is rendered unnecessary.

Thanks Henrik and the rest of the OpenOffice team!

Postscript:
While not open source, TeXaide from Design Science is a very nice free LaTeX equation editor. Write your equation, the highlight and copy it... then it pastes magically as text markup into your LaTeX code. Now if only I could just drag and drop an image on it and have it convert the equation in the image.

Semantic Features for Contextual Advertising

2008-03-28T10:49:00.000-07:00

Andrei Broder's group at Yahoo! Research has a focus on Computational Advertising. At SIGIR 2007 they released a paper on using Semantic Taxonomy to do contextual matching for advertising. This is a similar problem to the previous post about MS Research, deriving lists of keywords from a document to use as queries to an advertising system. Unlike the MS Research paper, Yahoo has built a large taxonomy of "commercial interest queries" with 6000 nodes and approx 100 items attached to each node.

The essential approach is to classify a document into the taxonomy as well as all of the ads and match ads to documents on the basis of topical distance. The distance score is combined with a more standard IR type approach forming a combined score. The top-k matching ads ordered by lowest distance are the ads displayed the page.

The TaxScore() function is fairly interesting, it attempts to generalize the given term within the taxonomy. It seems that this type of approach could work well with using WordNet's Hypernyms in a more regular IR/Search setting.

I have to read it again more carefully to see if I missed it, however I did not see anywhere in the formulas using any weighting of a keyword's bid value (or advert count). Maybe this was omitted for trade secrecy?? .. it seems obvious that it should be used to some degree to maximize $$ yield or eCPM of clicked ads. The idea is not to let it affect the matching of the ads to keywords, just the final rank order to some degree.

In my own experiments @ OO, using some proxy for bid value seems to increase eCPM. The biggest challenge is getting comprehensive data for your dictionary if you are not Google, Yahoo or MS.

Postscript:
I have it confirmed from two independent sources (current and ex Y!ers) that Yahoo is working in a new Content Match codebase as the old version didn't work. Hard to say what status Broder's above technique is in (production usage or internal testing).. or if it was part of the old system?

Scraping Documents for Advertising Keywords

2008-03-28T09:41:00.000-07:00

Lately I've been working on extracting keywords from text that would be associated with good keyword advertising performance. This is fairly related to the 'text summarization' problem, yet that usually works towards a goal of readable summaries of documents. This is a simpler problem as I don't want to build readable summaries.

'Finding Advertising Keywords on Web Pages' from MS Research (Yih, Goodman, and Carvalho) was interesting reading. To boil it down to its essence, the authors used a collection of standard text indexing and NLP techniques and datasets to derive 'features' from the documents, then used a feature-selection method to decide what features were best in deciding good advertising keywords in a document. They judged the algorithms against a human generated set of advertising keywords associated with a group of web pages. Their 'annotators' read the documents then chose prominent words from the document to use as viable keyword advertising inputs.

Note that this is not an attempt to do topic classification, where you could produce a keyword describing a document that did not exist in the document.. for example labeling a news article about the Dallas Cowboys with 'sports' or 'event tickets' if those labels did not exist in the article.

Interestingly the algorithm learned that the most important features predicting a word's advertising viability was the query frequency in MSN Live Search (a dead obvious conclusion now supported by experiments), and the TF-IDF metric. Other features like capitalization, link text, phrase & sentence length and title/headings words were not as valuable alone.. yet (unsurprisingly) the best system used nearly all features. The shocker was that the part-of-speech information was best left unused.

I emailed the lead author and learned that the MS lawyers killed the idea of releasing the list of labeled URLs.

Post Script: The second author is Joshua Goodman, who had a hilarious exchange with some authors from La Sapienza University in Rome. They wrote a 2002 Physical Review Letters paper on using gzip for analyzing the similarity of human languages. Goodman responded with this critique, causing the original authors to respond with this response. Looks like there are other follow ups by third-parties. The mark of an effective paper is that it is talked about and remembered.

Frequent Pattern Mining

2008-03-28T08:12:00.000-07:00

In the weekly RightNow AI Colloquium @ MSU CS , we read a paper by Jiawei Han et al. called
Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach.
Basically the problem is this, given a sequence of transactions involving multiple items per transactions, what are the frequent itemsets? Itemsets are groups of m items that tend to be purchased together. The earlier SQL-based version of FP-Tree looks interesting as well.

FP-Tree out competes in time complexity the Apriori Association Rule Miner Algorithm (Java Code). Not sure how it compares with this raft of other algorithms available at the FIMI.

I'd love to use an algorithm like this to extract pairs and triples of keywords from documents in a clickstream.. basically looking for recurring patterns in browsing/hunting bevavior in document repositories.

I would say the biggest issue using either of the two above algorithms in a 'production' system is that they are not incremental. Ideally one could process a batch of transactions a record at a time and form a rolling frequent itemset collection. Itemsets would move in and out of the collection as they achieved or lost 'support', and the cost of adding another transaction is minimal... as in not having to rescan all previous transactions.

My initial idea how to do this would be to devise an incremental approximation addition to any association miner. At the end of a full-run of your miner, you would keep the final itemsets AND the itemsets that just missed the support threshold. The incremental algorithm would process up to a tolerance level of new transactions, say log(n) of the original transaction set size, and look to promote the 'just missed' itemsets if support arrives. Maybe some attempt could be made to remove itemsets if the additional transactions sank their support level to below the cut-line. After more than log(n) new transactions arrive, you can reprocess the entire set or trim off the first log(n) of the old transactions plus the new ones.

There are likely some speedups to be had in subsequent reprocessings. If from the previous full-run you found that a collection of itemsets made the cut, you could prune out those itemsets from the old transactions.. restarting the algorithm with the previous run's itemsets in the "found pool".

Of course with an algorithm like FP-Tree you must save the tree for the next run, and devise a tree rebalancing algorithm to make it incremental (relative frequencies of items change with new information). It gets messy quick.

Road Coloring Problem solved

2008-03-24T08:00:00.000-07:00

I'm not sure why this hit my buttons, as it's not my area of expertise, yet I found it very interesting. Avraham Trahtman, 63 year old Russian mathematician who used to work as a plumber & maintenance guy in Israel, has solved (paper with solution) an interesting problem in graph theory. Unlike other famous problems with few applications, this appears to have some (network routing) and he's published an updated paper with a sub-quadratic algorithm.

I think it has been captured in news coverage more as a result of his age and story than importance of the problem.

Refocusing of Others Online to Behavioral Targeting and Computational Advertising

2008-02-12T10:09:00.000-08:00

On the work/professional front Others Online is going into a bit of a transformation.

A rethinking exercise demonstrated that what we do best was connect people with content based upon implicit attention streams (this can be anything, click streams, blog posts, twitter, searches). That content was other people (social referrals), content (web pages & blogs) and ads.

Optimizing the process of selecting ads for individual people/groups and context rather than broad categories is what we'll focus on for a while, particularly me as concentrate on being the computational advertising guy at OO.

As for the social networking part of the software, we're refocusing on adding value to existing community and topical sites and other like groups that tend to connect people around a specific topic or geography.

Personally I think the refocusing on computational advertising and targeting is a great choice. When was the last time a web advertisement was really relevant to you? Do you really want to see noisy advertisements for mortgage refinancing and Viagra-like products? The key to all of this is to be socially responsible and give users complete control so that we don't fall into the Facebook-Beacon backlash.

Well, that and some clever algorithms to do the learning.

Dual Purpose trip to Germany

2008-02-12T09:52:00.001-08:00

I was recently in Germany for two purposes. The first was for the 'Theory of Evolutionary Algorithms' conference at Dagstuhl Castle in Saarland Germany. This was a joy as I was able to focus nearly entirely on my PhD research and dissertation progress. At this point I'm in the home stretch.. I think I have two provable theorems sketched out and a set of new tractable items to explore to finish off the meat of the dissertation.

The second week in Germany was a beer tourist adventure through Bavaria and Bohemia. We hit Munich on day one and drank expensive tourist beer, then took a train to the Czech Republic to see Plzen (home of Pilsener beer) and Budweiss (Ceske Budejovice - original home of Budweiser beer). Plzen was very interesting and Budweiss was an adventure of train & bus travel. Two days later we took a train back into Germany to Bamberg. Bamberg is stunningly beautiful and is the home of a wide selection of locally crafted smoked lager beers. More on this trip in future posts.

Work and School News

2007-12-13T21:46:00.000-08:00

It seems I have committed the most frequent sin of blogging.. sporadic posting patterns. All of November and half of December and no posts. It's been a busy month at OthersOnline. We got a huge spike in user traffic and sign-ups, which is awesome.. and predictably exposed some performance issues. That work, plus working on a better user behavior capture algorithm (to better match users to other users and content) was the bulk of the time.

In school news, I just turned in a first draft of the dissertation to my adviser. It's really a disposable organizational draft to help us plan out what the flow of topics and structure is,, and what is left to add. Nice milestone anyway. Goal is late spring for near-final draft with the defense goal in august.

Some advice for people doing PhD work while employed full-time: If you are working in your field of graduate study, and your employer permits it.. do the dissertation on a work related topic! I could easily have done mine on a topic related to my AI work at RightNow and have finished by now. I chose to not only do a different topic in AI from work (to be more well-rounded) but to do it on the theory of that topic (genetic algorithms).

While this seemed a good choice at first, the dissertation sunk to 4th place on the priority list (family, career, misc leisure activities). Don't make this mistake! Take the shortest path and get done... then pursue the side topic under no pressure.

Inferring meaning from data and structure

2007-10-29T09:26:00.001-07:00

Jeremy Liew has quite the thread going on his blog about 'Meaning = Data + Structure (User Generated)', Part2 on Inferring Structure and a Guest Post by Peter Moore.

The post by Moore is a wonderful summary of approaches and their difficulties, and I'll post more on this as I think about it. My initial response is that we should stop looking/waiting for some near holy-grail {fully functional semantic web} and use a lot of good-enough {technologies, algorithms, ontologies} to make progress. I think that the perfection-in-reasoning stuff is great for the teleportation version of personal search vs the good-enough techniques as applicable now to the orienteering version of personal search. See this post and this paper for orienteering vs teleportation in search.

Last week the Bozeman AI group read a paper on Deriving a large Scale Taxonomy from Wikipedia. I look at this as an example of the main idea above, deriving structure from user generated content. True, Wikipedia is already structured, but not necessarily in a way that a computer program can use to reason with.

The killer thing about this idea is that it's finally time to do it. Essentially this is what machine learning and data mining has been about for years. I've read/perused hundreds of academic papers where the basic premise is that we write a suite of algorithms to learn/extract structure from a pool of data. A big chunk of papers in the KDD conferences each year (2007, 2006, 2005) operates on this premise and this field is quite old (decades).

Really pointy-headed CS types are horrible at monetizing their work. At approx the same time that Google founders were inventing PageRank, Jon Kleinberg was creating HITS. Both are link-analysis algorithms to augment what at the time were poor quality search engines. Over the past 10 years when they are evaluated head-to-head on some Information Retrieval task HITS works on-par with PageRank. Yet Kleinberg is not now worth 40 billion dollars like Brin and Page of Google.

I fear that the Semantic web people/researchers have been building sand castles for a decade rather than monetizing what they have to subsidize more research on it. Perhaps if they had been Delicious, Digg, WikiPedia, et al. would be contributing to the Semantic Web natively, rather than forcing people to figure out a way to export that data into RDF/OWL.

Semantic Wishfull Thinking? Or Semantics for turing lead into gold?

2007-10-24T22:22:00.000-07:00

I'm seeing quite the meme these days on the 'Semantic Web' as a way to build the next big thing (See Twine, AdaptiveBlue, more). The essence of the Semantic Web is the markup of knowledge in such a way as to enable machines to reason about it.

The idea of having every HTML page you download contain markup that enables a smart web browser or search engine to know that you are looking for (or browsing about) Anthrax the UK punk band, the US heavy metal band, the fly, or the toxin. This vision is basically one of the Structured Web.

There are issues in my mind:

1) The Semantic Web has been around for years. During all those years the content of the web grew from nearly nothing to the mountain of (mostly unstructured) goo we all browse daily. Why/How will all that knowledge be 'structured'?

Take Home: People do not want to 'structure' knowledge themselves. They are writing their content for people and not machines (except the SEO people).

2) Formally structured data is an OLD idea in AI. See expert systems. How will the 'semantic web' over come the basic problem that structuring human knowledge is DAMN hard. And by hard I mean making it consistent (this is what mostly broke expert systems).

Have you been following what Cyc Corp has been doing since 1984? Attempting to structure human knowledge. These guys have invented whole new ways of representing human knowledge.. where is it on the web? Can anyone tell me an application that uses it? I am very certain that the CycCorp guys could (and likely have) a way to export their databases into RDF, OWL, etc.

Also.. the old white-haired guys of AI invented various forms of Semantics and 'Knowledge Representation' way-back in AI history (see chapter 10 of Russell-Norvig).

Take Home: Once you have the knowledge structured and embedded, what happens next? Magic? Merely inventing a representation of knowledge relies on the 'if you build it they will come' doctrine of AI.. which has NEVER been true.

3) Reasoning with said structured knowledge is unsolved in general. Given a specific knowledgebase (or Semantic database) and specific questions (or semantic queries) systems can reason about the question and deliver results.. but it's still a garbage-in-garbage-out world.

This is especially true when most people really expect a search engine to read their minds (Sorry Udi - I agree with Greg) or they tend to give up on their search queries.

How do we prevent such systems from becoming SEO spammed? I suppose a reputation system on the source of semantic markup data could be created.

Take Home: How in the hell do I build a search engine that uses Semantics that really understands what I am looking for and delivers me the Answer? Such a system pretty much is an AI Oracle.

Ok.. enough with the half-empty-glass negativity! What can we really do with the Semantic web NOW?

For sure we can build a semantically enhanced 'filter' of the web. Google/Yahoo/MSN/Ask are great, but in the end the are giant databases that serve you up link-graph weighted & keyword-filtered URLs.

However, if you are trying to build a money making business, a new search box that returns URLs seems like an insane idea.. unless you can co-opt the browser and augment the results that the big-boys are returning (See Search Radar). Or pull a StumbleUpon strategy.

For a business, the Semantic Web is a potential tool in a step along the path in creating a valuable application. Remember your history here.. creating a giant repository and/or formal structure of knowledge will not alone result in something novel.. nor is using it required to create novelty in AI.

I'd probably make the argument that delicious itself (and similar data) is a growing embodiment of a user-generated database that clever software could derive semantic-data from.

I am NOT arguing that the semantic web is a bad idea... but be careful of the hype you read. The Semantic Web is merely the first step (and a hard one) at stitching together knowledge in a way that can be usefully used to reason. The S-M is as necessary for a smarter web as databases are for useful applications... yet the database is the data-store and NOT the application logic.

Recommender Systems

2007-10-19T08:18:00.000-07:00

Greg Linden has another insightful post on his blog about Recommender Systems. He argues that the systems can be tuned to recommend diversity (ala-Netflix), rather than the more too-similar echo chamber of stuff you see sometimes on Amazon.

Jeremy Liew at LightSpeed VCP had a good post recently about search query understanding being the future direction of search.

In my mind, recommender systems are part of that vision. A truly great search engine will seek to understand your queries, your query history, personal interests and recommend content.. rather than just give you a keyword-filtered & ranked slice of the web.

Yet there are other ways to achieve that kind of output. Search engines and AI in general are a good distance away from real query understanding (it requires some form of machine reading). If instead we consider bootstrapping a recommender system that is driven by people's recommendations on a topic.. we can potentially get there quicker. This is how you train product recommender systems (with purchase history).

A system that implicitly follows you around the web and allows your content to be communally shared into an index would at a minimum be a very fresh index of what people are looking at now. Combining this index with a social network of people (enabling matching of topically relevant users to you) and we have something of a human-filter of the web driving a content recommender.

Yes, this is what many social URL sharing sites are building now... but do they have the pieces all together to drive people to directed content rather than allowing them to surf the wave of current topics?

Seattle Beer notes

2007-10-18T12:34:00.000-07:00

My september trip to Seattle included stops at Kells. I really loved the Roslyn Brookside Lager from Roslyn Brewing. It has a wonderful fruity complexity to it, which is unusual for a lager (more like a Kolsch). A quick email to the brewer and I learned that he ferments it warm with a lager yeast.

I also enjoyed the Baron Brewing Helles Bock served at the Palace Kitchen. Great malt flavor. Great food at PK at reasonable prices.

On this October trip to Seattle I loved the Feierabend Pub. They have about 18 beers (all German styles) on tap. I tried/sampled about 5 kinds of Octoberfest and several other lagers.

Tap House Grill, 160 draft beers.. need I say more? This place was impressive. I tried two more Baron beers (Pils & Uber-Weiss) and the Brewery Ommegang Hennepin Farmhouse Saison. It's good, but my taste buds still prefer the New Belgium Saison.. the NB has a nice earthy taste.

Attention IR and People Search

2007-10-17T11:38:00.001-07:00

The SIGIR 2007 conference also had a couple of gems in the Doctoral Consortium workshop.

Krisztian Balog (University of Amsterdam) homepage
People Search in the Enterprise

The abstract of Balog looked a two areas concerning people search, profiling people and enabling search of those people based upon both the topical and social profile. Who is an expert on X? Who do I know (or get introduced to) someone who is an expert on X? His research seems to be just beginning.. I'll be checking his page for new papers.

Georg Buscher (German Research Center for AI) homepage
Attention-Based Information Retrieval

Buscher won the best presentation award at the workshop. His slides outline how attention data can be used to bias/rerank IR results to enable re-finding old information/documents as well as doing query expansion (profile based???) given the current user's attention data. His research is also fairly new.

Both of these topics are obviously of interest to Others Online and the idea of connecting people together through a common topic or set of topics that are learned as implicitly related to the users.

Learning to Rank

2007-10-17T10:16:00.000-07:00

SIGIR 2007 (which I unfortunately did not attend) had a really great workshop called 'Learning to Rank' or LTR. The weekly RightNow-organized Bozeman AI Colloquium recently covered two papers in this area. Essentially the idea is that a search engine can implicitly learn to rank documents for a given query by looking at user behavior.

The first one we covered (by Yeh, Lin, Ke & Yang) used genetic programming to do the learning. Needless to say this caught my eye. Evolutionary Algorithms are built to learn rankings, usually based upon a fitness function. I found this paper interesting, however even the authors admit that their algorithm is very slow.

In my mind they picked too complex of an algorithm. There are far simpler EAs that can do this job. The well-known (n+1) EA could do this task (per query). I'll likely be writing a paper on this for GECCO 2008. l

Many of the workshop papers reference work by Joachims and Radlinski (find them here). Their recent paper in IEEE Computer (not avail for free) was interesting in that they used a LTR method to re-rank Google results and then did a user-study to look at how effective the method was.

Personally I think that the idea of LTR should be a component of every search engine. The ranking of search results should change as fast as users interact with the content, rather than how fast the content itself changes. This is something that the big search engines are fairly quiet on, not sure why.

Sure it's an incremental rather than revolutionary step (Powerset is trying to take a revolutionary step), however can anyone give me a good argument why LTR should not be done? The idea can be applied to any engine.. keyword, link-graph (Google) or NLP based (Powerset).

Taking the next step beyond that, the next big thing could very well be doing an LTR method per-person or per-peer-group for each query family. This effectively would allow the engine to self-learn to personalize results. One can imagine how this could be glued into the idea of using the 'social graph' to establish the peer-group on a given topic/query.

More old wine in new Web 2.0 bottles

2007-09-21T15:00:00.000-07:00

In light of last week's post on "beware of old AI wine in new Web 2.0 bottles" I wanted to post this link from Joel Spolsky. (A buddy of mine brought my attention to it)

Once in a while Joel posts "strategy letters". This one addresses history repeating itself in the old-html-web -> ajax-web paralleling the text-terminal -> windows-api flow. Very true. I did find it odd that he did not mention the Google Toolkit in his thoughts about the potential game-changing "NewSDK" and how it needs fancy new compilers. As a CS geek I think the idea of compiling Java to cross-browser-compliant javascript a simply amazing technical achievement.

The interesting thing about this topic is that it's what Java was supposed to do for the browser back in the 90s. Didn't work, no one could keep their browser & the JVMs synced and integrated well, plus Microsoft managed to run good interference via IE just being crappy at Java/JVMs at that time.

Turns out that Java succeeded wildly in reinventing the way back-end web services are written (CGIs just don't cut it for some things despite the PHP/Perl/Python crowd making CGIs way more useful than before.) On the browser today's Java-JVM is the javascript-engine (which is not java at all). The idea of using JS as byte-code makes me cringe, but it's where we are.

Nice post Joel! Would be nice if he'd follow up on why he thinks that the Google Toolkit, Yahoo's YUI and others aren't yet (or won't get to) the definition of his NewSDK.

The Implicit Web flowing into Collective Search

2007-09-10T14:43:00.000-07:00

Here are some recent articles that I read and kept thinking about again and again. What is cool about this moment in time is that these things are gelling. Entrepreneurs and innovators are trying to build this stuff, rather than the ideas rotting unfulfilled in the mind of some AI/Search-Engine geek.

Read/Write Web's Implicit Web

Important point here is that systems should both learn what users are interested in implicitly and allow users control over the learned topics. The former point is what algorithms like collaborative filtering were intended to do. The latter is a great point that users should have visibility and control into their learned topics.

This has been a frequent critique against Amazon's recommender system.. while personalized, it can learn goofy things. I have no desire to be a frequent buyer of items similar to what I bought for a niece as a gift last year.

Collective Search by Greg Linden

I just learned that Greg is one of the brains behind Amazon's AI. Thinking about the data Amazon has and what could be done with it always makes me drool. Greg's post here is an aggregation of points he came up with while reading transcripts of the recent SES 2007 conference.

I'll join Ask's Jim Lanzone (isn't the new Ask.com much better than Google!) in saying that collective search is potentially better than personalized search. Greg is arguing for a redefinition of 'personalization' here, but we have to pick descriptive terms for abstract ideas. I would define personalization as skewing of search results by what you are interested in. Where I'd read collective search as letting the collective behaviors of a group of similar users influence/skew search results. This is the flavor of stuff I worked on at RightNow.

Ultimate Answer Engine @ Information Week

Favorite quote: "Who said an edit box and 10 blue links is what search is?" asks Microsoft's Satya Nadella.

This great piece has several items that just jumped out at me. "Queryless Search", essentially this is using what the system knows about you and your path through to the engine and do a implicit query. (We also worked and patented variations of this idea at RightNow). The "Personalization" and "Social Skills" sections deal with the ideas in Greg's post above. More to come on that re 'The Social Graph'.

Another good quote: "Serendipity is an amazing teacher". This is what Others Online is all about... focused on People, not necessarily documents/media.

After reading all three of these in the current context of what people are willing to spend time and money on... I can't help but be totally jacked about the opportunities at hand!

Loads of academics have been working on this stuff for years, check out any ACM SIGIR and various data mining conference proceedings for the last 10+ years. Personally, I've been thinking and working on many of the things above since 2000 when Doug Warner and I started doing a deep dive into the academic literature.

The "social graph" and search engines

2007-09-07T10:26:00.000-07:00

Robert Scoble recently posted about Mahalo, TechMeme and Facebook versus Google. His thesis is basically that somehow blending social networks with search engines will be the next big thing. He also comments (as have others) that searching blogs can get better results than major search engines sometimes.

Danny Sullivan chimed in response with a blistering commentary on both Scoble's "new ideas" and Mahalo (run by Jason Calacanis). Mahalo and ChaCha are both 'human powered' search engines. Basically they take popular search terms and use editor to augment and/or reorganize Google results.

First a history review. Way back Yahoo built it's people powered directory, while initially useful it could not keep up with the growth of the internet. Google comes along with a simple idea called PageRank (it essentially forms a Markov model of the web and computes the stationary distribution of the markov matrix - an 80+ year old idea applied to the web) and kills Yahoo's directory as well as purely keyword based engines like Altavista.

More History. Once upon a time in the 60s-80s expert systems were seen as the next big thing in AI. Solve all the world's problems by enabling a formal system of rules and facts to answer questions posed to the system. ES was a miserable failure at these lofty goals. Why? Growing the rulebase is hard. Humans do a terrible job at crafting rulesets that are complete and consistent (no conflicts). Even worse is when you throw multiple people at crafting rules together. You end up with trash.

Why is this relevant here? The lesson of ES seems to be lost on efforts like ChaCha and Mahalo. These systems are built on very basic rules (if query X then return A, B, C, D ...). Granted these are much simpler rules than a typical ES, and the engines don't support real reasoning using backward or forward chaining either. This may not save them.. the rules will still suffer from the huge maintenance problem in a context where the information captured is dynamic and changing. Just ask any of the dozen 80s companies that tried to build medical diagnosis expert systems. The rules suffered from inattention to medical advances as well as being contradictory (multiple doctors with different ideas making rules).

Nowdays we call this "linkrot" on the web. While successful, sites like About.com suffered from linkrot on pages not frequently edited. How will ChaCha and Mahalo avoid this without having a massive number of editors? Del.icio.us itself suffers from the same issues, people tag stuff and it mostly rots unorganized or maintained.

Yet More History. From about 1999 to 2003 AskJeeves.com sold software in the emerging web eCRM space in addition to having a search engine. Web eCRM (or web self-service) is essentially creating a customer service portal for corporate websites. The portal contains a collection of FAQs, articles, HowTos, Manuals etc. The essential function of the portal is to help people find what they are looking for and keep them from dialing the 1800 customer service number (which typically costs a company about $30 per call). AskJeeves sold their CRM and enterprise search unit in 2003 for less than 5 million dollars. Why? Their system required manual input of of a huge set of rules linking search queries and documents, as well as complex rules to equate queries to other queries and attempt to do some Natural Language Processing and Inference.

It didn't work, there was no way in hell that an average business user that maintained this set of Articles, FAQs etc was prepared to the massive amount of structuring. AskJeeves attempted to hire a team of people to optimize and tune the implementations. It took weeks of learning the business and translating that into structure for the engine to use. Nowdays we call this SEO.

Another example in CRM is the 'chatbot'. These are software products that try and give a user a good customer experience by putting a cute face/persona on the search box and having it talk back to you in a conversational style. They have never really taken off, despite the CRM industry analysts that love them. They suffer from the same basic problem that expert systems (chat bots are expert systems of a sort) suffered from.. structuring information is hard for most people to do.

For the past 8 years I've been working for an CRM company (RightNow Tech) that had a simple idea to help customer service web portals... implicitly learn from what users are doing in the portal to optimize the engine automatically. (See patents 6434550, 6665655, & 6842748 - at the moment the RNT systems process about 100 Million searches per month). The cutting edge of eservice CRM at the moment is taking that type of idea and THEN adding (or learning) structure to it.

Lessons learned and observations:

Study the basic history of AI. Here's a good book Artificial Intelligence: A Modern Approach.
Note that the one of the authors (Peter Norvig) is The Director of Research at Google. Prabhakar Raghavan is his counterpart at Yahoo. Ask.com and Microsoft also have strong AI people. There is no secret as to why these four companies are hiring all the good AI people they can relocate to the bay area, Seattle and New Jersey. You will not beat them with an expert system. A secondary lesson of AI is to never believe someone who will attempt to tell you that a new algorithm will create intelligence (neural networks anyone? Fuzzy Logic?).

Look at industries like CRM as a microcosm of the search industry. For every new idea you have, someone in CRM has likely tried it already on a smaller scale.

Beware of old wine in new bottles. You might be able to spend enough money on PR to help you get attention.. but you will likely die unless you invest in real scalable algorithms to do the work.

I'm certainly not intending to down-grade ChaCha and Mahalo as viable businesses. Often the viability of a business is independent of the technology used. They seem to have plenty of funding, and will likely adapt as they see problems. A babe-in-the-woods can't get 20 million in VC money. Neither of these systems will require boiling-the-ocean and implementing strong AI. Spinning a tight loop on what users are looking for and optimizing those results as fast as possible might work long enough to make some cash... it worked to bootstrap Yahoo after all.

As for the social-network blending into standard search? Stay tuned, I'll post some thoughts on that soon. There are plenty of good AI people working on graph based data mining.

Circling back to expert systems, if you can automatically 'read' text, and induce a rule-base.. then use that to help with queries, then we have something. I believe the direction of search engines will slowly head in this direction... machine reading.

Jordan Mitchell (my new boss at OthersOnline.com) recently posted on the same subject on his blog.

Other interesting links about this:
Skrentablog on Mahalo
Keving Burton's Thoughts on the Social Graph

New Job - OthersOnline.com

2007-09-06T22:50:00.001-07:00

I just started a new job at OthersOnline.com. It's a new startup with a social networking spin. We let users declare themselves, their pages and interests, then be syndicated around the web via the OO Widget (see it to the right). We also have a browser toolbar that allows users to see other people relevant to the user's own interests and the content of the current webpage. I think my official title is the "Search Guy" or "AI Guy" or something. The potential of these two basic ideas is huge, and I'm wading in chest deep to put some great AI ideas into the systems. More posts coming soon on these topics.

I spent the last (nearly) eight years working at RightNow Technologies (a CRM SAAS company - once upon a time it was a small startup as well) in the AI Research Labs. At RNT I was in charge of implementing various search engines, data mining & nlp algorithms, swarm techniques, user interfaces, analytics, and whatever AI I could throw at the basic problem of enabling endusers to find information on approx 2000+ customer service portals around the web (here is Leapfrog's Portal). I spent most of the last six months becoming the project manager of the group, responsible for multiple projects, coordinating with product management, initiating new feature ideas, etc. It's a fantastic group to work for, and has an application for about any advanced CS topic there is. A more complete synopsis is on my resume.

(At some point in 2008 I will hopefully finish a PhD in CS at Montana State - topic is Theory of Genetic Algorithms)

New Blog

2007-09-06T22:01:00.000-07:00

I have been ignoring using a blog for too long, the old homepage is too static. I'll use this space to muse about artificial intelligence, search engines, machine learning, social media & widgets, my career, PhD dissertation progress, Montana, fishing and good beer.

My Montana State University homepage

RSS Feed of this Blog