HardNLPnlp-170

Gibbs Sampling One Step

Problem

Draw a new topic for one word with collapsed Gibbs sampling for LDA. For each topic k the unnormalized probability is (n_dk + alpha) * (n_kw + beta) / (n_k + vocab_size * beta), where n_dk comes from doc_topic, and n_kw and n_k come from topic_word.

Draw a value with random.Random(seed) scaled by the total probability and return the selected topic. Return the first topic in sorted order when every probability is 0.

Hint

Iterate topics in sorted order so the seeded draw maps to a stable range.

Test cases

case 1

in: [{"t1":2,"t2":1},{"t1":{"cat":3,"dog":1},"t2":{"cat":1,"dog":2}},0.5,0.1,2,"cat",42]

expected: "t1"

case 2

in: [{"t1":2,"t2":1},{"t1":{"cat":3,"dog":1},"t2":{"cat":1,"dog":2}},0.5,0.1,2,"cat",2]

expected: "t2"

case 3

in: [{"t1":2,"t2":1},{"t1":{"cat":3,"dog":1},"t2":{"cat":1,"dog":2}},0.5,0.1,2,"dog",1]

expected: "t1"

case 4

in: [{"a":1},{"a":{"x":1}},0.1,0.1,3,"x",5]

expected: "a"

Starter codePython

import random
def gibbs_sampling_step(doc_topic, topic_word, alpha, beta, vocab_size, word, seed):
    # Your code here
    pass

4 test cases · run your code against them in the editor