31 January 2010

Coordinate ascent and inverted indices...

Due to a small off-the-radar project I'm working on right now, I've been building my own inverted indices. (Yes, I'm vaguely aware of discussions in DB/Web search land about whether you should store your inverted indices in a database or whether you should handroll your own. This is tangential to the point of this post.)

For those of you who don't remember your IR 101, here's the deal with inverted indices. We're a search engine and want to be able to quickly find pages that contain query terms. One way of storing our set of documents (eg., the web) is to store a list of documents, each of which is a list of words appearing in that document. If there are N documents of length L, then answering a query is O(N*L) since we have to look over each document to see if it contains the word we care about. The alternative is to store an inverted index, where we have a list of words and for each word, we store the list of documents it appears in. Answering a query here is something like O(1) if we hash them, O(log |V|) if we do binary search (V = vocabulary), etc. Why it's called an inverted index is beyond me: it's really just like the index you find at the back of a textbook. And the computation difference is like trying to find mentions of "Germany" in a textbook by reading every page and looking for "Germany" versus going to the index in the back of the book.

Now, let's say we have an inverted index for, say, the web. It's pretty big (and in all honesty, probably distributed across multiple storage devices or multiple databases or whatever). But regardless, a linear scan of the index would give you something like: here's word 1 and here are the documents it appears in; here's word 2 and its doucments; here's word v and its documents.

Suppose that, outside of the index, we have a classification task over the documents on the web. That is, for any document, we can (efficiently -- say O(1) or O(log N)) get the "label" of this document. It's either +1, -1 or ? (? == unknown, or unlabeled).

My argument is that this is a very plausible set up for a very large scale problem.

Now, if we're trying to solve this problem, doing a "common" optimization like stochastic (sub)gradient descent is just not going to work, because it would require us to iterate over documents rather than iterating over words (where I'm assuming words == features, for now...). That would be ridiculously expensive.

The alternative is to do some sort of coordinate ascent algorithm. These actually used to be quite popular in maxent land, and, in particular, Joshua Goodman had a coordinate ascent algorithm for maxent models that apparently worked quite well. (In searching for that paper, I just came across a 2009 paper on roughly the same topic that I hadn't seen before.)

Some other algorithms have a coordinate ascent feel, for instance the LASSO (and relatives, including the Dantzig selector+LASSO = DASSO), but they wouldn't really scale well in this problem because it would require a single pass over the entire index to make one update. Other approaches, such as boosting, etc., would fare very poorly in this setting.

This observation first led me to wonder if we can do something LASSO or boosting like in this setting. But then that made me wonder if this is a special case, or if there are other cases in the "real world" where you data is naturally laid out as features * data points rather than data points * features. Sadly, I cannot think of any. But perhaps that's not because there aren't any.

(Note that I also didn't really talk about how to do semi-supervised learning in this setting... this is also quite unclear to me right now!)

39 comments:

Top said...

I'm sorry if this sounds silly, but wouldn't naive bayes be ridiculously easy to train in this setting (even EM for semi-supervised naive bayes)?

Bob Carpenter said...

Madigan and Lewis's Bayesian Multinomial Regression (BMR) package uses coordinate ascent with L1 priors, and is pretty scalable. They seem to have added hierarchical models since I last checked, and they allow very flexible priors with means and variances specified by dimension.

More practically speaking, who builds a reverse index and throws away the original docs? Why do you want to train coordinate-wise?

P.S. If you think of the natural indexing as a relation R(doc,term) between a doc to its terms, it naturally corresponds to a function from the doc to its set of terms. If you look at the usually definition of relation inverse, you get R^{-1}(term,doc) = R(doc,term), which corresponds to a map from terms to the set of docs in which they occur.

P.P.S. Apache Lucene's inverted indexes are flexible, fast, and easy to use, at least from Java. Lucene uses a byte-based variable length encoding of document id sequences, and can store and compute with offset info as well as simple occurrence. If there's no dynamic doc insertion/deletion, building your own reverse indices is really easy. The Managing Gigabytes book has a reasonable discussion of these issues.

rui said...

nike air max 90
nike air max 95
nike shoes
nike air
nike air shoes
nike air max tn
nike air rift
nike shox r4
sports shoes
nike air rifts
nike air rift trainer
nike air max 360
nike shox nz
puma cat
air max trainers
mens nike air max
nike air
puma mens shoes
puma shoes
puma speed
nike shoes air max
nike shoes shox
air shoes
Lucyliu IS Lucyliu
nike shoe cart
puma future
levis jeans
nike rift shoes
cheap nike air rifts
bape shoes
cheap puma
nike rift
jeans shop
diesel jeans

nike said...

cheap nike shox
cheap sport shoes
nike tn dollar
ed hardy ugg boots
ed hardy love kills slowly
ed hardy clothing us
ed hardy clothing
cheap ed hardy
cheap ed hardy clothing
ed hardy clothes
ed hardy wholesale
ed hardy clothing
ed hardy t shirts
ed hardy shirts
ed hardy uk
ed hardy t shirts
ed hardy shirts
ed hardy hoodies
Cheap JORDAN SHOES,,
cheap nike max ,。
puma future cat
ed hardy ugg boots.
ed hardy love kills slowly boots.
ed hardy love kills slowly.
ed hardy polo shirts.
cheap ed hardy clothing,.
ed hardy shirts .
ed hardy t shirts.,.,.

qishaya said...

one day i went shopping outside,and in an ed hardy store,I found some kinds of ed hardy i love most they are Your website is really good Thank you for the information ed hardy ed hardy ed hardy clothing ed hardy clothing ed hardy shoes ed hardy shoes don ed hardy don ed hardy ed hardy clothes ed hardy clothes ed hardy bags ed hardy bags ed hardy swimwear ed hardy swimwear ed hardy jeans ed hardy jeans ed hardy mens ed hardy mens Thank you for the information

ally said...

Fashion trends change on daily basis, like Gold GHD. Following the latest in designer shades has become a passion of everyone, now Burberry Sunglasses. If you are the type of a woman who loves to explore in fashion, our ED Hardy Sunglasses will definitely satisfy your taste. Cheap Ed Hardy Sunglasses is also OK. Ed hardy streak of clothing is expanded into its wholesale ED Hardy T-shirt chain so that a large number of fans and users can enjoy the cheap ED Hardy Clothing range easily with the help of numerous secured websites, actually, our ED Hardy Outlet. As we all know, in fact discount ED Hardy, is based on the creations of the world renowned tattoo artist Don Ed Hardy. Well, this question is bound to strike the minds of all individuals. Many people may say Prada shoes is a joke, but we can give you Prada Sunglasses, because we have Prada handbags. Almost everyone will agree that Prada Purses are some of the most beautiful designer handbags marketed today. Now we have one new product: Prada totes. The reason is simple: fashion prohibited by ugg boots, in other words, we can say it as Cheap ugg boots. Would you like to wear Discount ugg boots. We have two kinds of fashionable boots: classic ugg boots and ugg classic tall boots. Ankh Royalty--the Cultural Revolution. Straightens out the collar, the epaulette epaulet, the Ankh Royalty Clothing two-row buckle. Now welcome to our Ankh Royalty Outlet. And these are different products that bear the most famous names in the world of fashion, like Ankh Royalty T shirt by the way -Prada, Spyder, Moncler(Moncler jackets,or you can say Moncler coats, Moncler T-shirt, Moncler vest,and you can buy them from our discount Moncler outlet), GHD, ED Hardy, Ankh Royalty, Twisted Heart.

ally said...

moncler jacketsmonclermoncler coatsmoncler t-shirtmoncler vestmoncler outletugg bootscheap ugg bootsdiscount ugg bootsugg classic tall bootsclassic ugg bootsmoncler jacketsmoncler
new moncler coatsmoncler vestmoncler outletmoncler polo t-shirtcoach outletcoach handbagscoach bagscoach totescoach outletlouis vuitton handbagsLV handbags 2010Louis Vuitton bags
Louis Vuitton totesrain bootsrainweardiesel jeansTure Religion Jeanslevis jeansabercrombie and fitch outlet
ed hardy wholesaleed hardy outletcheap ed hardy wholesalediscount ed hardy wholesalewholesale ed hardyGHDGHD straightenersCheap GHDDiscount GHDGHD OutletGHD New Pink

Ann said...

Fashion trends change on daily basis, like Gold GHD. Now Burberry Sunglasses.Our ED Hardy Sunglasses will definitely satisfy your taste. ED Hardy T-shirt chain makes people enjoy the cheap ED Hardy Clothing range easily our ED Hardy Outlet. As we all know, in fact discount ED Hardy, is based. The reason is simple: fashion prohibited by polo boots, in other words, we can say it as polo shoes. Would you like to wear cheap ugg boots? Now welcome to our paul smith outlet. And these are different products, like Puma Shoes (or you can say Puma Sneaker, and you can buy them from our puma outlet), GHD, ED Hardy, UGG, Paul Smith and brand Sunglasses. For those who desire for a ugg boots but have to refrain themselves from buying one ugg boots, there are some company that offer discount ugg boots.

songsong_like said...

If you really want it
nike outlet
everything to your fire
adidas outlet
puma outlet
you can do anything you want to
wholesale nike shoes
wholesale jordans
china wholesale
learn how to win
nike shoes wholesale
wholesale jordan shoes
living your dreams
jordan 11
jordan 12
jordan 13
jordan 14
stylish design
wholesale clothing

daiyanren said...

coats & jackets
If one knows where to, the world will give way.
north face jackets
moncler
World-class brands
moncler jackets
The top fabric produced in France is 100%
duvetica
Italy's top outdoor brands
peuterey
Good quality and function, more accord with fashionable design
spyder jackets
High-grade, innovation, the trend of the brand
Columbia Sportswear
The quality is so good
quiksilver jackets
Young and creative style
ski jacket


You can have a look at it.
jordan shoes
Wow.
newest jordans
jordan 7
Wonderful!
air yeezy
jordan true flight
If you like,you can contact us.
jordan 3
jordan 4
We offer different styles.
jordan 1
jordan 2
Thanks.
jordan 5
jordan ajf shoes
There are cheap shoes to choose
nike footwear
jordan flight 45
Good quality with low price.
air jordan 2010
Air Jordan 2009
Enjoy it!
jumpman
nike trainers

mili said...

I can't believe it.
abercrombie outlet
You can have a look at it.
abercrombie fitch outlet
The quality is so good
nike shoes wholesale
wholesale jordan shoes
Young and creative style
wholesale clothing
wholesale nike shoes
wholesale jordans
Young and creative style
china wholesale
There are cheap shoes to choose
jordan 6
jordan 28

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..

sesli sohbet
seslisohbet
sesli chat
seslichat
sesli sohbet sitesi
sesli chat sitesi
sesli sohpet
kamerali sohbet
kamerali chat
webcam sohbet

jacket said...

You can have a look at it.
coats & jackets
jordan shoes
The quality is so good.
abercrombie and fitch
abercrombie & fitch
Abercrombie and fitch outle

combattery84 said...

Laptop battery
ACER Laptop Battery
ASUS Laptop Battery
COMPAQ Laptop Battery
Dell Laptop Battery
HP Laptop Battery
IBM Laptop Battery
SONY Laptop Battery
TOSHIBA Laptop Battery
APPLE M8403 battery
APPLE A1078 Battery
APPLE A1079 battery
APPLE A1175 battery
APPLE a1185 battery 1
APPLE A1189 battery
Acer aspire 5920 battery
Acer btp-arj1 battery
Acer LC.BTP01.013 battery

Acer ASPIRE 1300 battery
Acer ASPIRE 1310 battery
Acer Aspire 1410 battery
Acer ASPIRE 1680 battery
ACER BTP-63D1 battery
ACER BTP-43D1 battery
Acer lc.btp05.001 battery
Acer aspire 3000 battery
Acer Travelmate 4000 battery
ACER aspire 5560 battery
ACER BATBL50L6 battery
ACER TravelMate 240 Battery
ACER BT.00803.004 Battery
ACER Travelmate 4002lmi battery
Acer travelmate 800 battery

combattery84 said...

Laptop Battery
acer Laptop Battery
apple Laptop Battery
asus Laptop Battery
compaq Laptop Battery
Dell Laptop Battery
fujitsu Laptop Battery
gateway Laptop Battery
hp Laptop Battery
ibm Laptop Battery
sony Laptop Battery
toshiba Laptop Battery
APPLE M8403 battery
APPLE A1078 Battery
APPLE A1079 battery
APPLE A1175 battery 1
APPLE a1185 battery
APPLE A1189 battery
Acer aspire 5920 battery
Acer btp-arj1 battery
Acer LC.BTP01.013 battery
Acer ASPIRE 1300 battery
Acer ASPIRE 1310 battery
Acer Aspire 1410 battery
Acer ASPIRE 1680 battery
ACER BTP-63D1 battery
ACER BTP-43D1 battery
Acer lc.btp05.001 battery
Acer aspire 3000 battery
Acer Travelmate 4000 battery
ACER aspire 5560 battery
ACER BATBL50L6 battery
ACER TravelMate 240 Battery
ACER BT.00803.004 Battery

combattery84 said...

ACER Travelmate 4002lmi battery
Acer travelmate 800 battery
Acer aspire 3613wlmi battery
Travelmate 2414wlmi battery
Acer batcl50l battery
Acer Travelmate 2300 battery
ACER aspire 3610 battery
ACER travelmate 4600 battery
Dell Latitude D800 battery
Dell Inspiron 600m battery
Dell Inspiron 8100 Battery
Dell Y9943 battery
Dell Inspiron 1521 battery
Dell Inspiron 510m battery
Dell Latitude D500 battery
Dell Latitude D520 battery
Dell GD761 battery
Dell NF343 battery
Dell D5318 battery
Dell G5260 battery
Dell Inspiron 9200 battery
Dell Latitude C500 battery
Dell HD438 Battery
Dell GK479 battery
Dell PC764 battery
Dell KD476 Battery
Dell Inspiron 1150 battery

ylinling001 said...

I like your article, really interesting! My point is also very good, I hope you'll like:chi flat iron are a very popular choice of hair straightener.New Balance,new Blance shoes,new Blance Outlet are some of the most comfortable and stylish shoes on the market today. The designer has a whole range of shoes for all types of athletes. five finger shoes,vibram five fingers,Five fingers shoes give women the feeling of walking barefoot while still keeping the feet protected.

DiSCo said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
kameralı sohbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
seslidunya
seslisehir
sesli sex

trustme said...

This is really a nice blog, I appreciate you for telling us so nice things, thank you!By the way, if you like nike tn you can come here to choose! We have a lot of
nike tn,tn chaussures,
nike tn chaussures
nike tn requin chaussures,nike air max tn chaussures.
nike homme chaussures,
nike femme chaususres,
nike enfant chaussres,
MBT France
vibram
If you want to find the shoes according to the sorts, then here you can have the informations,
we classied the shoes in nike presto,
nike air max,
nike air rift ninja,
tn requin,tn pas cher
vibram fivefingers,
converse.
At the same time, the vibram also offer you in our store.
You also can choose the most fashionable sunglasses here, it really can make you different from other people. We have
sunglasses,designer sunglasses,
wholesale sunglasses,sunglasses discount in USA.
They includ men's sunglasses,women's sunglasses.
So many fashion brands are for you,like Dior Sunglasses,
Emporio Armani Sunglasses,
Fendi Sunglasses,
Giorgio Armani Sunglasses,
Gucci Sunglasses,
LV Sunglasses and so on.

Sesli Chat said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
sesli muhabbet siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
görüntülü muhabbet siteleri
kameralı sohbet siteleri
kameralı chat siteleri
kameralı muhabbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
birsesver
birses
seslidunya
seslisehir
sesli sex

Ramy Ghaly said...

Social Media is big, but are there semantic tools to monitor them?

Not too long ago a series of reputation disasters aided and abetted by social media have seriously affected Tiger Woods, Toyota, Lebron James, Mel Gibson, BP, and assorted other businesses, entertainment figures and politicians. The noise level woke some people up. Needless to say, Google’s recent purchase of MetaWeb, and the booming business of “Social Business Software” are indicators that monitoring social media is a growing trend with business opportunities to meet the thrust of semantic tools to be put in hands of enterprises that enable them to monitor their brands, reputation, and other influences. It is estimated that text analytical industry to be growing by 25% Y-O-Y based on an estimate made by Seth Grimes, Text Analytics Conference Chair, in an article http://www.b-eye-network.com/channels/1394/view/12638 .

Semantic Tool that works.

Ctrl is a library with an API that can be used to extract metadata (key topics, and entities) of any textual document, to generate a document summary, and to index and retrieve documents by topics as opposed to key words.

Ctrl can be used in several domains for different purposes (besides the obvious application in search). For instance, in the news industry Ctrl provides a tool to automatically generate the ‘story highlights’, categorize and index any article based on its topics, and recommend related stories. This in turn helps both internal and external (users) in the retrieval of related documents for any required topic; it further allows automatic data push (could be in the form of RSS Feeds) for user‐selected topics.

In this context, Ctrl can be used in effective targeted marketing since users are retrieving highly relevant information that exactly matches their topics of interest. Ctrl can also be the new standard in the business intelligence industry for intelligent topic‐based enterprise search. Its ability to provide relevant documents based on topics is a daily need in large corporations. The various solutions that are currently employed in the industry are quite costly and are time‐ and error-prone since they rely on expert topic (or meta‐data) engineering for effective performance. In the Intelligence community, Ctrl means cutting time and cost that is being spent on processing a huge number of documents ‘manually’ searching for relevant information about specific topics, since the identification of topics (and more importantly, the identification of the key topics) is the most important differentiator between Ctrl and existing systems. Other applications can be developed around Ctrl’s API functionality to service several other fields especially when integrated with existing software (e.g., database systems, desktop and document management tools, etc.)
The accuracy of Ctrl's WSD algorithm in inferring the most likely meaning of a word in some context is above 80%, and, as far as we know, this accuracy rate is by far much higher than any WSD results that have been reported in the computational linguistics research.

Ctrl give words meanings, including names of things. To do so basic reference resolution and entity identification has to be performed. Names of people, organizations, movies, etc. are not therefore just words and phrases, but are full-fledged concepts that can be related to and matched with other concepts and topics. Thus, while the sentence “popularity of former NY Yankees slugger Babe Ruth” is not at all related to “Dr. Ruth popularity in NY”, there is clearly some semantic relation between “US President Barak Obama” and “German Chancellor Angela Merkel” (due, among other things, to the semantic relationship between ‘Barak Obama’ and ‘Chancellor’, for example). Read more: http://ctrl.pragma-tech.com

Now you can try it yourself! If you would like to receive an invitation to test ctrl online, please visit this link below:
http://ctrl.pragma-tech.com/DemosInvitation.aspx

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер

Anonymous said...

коттедж
восстановление зрения
зеленый лазер
электрошокер