21 October 2009

Convex or not, my schizophrenic personality

Machine learning as a field has been very convex-happy for the past decade or so. So much so that when I saw a tutorial on submodular optimization in ML (one of the best tutorials I've seen), they said something along the lines of "submodularity will be for this decade what convexity was for the last decade." (Submodularity is cool and I'll post about it more in the future, but it's kind of a discrete analog of convexity. There's a NIPS workshop on the topic coming up.) This gives a sense of how important convexity has been.

There's also a bit of an undercurrent of "convexity isn't so great" from other sides of the ML community (roughly from the neural nets folks); see, for instance, Yann LeCun's talk Who's Afraid of Non-convex Loss Functions, a great and entertaining talk.

There's a part of me that loves convexity. Not having to do random restarts, being assured of global convergence, etc., all sounds very nice. I use logistic regression/maxent for almost all of my classification needs, have never run a neural network, and have only occasionally used svms (though of course they are convex, too). When I teach ML (as I'm doing now), I make a bit deal about convexity: it makes life easy in many ways.

That said, almost none of my recent papers reflect this. In fact, in the structure compilation paper, we flat out say that non-linearity in the model (which leads to a non-convex loss function) is the major reason why CRFs outperform independent classifiers in structured prediction tasks! Moreover, whenever I start doing Bayesian stuff, usually solved with some form of MCMC, I've completely punted on everything convex. In a "voting with my feet" world, I could care less about convexity! For the most part, if you're using EM or sampling or whatever, you don't care much about it either. Somehow we (fairly easily!) tolerate whatever negative effects there are of non-convex optimization.

I think one reason why such things don't both us, as NLPers, as much as they bother the average machine learning person is that we are willing to invest some energy in intelligent initialization. This already puts us in a good part of the optimization landscape, and doing local hillclimbing from there is not such a big deal. A classic example is the "Klein and Manning" smart initializer for unsupervised parsing, where a small amount of human knowledge goes a long way above a random initializer.

Another style of initialization is the IBM alignment model style. IBM model 4 is, of course, highly non-convex and ridiculously difficult to optimize (the E step is intractable). So they do a smart initialization, using the output of model 3. Model 3, too, is highly non-convex (but not quite so much so), so they initialize with model 2. And so on, down to model 1, which is actually convex and fairly easy to optimize. This sequencing of simple models to complex models also happens in some statistical analysis, where you first fit first order effects and then later fit higher order effects. The danger, of course, is that you got to a bad hill to climb, but this overall generally appears to be a bigger win than starting somewhere in the middle of a random swamp. (Of course, later, Bob Moore had this cute argument that even though model 1 is convex, we don't actually ever optimize it to the global optimum, so doing clever initialization for model 1 is also a good idea!)

These two ideas: clever initialization, and sequential initialization, seem like powerful ideas that I would like to see make their way into more complex models. For instance, in the original LDA paper, Dave Blei used an initialization where they pick some random documents as seeds for topics. As far as I know, no one really does this anymore (does anyone know why: does it really not matter?), but as we keep building more and more complex models, and lose hope that our off the shelf optimizer (or sampler) is going to do anything reasonable, we're probably going to need to get back to this habit, perhaps trying to formalize it in the meantime.

30 comments:

slycoder said...

Maybe I can answer the question at the end about LDA. Because of the way variational inference for LDA is formulated as an optimization problem, you need to initialize with something which breaks the symmetry and how you do this matters which is why AFAIK Blei's lda-c distribution by default still uses the seeding method you mentioned.

A lot of people have lately moved towards using collapsed Gibbs sampling. Initialization seems to matter less here, and you needn't break any symmetries since the non-determinism will take care of that for you.

rr8004 said...

love your blog! Very cool! Please come visit my site Business Trade Guide of Columbus Ohio OH when you got time.

rr8004 said...

love your blog! Very cool! Please come visit my site Austin Business Directory when you got time.

rr8004 said...

Wow! Thank you! I always wanted to write in my site something like that. Can I take part of your post to my blog? Please come visit my site Jacksonville Business Search Engine when you got time.

rr8004 said...

Wow! Thank you! I always wanted to write in my site something like that. Can I take part of your post to my blog? Please come visit my site Jacksonville Business Directory Forum Blog Classifieds when you got time.

Mark Dredze said...

Convexity still matters, but we care less about it when doing things that are never going to be convex. For supervised learning, we can get nice convex optimization for basically anything we want, and so we are happy. Why deal with non-convexity?

For the more complex graphical models, could we ever hope to achieve convexity? No. If we could define a convex model, then we would. But since we couldn't learn these models without using non-convex objectives, we are willing to settle for non-convexity.

The interesting tension comes when you have reasonable convex approximations for non-convex objectives. There are a number of papers that need to make this decision: solve the non-convex objective, or solve exactly a convex approximation.

As we continue to look at these complex graphical models, the understanding of issues with non-convexity will become increasingly important.

Research Papers said...

Many institutions limit access to their online information. Making this information available will be an asset to all.

Admin said...

thnxxx for sharing the information

public speaking

thomson said...

Beauty Schools And Cosmetology Schools, Beauty Careers and Cosmetology training online guide. Find out how to find the best cosmetologist schools, career and job descriptions of spa therapist, hair designer, makeup artist.cosmetology jobs salaries

thomson said...

Beauty Schools And Cosmetology Schools, Beauty Careers and Cosmetology training online guide. Find out how to find the best cosmetologist schools, career and job descriptions of spa therapist, hair designer, makeup artist.cosmetology jobs salaries

rr8004 said...

You do have a point here :) I admire the stuff you post and the quality information you offer in your blog! Keep up the good work dude. Please come visit my site Fresno Business Search Engine when you got time.

rr8004 said...

You do have a point here :) I admire the stuff you post and the quality information you offer in your blog! Keep up the good work dude. Please come visit my site Fresno Web Link when you got time.

rr8004 said...

I found your blog on google and read a few of your other posts. I just added you to my Google News Reader. Keep up the good work. Look forward to reading more from you in the future. Please come visit my site Kentuchy KY Phone Directory when you

rr8004 said...

I found your blog on google and read a few of your other posts. I just added you to my Google News Reader. Keep up the good work. Look forward to reading more from you in the future. Please come visit my site Louisville Phone Book when you

Godar said...

There was this guy who believed very much in true love and decided to take his time to wait for his right girl to appear.
nike shox nz shoes
cheap nike shox nz shoes
nike shoxs
Chaussures puma
wholesale nike shox nz shoes
cheap ugg boots
nike womens shoes
hommes nike chaussures
femmes nike
mens puma shoes
hommes puma chaussures
femmes puma chaussures
Nike Air Max 360 chaussures
Nike Air Max 90 Chaussures
Nike Air Max 95 Chaussures
Nike Air Max Ltd Chaussures
nike shox
Nike Max Tn Chaussures
nike 360 air max
nike running shoes
NIKE air shoes
nike shox nz shoes online store
nike air max
Nike Air TN Spider Chaussures
Nike Max Plata Chaussures
Nike R4 Plating Chaussures
Nike Shox Rival Velcro
Nike Shox Deliver Chaussures
Nike Shox Classic Chaussures
Nike NZ Plating Chaussures
wholesale nike shoes
nike shox torch
sneakers shoes
Nike Tn
discount nike shoes
nike shox r4
tn dollar
cheap nike shoes
nike tennis shoes
cheap nike shox
free shipping shoes
Paypal Credit card Accept
nike shoes
nike discount shoes
cheap puma shoes
nike shox shoes
chaussures nike
nike free shoes
buy shoes online
You may painfully regret, only to realise that it is too late.

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

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

janewangleilei said...

You can have a look at it.
jordan shoes
jordan ajf shoes
There are cheap shoes to choose
jordan 6
jordan 7
Good quality with low price.
air jordan 2010
Air Jordan 2009
If you like,you can contact us.
jordan 3
jordan 4
We offer different styles.
jordan 1
jordan 2
Thanks.
jordan 5
jumpman
I can't believe it.
nike outlet
You can have a look at it.
adidas outlet
puma outlet
north face
moncler
Wow
ak jackets
spyder jackets
Beautiful!
Columbia Sportswear
quiksilver jackets
Enjoy it.
burton jacket
powder room jackets
Thanks.
karbon jacket
goldwin jackets
I can't believe it.
eider jackets
You can have a look at it.
sportalm jackets
Wonderful!
west scout
stylish design
Ed Hardy Wholesale
fashion excellent quality
wholesale Ed Hardy
ED Hardy clothing bring you a super surprise!
ed hardy wholesale clothing
I can't believe it.
abercrombie outlet
You can have a look at it.
abercrombie fitch outlet
Wonderful!
coats & jackets

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.

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 sohbetsesli chatkamerali sohbetseslisohbetsesli sohbet sitelerisesli chat siteleriseslichatsesli sohpetseslisohbet.comsesli chatsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet
seslisohbetsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet

janewangleilei said...

You can have a look at it.
jordan shoes
jordan ajf shoes
There are cheap shoes to choose
jordan 6
jordan flight 45
Good quality with low price.
air jordan 2010
Air Jordan 2009
Enjoy it!
jumpman
jordan 28
Wow.
newest jordans
Wonderful!
air yeezy
jordan true flight
I can't believe it.
nike outlet
adidas outlet
puma outlet

janewangleilei said...

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
jordan 6
jordan flight 45
Good quality with low price.
air jordan 2010
Air Jordan 2009
Enjoy it!
jumpman
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

songsong_like said...

Young and creative style.
abercrombie and fitch
abercrombie & fitch
You can have a look at it.
Abercrombie and fitch outlet
ED Hardy clothing bring you a super surprise!
ed hardy wholesale clothing
If you really want it.
nike outlet

combattery84 said...

Laptop Battery
ACER Laptop Battery
ASUS Laptop Battery
COMPAQ Laptop Battery
Dell Laptop Battery
FUJITSU 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

combattery84 said...

Dell inspiron 8500 battery
Dell Inspiron 4100 battery
Dell Inspiron 4000 battery
Dell Inspiron 8200 battery
Dell FK890 battery
Dell Inspiron 1721 battery
Dell Inspiron 1300 Battery
Dell Inspiron 1520 Battery
Dell Latitude D600 Battery
Dell XPS M1330 battery
Dell Latitude D531N Battery
Dell INSPIRON 6000 battery
Dell INSPIRON 6400 Battery
Dell Inspiron 9300 battery
Dell INSPIRON 9400 Battery
Dell INSPIRON e1505 battery
Dell INSPIRON 2500 battery
Dell INSPIRON 630m battery
Dell Latitude D820 battery
Dell Latitude D610 Battery
Dell Latitude D620 battery
Dell Latitude D630 battery
Dell xps m1210 battery
Dell e1705 battery
Dell d830 battery
Dell inspiron 2200 battery
Dell inspiron 640m battery
Dell inspiron b120 battery
Dell xps m1210 battery

combattery84 said...

Dell inspiron xps m1710 battery
Dell inspiron 1100 battery
Dell 310-6321 battery
Dell 1691p battery
Dell Inspiron 500m battery
Dell 6Y270 battery
Dell inspiron 8600 battery
Latitude x300 series battery
Dell latitude cpi battery
Dell 1x793 battery
dell Inspiron 1501 battery
Dell 75UYF Battery
Dell Inspiron 1720 battery
dell Latitude C640 battery
Dell XPS M140 battery
Dell Inspiron E1405 battery
dell 700m battery
dell C1295 battery
Dell U4873 Battery
Dell Latitude C600 battery
Armada E700 Series battery
Compaq 116314-001 battery
Compaq 319411-001 battery
Compaq nc4200 battery
Compaq Presario R3000 Battery
Compaq Presario 2100 battery
Compaq Presario r3000 Battery
Compaq Business Notebook NX9000 series battery
HP 395789-001 battery
HP 446506-001 Battery

combattery84 said...

HP dv9700 battery
HP F4809A Battery
HP nc8000 battery
HP nc8230 battery
HP pavilion zd8000 battery
HP f2024b battery
HP f4812a battery
HP Pavilion ZV5000 battery
HP Pavilion DV1000 battery
HP Pavilion ZD7000 Battery
HP Pavilion DV2000 battery
HP Pavilion DV4000 Battery
HP Pavilion dv6000 Battery
HP Pavilion DV9000 Battery
HP F4098A battery
HP pavilion zx6000 battery
HP omnibook xe4400 battery
HP omnibook xe4500 battery
HP omnibook xe3 battery
Notebook NX9110 battery
IBM 02K6821 battery
IBM 02K7054 battery
IBM 08K8195 battery
IBM 08K8218 battery
IBM 92P1089 battery
IBM Thinkpad 390 Series battery
IBM Thinkpad 390X battery
IBM ThinkPad Z61m Battery
IBM 02K7018 Battery
IBM thinkpad t41p battery
IBM THINKPAD T42 Battery

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

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