Posted in Khác

Introduction to Latent Dirichlet Allocation

Latent Dirichlet Allocation – Blei & Ang & Jordan , JMLR 2003

Introduction

Giả sử bạn có một tập các câu sau đây :

  • I like to eat broccoli and bananas.
  • I ate a banana and spinach smoothie for breakfast.
  • Chinchillas and kittens are cute.
  • My sister adopted a kitten yesterday.
  • Look at this cute hamster munching on a piece of broccoli.

Thế thì LDA là gì ? Đó là một cách từ động khám phá ra các topics mà các câu trên chứa. Ví du, cho các câu trên và yêu cầu cho 2 topics, LDA có thể sinh ra một kết quả như kiểu này :

  • Sentences 1 and 2: 100% Topic A
  • Sentences 3 and 4: 100% Topic B
  • Sentence 5: 60% Topic A, 40% Topic B
  • Topic A: 30% broccoli, 15% bananas, 10% breakfast, 10% munching, … ( tại điểm này , bạn có thể diễn tả topic A là về food)
  • Topic B: 20% chinchillas, 20% kittens, 20% cute, 15% hamster, … (tại điểm này , bạn có thể diễn tả topic B là về cute animals)

Làm thế nào để LDA có thể thực hiện được điều này ?

LDA Model

Chi tiết hơn , LDA miêu tả các văn bản như là sự pha trộn của các topics that spit out words với các xác suất nhất định . Nó giả sử các văn bản được tạo ra theo cách sau : khi bạn viết mỗi văn bản , bạn

  • Quyết định số lượng từ N mà document sẽ có ( theo một phân phối Poisson )
  • Chọn một chủ đề hỗn hợp cho document này (theo một phân phối Dirichlet trên một tập hợp cố định K chủ đề). Ví dụ , giả sử bạn có hai topics bên trên : food và cute animal , bạn có thể chọn rằng document này sẽ bao gồm 1/3 food và 2/3 cute animals.
  • Generate each word w_i trong document này bằng cách:
    • Đầu tiên là chọn một topic (theo phân phối đa thức mà bạn đã láy ví dụ bên trên , ví dụ , bạn có thể chọn food topic với xác suất 1/3 và cute animals topic với xác suất 2/3).
    • Sử dụng topic để sinh ra các từ (theo phân phối của topic’s multinomial). Ví dụ , nếu bạn chon food topic , bạn có thể sinh ra được các từ “broccoli” với xác suất 30% , “bananas” với xác suất 15% , và cứ thế …

Giả sử this generative model này cho một tập hợp các documents , LDA sau đó cố gắng để quay lui (backtrack) từ các tài liệu để tìm thấy một tập hợp các chủ đề mà rất có thể đã tạo ra collection .

Example

Ví dụ . Tuân theo quy trình bên trên , khi sinh ra một số document D cụt hể , bạn có thể :

  • Chọn 5 là số lượng từ trong D.
  • Quyết định rằng D sẽ là 1/2 về food và  1/2 về cute animals.
  • Chọn từ đầu tiên trong food topic , và bạn sẽ có từ “broccoli”.
  • Chọn từ thứ hai tới từ cute animals topic, bạn sẽ có “panda”.
  • Chọn từ thứ 3 tới từ cute animals topic , sẽ cho bạn từ “adorable”.
  • Chọn từ thứ tư tới từ food topic, sẽ cho bạn từ “cherries”.
  • Chọn từ thứ năm tới từ food topic, sẽ cho bạn từ “eating”.

Như thế document được sinh ra từ LDA sẽ là  “broccoli panda adorable cherries eating” (ghi nhớ rằng LDA là a bag-of-words model).

Learning

Giả sử bạn đã có tập các documents. You’ve chosen some fixed number of K topics to discover, and want to use LDA to learn the topic representation of each document and the words associated to each topic. How do you do this? One way (known as collapsed Gibbs sampling) is the following:

  • Go through each document, and randomly assign each word in the document to one of the K topics.
  • Notice that this random assignment already gives you both topic representations of all the documents and word distributions of all the topics (albeit not very good ones).
  • So to improve on them, for each document d…
    • Go through each word w in d…
      • And for each topic t, compute two things: 1) p(topic t | document d) = the proportion of words in document d that are currently assigned to topic t, and 2) p(word w | topic t) = the proportion of assignments to topic t over all documents that come from this word w. Reassign w a new topic, where we choose topic t with probability p(topic t | document d) * p(word w | topic t) (according to our generative model, this is essentially the probability that topic t generated word w, so it makes sense that we resample the current word’s topic with this probability). (Also, I’m glossing over a couple of things here, in particular the use of priors/pseudocounts in these probabilities.)
      • In other words, in this step, we’re assuming that all topic assignments except for the current word in question are correct, and then updating the assignment of the current word using our model of how documents are generated.
  • After repeating the previous step a large number of times, you’ll eventually reach a roughly steady state where your assignments are pretty good. So use these assignments to estimate the topic mixtures of each document (by counting the proportion of words assigned to each topic within that document) and the words associated to each topic (by counting the proportion of words assigned to each topic overall).

Layman’s Explanation

In case the discussion above was a little eye-glazing, here’s another way to look at LDA in a different domain.

Suppose you’ve just moved to a new city. You’re a hipster and an anime fan, so you want to know where the other hipsters and anime geeks tend to hang out. Of course, as a hipster, you know you can’t just ask, so what do you do?

Here’s the scenario: you scope out a bunch of different establishments (documents) across town, making note of the people (words) hanging out in each of them (e.g., Alice hangs out at the mall and at the park, Bob hangs out at the movie theater and the park, and so on). Crucially, you don’t know the typical interest groups (topics) of each establishment, nor do you know the different interests of each person.

So you pick some number K of categories to learn (i.e., you want to learn the K most important kinds of categories people fall into), and start by making a guess as to why you see people where you do. For example, you initially guess that Alice is at the mall because people with interests in X like to hang out there; when you see her at the park, you guess it’s because her friends with interests in Y like to hang out there; when you see Bob at the movie theater, you randomly guess it’s because the Z people in this city really like to watch movies; and so on.

Of course, your random guesses are very likely to be incorrect (they’re random guesses, after all!), so you want to improve on them. One way of doing so is to:

  • Pick a place and a person (e.g., Alice at the mall).
  • Why is Alice likely to be at the mall? Probably because other people at the mall with the same interests sent her a message telling her to come.
  • In other words, the more people with interests in X there are at the mall and the stronger Alice is associated with interest X (at all the other places she goes to), the more likely it is that Alice is at the mall because of interest X.
  • So make a new guess as to why Alice is at the mall, choosing an interest with some probability according to how likely you think it is.

Go through each place and person over and over again. Your guesses keep getting better and better (after all, if you notice that lots of geeks hang out at the bookstore, and you suspect that Alice is pretty geeky herself, then it’s a good bet that Alice is at the bookstore because her geek friends told her to go there; and now that you have a better idea of why Alice is probably at the bookstore, you can use this knowledge in turn to improve your guesses as to why everyone else is where they are), and eventually you can stop updating. Then take a snapshot (or multiple snapshots) of your guesses, and use it to get all the information you want:

  • For each category, you can count the people assigned to that category to figure out what people have this particular interest. By looking at the people themselves, you can interpret the category as well (e.g., if category X contains lots of tall people wearing jerseys and carrying around basketballs, you might interpret X as the “basketball players” group).
  • For each place P and interest category C, you can compute the proportions of people at P because of C (under the current set of assignments), and these give you a representation of P. For example, you might learn that the people who hang out at Barnes & Noble consist of 10% hipsters, 50% anime fans, 10% jocks, and 30% college students.

Real-World Example

Finally, I applied LDA to a set of Sarah Palin’s emails a little while ago (see here for the blog post, hoặc đây là một ứng dụng cho phép bạn duyệt qua các emails bằng LDA-learned categories), dưới đây là 1 bán tóm gọn . Đây là một vài topics mà thuật toán học được :

  • Trig/Family/Inspiration: family, web, mail, god, son, from, congratulations, children, life, child, down, trig, baby, birth, love, you, syndrome, very, special, bless, old, husband, years, thank, best, …
  • Wildlife/BP Corrosion: game, fish, moose, wildlife, hunting, bears, polar, bear, subsistence, management, area, board, hunt, wolves, control, department, year, use, wolf, habitat, hunters, caribou, program, denby, fishing, …
  • Energy/Fuel/Oil/Mining: energy, fuel, costs, oil, alaskans, prices, cost, nome, now, high, being, home, public, power, mine, crisis, price, resource, need, community, fairbanks, rebate, use, mining, villages, …
  • Gas: gas, oil, pipeline, agia, project, natural, north, producers, companies, tax, company, energy, development, slope, production, resources, line, gasline, transcanada, said, billion, plan, administration, million, industry, …
  • Education/Waste: school, waste, education, students, schools, million, read, email, market, policy, student, year, high, news, states, program, first, report, business, management, bulletin, information, reports, 2008, quarter, …
  • Presidential Campaign/Elections: mail, web, from, thank, you, box, mccain, sarah, very, good, great, john, hope, president, sincerely, wasilla, work, keep, make, add, family, republican, support, doing, p.o, …

Đây là một ví dụ một email rời vào Trig/Family/Inspiration category (particularly representative words are highlighted in blue):

Trig Email

Đây là một trích đoạn từ một email mà sẽ 10% rời vào Presidential Campaign/Election category (màu đỏ ) và  90% rơi vào Wildlife/BP Corrosion category (màu xanh):

Wildlife-Presidency Email

Lược dịch từ : https://www.quora.com/What-is-a-good-explanation-of-Latent-Dirichlet-Allocation/answer/Edwin-Chen-1?srid=nqv8

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s