31 January 2009

Boosting, neural networks and deep learning

I'm on a neural networks kick of late, apparently.

The following was pointed out to me recently. Maybe other people think it's obvious, and it's obvious once you hear it, but I'd never seen it that way. Suppose we're doing boosting and the weak learner that we choose is a thresholded linear model (eg., perceptron, SVM, logistic regression). Then what we get out of boosting is basically a neural network with a single hidden unit. The hidden units themselves are the weak learners, and the "alphas" that arise as part of the boosting procedure (eg., AdaBoost) are the weights connecting the hidden units to the output. (Thanks to Antonio Paiva for pointing this out to me.) So, in a sense, boosting a linear model can be seen as a kind-of-unusual method for training a two layer network. Essentially the number of boosting iterations that you run determines the number of hidden units (i.e., the network architecture).

Okay, that's great. But let's say we don't care about two layer networks, we care about deep learning. For a 3-layer network you could simple boost boosted-linear-models. For a 4-layer network you could boost boosted-boosted-linear models. And so on.

Is there an alternative?

Thinking purely procedurally, let's say my weak learner is a linear model. I start boosting and I've got 5 linear models trained in the standard AdaBoost manner. Now I have a choice. Should I train a 6th linear model to throw in to the standard boosting set? Or should I treat the 5 boosted linear models as a new base classifier and boost against the combination? If I choose the latter, I've now gone from two layers to three layers.

Why might it be a good idea to boost against the 5 collectively? Well, if you believe the whole deep learning propaganda, then it's a good idea because deep = good. From a more theoretical perspective, you might how that the extra level of recursion might get you an increased rate of improvement in the error rate. I.e., the recursion could potentially lead to stronger boosting results than the standard linear boosting. Of course, this is just a hunch: I haven't at all looked to try to figure out if it would actually work in theory. But it seems plausible. For instance, in neural networks theory, we know that a 2 layer network can approximate any (reasonable) function, but you might need an exponential number of hidden units; the number of required hidden units goes down if you make deeper networks (under assumptions).

Of course, maybe someone's already done this, maybe it doesn't work, and maybe it's a stupid idea :).

32 comments:

Peter Turney said...

The algorithm you describe reminds me a bit of Cascade Correlation.

Yoshua said...

The connection between boosted linear classifiers and one-hidden-layer neural networks has been studied in the past. See for example the NIPS'2005 paper on Convex Neural Networks
http://www.iro.umontreal.ca/%7Elisa/publications/index.php?page=publication&kind=single&ID=19

which shows that by successively adding the optimal linear classifier (as a weak learner) one could in principle find the global optimum of a 1-hidden layer neural net. Unfortunately, finding the optimal linear classifier is NP-hard. But more importantly, I agree that 1-hidden layer nets are not satisfying because they are too shallow.

I'm not sure I really understood your idea with 5 linear models and a 6th one added in such a way as to increase depth. To increase depth, the 6th one should see in its inputs the outputs of the previous ones. As noted by Peter Turney, this would turn the algorithm into something similar to Cascade Correlation. But looking back onto the goals and motivations of deep learning algorithms, something important would be missing: the discovery of intermediate representations that capture the variations in the input. But something else might be missing: the unsupervised component. Purely supervised greedy addition of layers does not work as well as unsupervised addition of layers, according to the experiments described in the NIPS'2006 paper by Bengio et al on Greedy Layerwise Training of Deep Networks (http://www.iro.umontreal.ca/%7Elisa/publications/index.php?page=publication&kind=single&ID=190). The authors conjectured that purely supervised greedy addition of layers was simply too greedy, not keeping enough of the input information (the part that cannot be exploited yet by a linear classifier but could be exploited later when more layers are added).


-- Yoshua Bengio

Joseph Turian said...

Another work which uses boosting to add units to an MLP is Grafting: Fast, Incremental Feature Selection by Gradient Descent in Function Space.

As Yoshua indicated, though, the main difficulty in inducing a deep architecture is that a purely supervised signal does not seem sufficient to guide the optimization to a good minimum.

hal said...

Yoshua's comment is definitely apt and one that I had sort of forgotten about when writing. The unsupervised aspect of getting things rolling in deep nets definitely seems to be super important. I don't know how to fix this :).

cutepig said...

Many people want to in the game had more archlord gold, but in the end always do not come true, so only relp on buy archlord gold, so for the students this is a big different, so we all need the cheap archlord gold, so we all hope.

. said...

酒店經紀PRETTY GIRL 台北酒店經紀人 ,禮服店 酒店兼差PRETTY GIRL酒店公關 酒店小姐 彩色爆米花酒店兼職,酒店工作 彩色爆米花酒店經紀, 酒店上班,酒店工作 PRETTY GIRL酒店喝酒酒店上班 彩色爆米花台北酒店酒店小姐 PRETTY GIRL酒店上班酒店打工PRETTY GIRL酒店打工酒店經紀 彩色爆米花

Taylor Party, Wedding said...

I wanted to thank you for this great read!! I definitely enjoying every little bit of it :) I have you bookmarked to check out new stuff you post. Please visit my Please visit my blog when you have time Please come visit my site
http://www.partyrockstars.com
Chicago Business Directory
when you got time.

Party Planning Services, Event Planning Rental, Wedding Rentals said...

I am not much into reading, but somehow I got to read lots of articles on your blog.
Its amazing how interesting it is for me to visit you very often :)
Please come visit my site
http://www.partyrockstars.com
Chicago Business Directory
when you got time.

frozen ice cream desserts said...

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

酒店上班請找艾葳 said...

艾葳酒店經紀公司提供專業的酒店經紀, 酒店上班小姐,八大行業,酒店兼職,傳播妹,或者想要到打工兼差打工,兼差,或者八大行業,酒店兼職,想去酒店上班, 日式酒店,制服酒店,ktv酒店,禮服店,整天穿得水水漂漂的,還是想去制服店上班小姐,水水們如果想要擁有打工工作、晚上兼差工作兼差打工假日兼職兼職工作酒店兼差兼差打工兼差日領工作晚上兼差工作酒店工作酒店上班酒店打工兼職兼差兼差工作酒店上班等,想了解酒店相關工作特種行業內容,想兼職工作日領假日兼職兼差打工、或晚班兼職想擁有快速賺錢又有保障的工作嗎???又可以現領請找專業又有保障的艾葳酒店經紀公司!

艾葳酒店經紀是合法的公司工作環境高雅時尚,無業績壓力,無脫秀無喝酒壓力,高層次會員制客源,工作輕鬆,可日領現領
一般的酒店經紀只會在水水們第一次上班和領薪水時出現而已,對水水們的上班安全一點保障都沒有!艾葳酒店經紀公司的水水們上班時全程媽咪作陪,不需擔心!只提供最優質的酒店上班,酒店上班,酒店打工環境、上班條件給水水們。心動嗎!? 趕快來填寫你的酒店上班履歷表

水水們妳有缺現領、有兼職缺錢卡奴的煩腦嗎?想到日本留學缺錢嗎?妳是傳播妹??想要擁有高時薪又輕鬆的夜間兼職工作,打工機會和,假日打工,假日兼職賺錢的機會嗎??想實現夢想卻又缺錢沒錢嗎!??
艾葳酒店台北酒店經紀招兵買馬!!徵專業的酒店打工,想要去酒店的水水,想要短期日領,酒店日領,禮服酒店,制服店,酒店經紀,ktv酒店,便服店,酒店工作,禮服店,酒店小姐,酒店經紀人,
等相關服務 幫您快速的實現您的夢想~!!

yi said...

Hello, everybody. I am a new hand to be here. So nice to meet you all. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

tariely said...

Классный фильм на кинозоуне.
электронная почта без регистрации

Anonymous said...

электронная почта без регистрации

gamefan12 said...

Your blog is so amazing. You definitely put a great insight into this. Keep up the good work.
boca raton cosmetic dentist

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

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

Sinan said...

Thanks so much for this! This is exactly what I was looking for bedava chat - sohbet odaları - sohbet - islami chat - sohbet siteleri - mynet sohbet - garanti arkadaş - islami sohbet - mirc sohbet - sohbet indir - mirc script indir - bedava sohbet - - cinsel muhabbet - dini sohbet - gay sohbet - cinsel sohbet - seviyeli sohbet - porno sohbet - kameralı sohbet - cinsellik sohbet - sex chat - mirc - mirc indir - kamerali mirc - turkce mirc - sohbet siteleri - cet - Video izle - sohbet - Muhabbet - sohbet siteleri - kızlarla sohbet - - kızlarla sohbet - chat kanalı - chat kanalları - sohbet kanalı - sohbet kanalları

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

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

combattery84 said...

IBM ThinkPad R60 Battery
IBM ThinkPad T60 Battery
IBM ThinkPad T41 Battery
IBM ThinkPad T43 Battery
IBM ThinkPad X40 Battery
Thinkpad x24 battery
ThinkPad G41 battery
IBM thinkpad r52 battery
Thinkpad x22 battery
IBM thinkpad t42 battery
IBM thinkpad r51 battery
Thinkpad r50 battery
IBM thinkpad r32 battery
Thinkpad x41 battery
SONY VGP-BPS2 Battery
SONY VGP-BPS2C Battery
SONY VGP-BPS5 battery
SONY VGP-BPL2C battery
SONY VGP-BPS2A battery
SONY VGP-BPS2B battery
SONY PCGA-BP1N battery
SONY PCGA-BP2E battery
SONY PCGA-BP2NX battery
SONY PCGA-BP2S battery
SONY PCGA-BP2SA battery
SONY PCGA-BP2T battery
SONY PCGA-BP2V battery
SONY PCGA-BP4V battery
SONY PCGA-BP71 battery
SONY PCGA-BP71A battery
SONY VGP-BPL1 battery
SONY VGP-BPL2 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

King Bayern Munich said...

This is a great article, supplies the useful information for me, thanks in this
pressure relief valve|forged Steel valve|butterfly valves|dustbin

King Bayern Munich said...

This is a great article, supplies the useful information for me, thanks in this
pressure relief valve|forged Steel valve|butterfly valves|dustbin

King Bayern Munich said...

This is a great article, supplies the useful information for me, thanks in this
pressure relief valve|forged Steel valve|butterfly valves|dustbin

King Bayern Munich said...

This is a great article, supplies the useful information for me, thanks in this
pressure relief valve|forged Steel valve|butterfly valves|dustbin

Anonymous said...

Southeast pandora jewelry and main Asian countries have twisted pandora bracelets rubies for centuries, but research as to where, cheap pandora charms and how to find more deposits is spare, and production has figured out how pandora uk and mining companies,” Giuliani says, pandora sale to look at exactly the right time and place.Farther cheap pandora investigation of claret formation, based on tectonic scenery, geochemistry, buy pandora fluid inclusions and isotopic ratios, allowed Giuliani’s lineup to remodel a new prototype pandora bracelets uk for the French Institute of Research for Development (IRD) and the National Scientific cheap pandora bracelets Center of Research, two government-sponsored knowledge and technology research pandora bracelets sale institutes that aim to aid in the sustainable pandora bangles development of developing countries.Before the collision of the Eurasian and Indian plates, cheap pandora bangles lagoons or deltas sat in the regions where marble is giant, he says, “and there is the brains pandora necklace to expect that the new thoughts should help development of the artless capital.”

Anonymous said...

contact | profile feedback: 260 | 100% | increasingly ed hardy shoes joined on: 04/15/09 status: Pittsburg,Zumba Fitness, KS Real ed hardy shoes canadae Conversation aqua_angels is gang offonly. Renthusiastic Items Items 127 items in Booth Top Ed Hardy Shoes Catself-confidenceries Jewelry & Watches,Christian Louboutin Knockoffs, Cloweakg,Tory Burch Thora Wedge, Shoes & Accessories,Christian ed hardy clothing Louboutin Wedges, Navel Rings My Cart Rstopewhite at 23:49:50 Home ? Buy ? aqua_angels' booth ? Animie Kona culture bag tote purse NWT canvas EMO
Click do whatever they want on weather to close Click a weather to enlarge Animie Kona costume bag tote purse NWT canvas EMO
$5.24 OBO 1 in stock CHECKOUTNo pre-registration requiwhite. Zoom! SHIPPING ed hardy outlet PRICE SHIPS WITHIN1-2 trade locations PAY WITH CATEGORYOther REVIEWSSpleasant to the earch Amazon on product reviews Item Specifics Color: Multi Color | Theme: Character | heme: Character | Condition: New | Fabric: Nylon This item has exhilarationn added to your cart Animie Kona costume bag tote purse NWT canvas EMO
Only one available in stock

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

Anonymous said...

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

Anonymous said...

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

Anonymous said...

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

Anonymous said...

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