« 宣伝 | Main | ベンチャーの興し方 PFI編 »

2009.02.25

レコメンド, LSH, Spectral Hashing

WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。

内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。

個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。

レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル(数百万次元とか)で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積(各ベクトルは長さ1に正規化されているとする)が最大となるようなベクトルを探して来いという問題になります。

この問題は結構厄介な問題で、近似無で解くには、索引(たとえばkd-treeや最新のcover tree)を作っても高次元の場合にはうまくいかないことが知られています。

これを近似有で高速に解こうというのがLSHを使った近傍検索です。LSHでは、高次元ベクトルを20~60bit程度のベクトルに写像するのですが、通常のhash関数はランダムに飛ばすのに対し、LSHは写像した先で内積をとっても、元のベクトルで内積をとったのと同じようになることが保障されているような関数になってます。似たベクトル同士は飛ばした先でも似たままで、似てないベクトル同士は飛ばした先でも似てないままです。

短いbitにさえ落してしまえば問題は簡単になります。例えば1回の内積の演算は数回のbit演算で解けますし、bit毎の転置ファイルなどいろんな索引を作って適当に枝狩りしながら探索するのも容易になります。

本ではLSHの作り方やその原理などを説明していたりするので興味のある方はみてみてください。

高度な話になってしまうため、本では書けなかったのですが、今LSHではSpectral Hashingが面白いです。
Y. Weiss, et. al. "Spectral Hashing", NIPS 2008 pdf

Spectral Hashingではよい写像を求める問題を制約付の最適化問題に帰着して解いています。制約それぞれは元の距離を保存する、各位置のbitは相関がない、写像後の符号では0と1が同程度出現するとかいったものに対応しています。この最適化問題はグラフ分割問題と同じでありNP完全ですが、緩和させて主成分分析をちょっと変更したものでとけます。

論文では8000万枚の画像tinyimagesを実験として使ってhashして似た画像を見つける例がのっていますが、ここまででかくなると、人の能力を超えている感じがしていいですね。

|

« 宣伝 | Main | ベンチャーの興し方 PFI編 »

Comments

こんにちは!
最近データマイニングを勉強しはじめたNyahatです。
さっそくWeb DB Press v49を買いました!!
難しいです(汗

ところで、疑問に思った点が2つあります。

1.8000万枚の画像tinyimagesとありますが、
これは画像の色や形をなんとなく分類しているのでしょうか?
多分、分類機の肝は特徴ベクトルをどう作るかだと思ったので、特徴が色や形を漠然と特徴として捉えるか、それとも「これは顔」「これは建物」というように抽象化した意味を抽出してから分類するのでは、精度が違う様な気がします。
もちろん意味の自動抽出はまだまだ研究途中で難しいと思いますが・・。

2.もう一つは、データや文章のクラスタリングは今の技術ではこれ以上精度を上げられないと思っています。
それは、文法とかを理解させることはできるかもしれませんが、結局「おもしろい話の分類」とか「うならせる科学分析のレポート」などは人間レベルの知能と経験を実現させないと分類させられないような気がしました。
なので、こういった技術が、記事分類や(服や本の)レコメンド以外に使われるニーズはあるのだろうかと考え込んでしまいます。
だからといってロボットのニーズがあるわけではないし、監視カメラとかの自動認識のニーズだってそんな大きくはないと思います。
こういった人工知能的な技術がブレークスルーするためのニーズがわからないのですが、どう思いますか?

Posted by: nyahat | 2009.02.27 at 09:28 PM

tinyimagesについては
http://people.csail.mit.edu/torralba/tmp/tiny.pdf
の論文に詳細があります。
このプロジェクトのコンセプトを簡単にいうと、ものすごい数の画像が集められるようになったので、それらに対して周辺のスニペットを利用したり、人手で正解をつけて意味を与えてやれば、世の中のほとんどの画像に対して、DB中の一番近い画像を見つけて、その画像の意味を使って、画像の意味付けができるのではないかというものです。特徴ベクトル(画素間の距離)については一般的なものを利用しているとおもいます(小さい画像に特化はしているが)

2番目の話題については精度とニーズに問題を分けたほうがよさそうです。

>これ以上精度を上げられないと思っています。

人間にとて面白そうだ、とかで分けるのはまだ難しいですが、それ以外、例えばトピックで分けたり、話しの観点(好意的か否定的か)、書いている人のスタンスの分類などで分けるのはある程度精度がでて、これからも精度は伸びていくとおもいます
研究分野として最近でてきて面白そうなのは、オントロジーのように木のように意味が階層的に分類されていて、それにマッピングする問題とかです

認知的な部分で意味を理解して分けるのはまだ難しいと思います。読んでいる人の背景知識などにもよってきますし。パーソナライズ化されたレコメンデーションなら疑似的に実現できるでしょう

で、二番目のニーズがあるかということについてはあると考えてます。これだけwebサービスが普及して、いろんな企業がログデータをため込んでいるのですが、それを活用して成功しているのはそれほど多くありません。
ただ、それがビジネス的に成功するかは純粋な技術力に加えて、見せ方とかタイミングとかいろんなものが絡んでくると思います。ただ、市場としてはこれからも大きくなるのは間違いないと思いますよ。

Posted by: oka | 2009.03.09 at 03:25 AM

返信ありがとうございます。
13日の講演を聴きに行きたかったのですけれど、仕事が休めそうにありません。

私は恋率というサイトを作ってたら、あとでテキストまイニングっぽくなっていることに気づき、確率の勉強をし始めた次第です。
恋率を公式サイトにしたくて、いろいろ企業とかけあったのですけれど駄目でした。
ビジネスにするって事の難しさを知った時でした。
でも、これに負けじと頑張りたいと思います。

Posted by: Nyahat | 2009.03.10 at 06:46 PM

ugg 公式通販 レストラン、美術館、ホテル、小売店舗ライン歩道。バッグを借りるか盗むは、しばしば、財布を借りて会社略してに時間の長い期間。だから、ヒントにする方法スポット模倣ルイ ・ ヴィントン ハンドバッグ本当にですか? グアム ugg

Posted by: ugg 公式通販 | 2013.11.24 at 08:05 PM

Ι trailed her оon Faceƅooҡ and discovered myself aghast at her actіons. One pooular guideline is definitely that students shouldn't post anything thing they wouldn't want their parents yyou just read; given that many adults arе employing Fɑcebook, youг mother and ather migɦt litеrall bbе reeading еvery status updatе. In the nonprofit sector, relationships are absolutely critical to the success of ann organization.

Posted by: share images | 2014.03.11 at 06:21 PM

Wow, awesome blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is great, let alone the content!

Posted by: Ross Lynch phone number | 2014.05.24 at 08:27 AM

I go to see daily some websites and sites to read content, except this website presents quality based writing.

Posted by: Taylor Swift Phone Number | 2014.05.24 at 07:26 PM

Hi! This is my first comment here so I just wanted to give a quick shout out and say I truly enjoy reading your articles. Can you recommend any other blogs/websites/forums that deal with the same subjects? Thank you!

Posted by: Louis Tomlinson Phone Number | 2014.05.26 at 07:03 AM

Greetings! I know this is kind of off topic but I was wondering which blog platform are you using for this site? I'm getting tired of Wordpress because I've had issues with hackers and I'm looking at options for another platform. I would be great if you could point me in the direction of a good platform.

Posted by: One Direction Phone Numbers | 2014.06.12 at 06:03 PM

Hi! This is kind of off topic but I need some guidance from an established blog. Is it very hard to set up your own blog? I'm not very techincal but I can figure things out pretty quick. I'm thinking about making my own but I'm not sure where to start. Do you have any points or suggestions? Cheers

Posted by: comment jouer fifa 14 en ligne | 2014.06.18 at 03:30 AM

However, it is difficult to arrange such pompous occasion as you invite lots of guests. You will be stunning, your own bridal diamond jewelry will improve that. A single flower or a cluster of delicate blooms can add a touch of romance to your hairstyle.

Posted by: testing.fintool.ch | 2014.08.13 at 10:56 PM

I know this web page gives quality dependent content and other information, is there any other web site which provides these data in quality?

Posted by: Tiara | 2014.08.15 at 12:23 AM

When I initially left a comment I seem to have clicked on the -Notify me when new comments are added- checkbox and now each time a comment is added I recieve 4 emails with the same comment. Is there a way you can remove me from that service? Kudos!

Posted by: Demetrice | 2014.08.17 at 12:40 PM

My coder is trying to convince me to move to .net from PHP. I have always disliked the idea because of the costs. But he's tryiong none the less. I've been using Movable-type on numerous websites for about a year and am nervous about switching to another platform. I have heard very good things about blogengine.net. Is there a way I can transfer all my wordpress content into it? Any help would be really appreciated!

Posted by: Lou | 2014.09.04 at 09:47 AM

My partner and I stumbled over here coming from a different website and thought I might check things out. I like what I see so now i am following you. Look forward to looking into your web page for a second time.

Posted by: vacation | 2014.09.08 at 11:21 AM

I must thank you for the efforts you've put in penning this site. I am hoping to see the same high-grade content from you later on as well. In truth, your creative writing abilities has encouraged me to get my very own website now ;)

Posted by: tony hawk net worth | 2014.09.14 at 09:11 AM

Small boutiques and dress shops tend to stock dress samples. They have a range of elegantly designed wedding dresses to choose from that are sure to be in your budget. It is important that you feel good while wearing the gown.

Posted by: planet326.dothome.co.kr | 2014.10.08 at 10:05 PM

At this time I am ready to do my breakfast, afterward having my breakfast coming again to read further news.

Posted by: pdeleusse.free.fr | 2014.10.16 at 03:27 PM

My family every time say that I am wasting my time here at web, except I know I am getting familiarity every day by reading thes nice posts.

Posted by: reebok dumbbell adjustable | 2014.10.21 at 08:40 AM

Asking questions are in fact fastidious thing if you are not understanding something totally, but this post gives nice understanding yet.

Posted by: see this | 2014.11.09 at 05:21 AM

Admiring the dedication you put into your site and detailed information you offer. It's good to come across a blog every once in a while that isn't the same out of date rehashed material. Great read! I've bookmarked your site and I'm adding your RSS feeds to my Google account.

Posted by: http://szybkierandki24.pl | 2014.11.10 at 08:41 AM

If you wish to give a game a try, the library may have a copy. Anytime your children wish to join an online site, be sure you review it in advance. So that they can understand our selves, we need to first understand Unlimited Treasures for Clash of Clans.

Posted by: clash of clans triche | 2015.04.22 at 10:03 PM

The efficacy should easily satisfy U.S. Food and Drugg Administration weight loss drug criteria, leaving safety as the main hurdle to approval.

Posted by: diabetes cure to end jabs | 2015.05.06 at 06:20 PM

I was suggested this blog by my cousin. I'm not sure whether this post is written by him as nobody else know such detailed about my trouble. You're wonderful! Thanks!

Posted by: cracker un mot de passe winrar | 2015.05.09 at 03:20 PM

The best part of the busy ones are actually more great for Windows Phone 7To begin tracing the simpsons tapped out hack your Windows or Xbox 360 exclusive that brings buyers and to function. However for facebook one need not efficient to build the gap between home consoles too.

Posted by: the simpsons tapped out cheats | 2015.05.11 at 06:13 AM

Moreover, there are no more treated only as a horizontal line should be kept in mind the purpose of cell phone is it can give you hours of gameplay. The side air bag deployed, but because of the best Mobile Phone NumberGetting a virtual place. Get 30 *New* High Page Rank Backlinks.

Posted by: Ashlee | 2015.05.12 at 05:57 AM

If you wish for to improve your knowledge only keep visiting this website and be updated with the most up-to-date gossip posted here.

Posted by: choosing a roofing system | 2015.05.12 at 06:39 PM

You're so cool! I don't suppose I've read through something like this before. So good to discover another person with unique thoughts on this subject matter. Really.. many thanks for starting this up. This web site is one thing that is required on the web, someone with a bit of originality!

Posted by: long term pet care | 2015.05.13 at 10:14 AM

Hi Dear, are you in fact visiting this website on a regular basis, if so afterward you will definitely obtain good knowledge.

Posted by: residential steel roofing Greenville | 2015.05.13 at 03:44 PM

all the time i used to read smaller content that as well clear their motive, andd that is also happening with this piece of writing which I am reading at this time.

Posted by: paid to take surveys | 2015.05.14 at 01:42 PM

Hello there! Would you mind if I share your blog with my facebook group? There's a lot of folks that I think would really appreciate your content. Please let me know. Cheers

Posted by: get paid surveys | 2015.05.14 at 04:30 PM

Hello there, You've done a fantastic job. Iwill definitely digg it and personaally recommend to my friends. I'm confident they'll be benefited from this site.

Posted by: paid for online surveys | 2015.05.15 at 12:01 PM

Admiring the commitment you put into your website and in depth information you offer. It's good to come across a blog every once in a while that isn't the same outdated rehashed information. Wonderful read! I've saved your site and I'm including your RSS feeds to my Google account.

Posted by: top dating websites | 2015.05.15 at 12:18 PM

fine, here's the scoop: I simply got my blood work back... So that as I suspected, It was NEGATIVE for everyone STD's!!!

Posted by: herpes natural cure | 2015.05.18 at 06:35 AM

Greetings! This is my first visit to your blog! We are a group of volunteers and starting a new project in a community in the same niche. Your blog provided us valuable information to work on. You have done a outstanding job!

Posted by: it solutions Lake Oswego | 2015.05.18 at 11:41 AM

I do not know if it's just me or if everyone else experiencing issues with your site. It appears as if some of the written text on your posts are running off the screen. Can someone else please comment and let me know if this is happening to them too? This may be a issue with my web browser because I've had this happen before. Cheers

Posted by: redirected here | 2015.05.20 at 01:17 PM

Hello there, I believe your web site might be having browser compatibility problems. When I look at your web site in Safari, it looks fine however, when opening in Internet Explorer, it's got some overlapping issues. I simply wanted to provide you with a quick heads up! Other than that, fantastic site!

Posted by: you could try these out | 2015.05.23 at 10:25 AM

Будто сбросить лишний вес с помощью шоколада? Сладкоежки, желащие похудеть, слим шоколад для похудения отзывы понимают, как сильной становится тяготение к лакомствам, когда ей оглашается бой. и все же имеется возвожность баловать себя сладким и сразу освобождаться от жирных отложенией - шоколад про похудения ChocolateSlim сбивает противоречие меж, на первый взгляд, несовместимыми багажами. Чтоб заказать Шоколад для заполните фигуру и надавите кнопку "Выписать". С вами свяжется свой менеджер про уточнения условий доставки Состав и полезные свойства Шоколадное дерево.Основным компонентом любого шоколада является шоколадное дерево. Нежели его более, другими словами, нежели чернее шоколадка, тем лучше. В какао держатся препарата, коие благоприятно влияют на службу сердечно-сосудистой системы и нормализуют давление. недавно шпанские эксперты провели исследование, дотрагивающееся капиталом самочувствия молодых людей от 12 до 17, коие держались разнообразных диет и вели здравый стиль жизни. В результате оказалось, что у ценителей шоколада количество жировых отложений было существенно ниже, чем около других. Объясняется таковым, что шоколад убыстряет стиль. Даже невзирая на высшую калорийность, дьявол мешает способности жиру осесть в организме в качестве отложений. А также одно интересное наблюдение.

Posted by: слим шоколад для похудения отзывы | 2015.05.24 at 07:16 AM

Family Christmas Fun - Activity #2 : Making Christmaas Keepsakes: These tiles can last though many Christmases, can be made as ornaments by securing a bail loop on the back with glue and a hook to hng from your Christmas tree, or a simlpe chain necklace to thread through the bail. Thiis craft project might be a bit tricky for younger children due tto spraying paint, so thery might neeed adult help or supervision. It is much thee same as rayoon thread but less expensive and more resilient.

Posted by: christmas craft | 2015.05.27 at 02:47 AM

This way, every single day. A game with iPhone, Droid phone, providing hours of gaming to users so that you don't miss important news while busy typing. Different from the sims freeplay cheats the popular Disney character is very necessary to vanish tensions and frustrations.

Posted by: sims freeplay cheats | 2015.05.28 at 01:34 AM

Hi there, i read your blog from time to time and i own a similar one and i was just wondering if you get a lot of spam comments? If so how do you protect against it, any plugin or anything you can suggest? I get so much lately it's driving me crazy so any support is very much appreciated.

Posted by: RusselPZertuche | 2015.06.07 at 06:17 PM

Years ago when so many anglers used milk protein baits these were mostly used in small amounts because they normally worked very fast and effectively compared to other baits of the time and it was just not necessary to pile in loads and loads of bait to catch loads of big fish. Also on-board the Bolt concept car is advanced driver assist features like an automated park-and-retrieval system where the car parks itself in a parking garage, and retrieves itself via a smart phone app. Don't try to do more than you are physically able to do.

Posted by: www.metta.org.uk | 2015.06.17 at 03:38 PM

Yes! Finally something about soundcloud promotion.

Posted by: buy soundcloud plays | 2015.08.22 at 12:05 AM

So this 2014 $140 present card is offered online.

Posted by: where can i buy dry ice in las vegas | 2015.09.27 at 11:25 AM

at a later time, an off cycle of three to six many months excellent for, and HGH output should persist accurately expensive do your best. Dieting high in protein foods, now and again physically demanding work-out, as well as enduring sleep all have fun playing keeping a positive job inside of the raw manufacture of HGH. however fresh idea made possible the man to delve into maturing similar problems with but, HGH injections are extremely expensive so they could make you use around $15000 longer period. Dental HGH is also deemed into dental hair sprays and tablets which come in product mode. Oral hair sprays do not work referring to because HGH could a huge and precarious molecule that can't go through the membranes within just your jaws. Wrinkles sufferers were originally beachfront look HGH drugs inserted into their muscle. locate on the best place to decide to purchase hgh online If also you would like an awesome web host go to The Sytropin HGH squirt increase is supplied void of any solutions; so far gets the hp 12c financial calculator's very high quality. Body Hgh must be created as anything meant to totally raise GH and libido,Optimize insulin shots sensitivity, improve healthy proteins synthesis, Up-regulate IGF-1 and additional growth points, expand nitric oxide supplement Performance, lower cortisol plus, crush myostatin. anatomy fit and healthy for Some users explained, HGH releaser sprinkle was soon the best choice for the children, some replied HGH Releaser pills was beneficial on their behalf. HGHAdvanced is very much an HGH releaser that hold the majority parts in control of extending the world's quantity purely natural GH - which helps in rising muscular tissues, bodybuilding and boosting matabolic activity. Unlike threatening HGH injections, Avatropin doesn't hang unnatural HGH in the setup.

Posted by: hgh secrets | 2015.09.29 at 12:05 PM

You can not buy a cash order with a bank card.

Posted by: where can i buy kitchenware online | 2015.10.15 at 06:11 AM

Hello! Quick question that's completely off topic. Do you know how to make your site mobile friendly? My website looks weird when browsing from my iphone4. I'm trying to find a template or plugin that might be able to correct this problem. If you have any suggestions, please share. Appreciate it!

Posted by: sewer line replacement | 2016.01.24 at 04:13 AM

This paragraph will help the internet viewers for creating new weblog or even a blog from start to end.

Posted by: sewer line | 2016.01.24 at 02:04 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/44175159

Listed below are links to weblogs that reference レコメンド, LSH, Spectral Hashing:

» [レコメンド][IT]WEB+DBプレスの「[速習]レコメンドエンジン」を訂正してみる [遙かへのスピードランナー]
プリファードインフラストラクチャーのid:tkngさんと岡野原さんがWEB+DBプレスvol.49に「[速習]レコメンドエンジン」という記事を書かれています。 WEB+DB PRESS Vol.49posted with amazlet at 09.03.08技術評論社 売り上げランキング: 359Amazon.co.jp で詳細を見る レコメ... [Read More]

Tracked on 2009.03.08 at 03:30 AM

« 宣伝 | Main | ベンチャーの興し方 PFI編 »