Thuật toán hiệu quả để lấy mẫu ngẫu nhiên từ phân phối trong khi cho phép cập nhật?

Question

Đây là câu hỏi mà tôi đã được hỏi một thời gian trước khi phỏng vấn, tôi không thể tìm thấy câu trả lời.

Cho một số mẫu S1, S2, ... Sn và phân bố xác suất (hoặc trọng số, bất kể nó được gọi là gì) P1, P2, .. Pn, thuật toán thiết kế chọn ngẫu nhiên mẫu có tính đến xác suất của nó. giải pháp tôi đến với là như sau:

1. xây dựng mảng tích lũy của trọng Ci, chẳng hạn

   C0 = 0; Ci = C [i-1] + Pi.

đồng thời tính T = P1 + P2 + ... Pn. Phải mất O (n) thời gian

2. Tạo thống nhất ngẫu nhiên số R = T * ngẫu nhiên [0..1]
3. Sử dụng thuật toán tìm kiếm nhị phân, trở lại ít nhất tôi như Ci> = R. kết quả là Si. Mất thời gian O (logN).

Bây giờ câu hỏi thực tế là: Giả sử tôi muốn thay đổi một trong các Trọng số ban đầu Pj. làm thế nào để làm điều này trong tốt hơn so với O (n) thời gian? cấu trúc dữ liệu khác có thể chấp nhận được, nhưng thuật toán lấy mẫu ngẫu nhiên không nên tệ hơn O (logN).

Answer 1

Một cách để giải quyết điều này là suy nghĩ lại cách cây tìm kiếm nhị phân của bạn chứa tổng tích lũy được tạo. Thay vì xây dựng cây tìm kiếm nhị phân, hãy suy nghĩ về việc mỗi nút được giải thích như sau:

• Mỗi nút lưu trữ một loạt các giá trị được dành riêng cho nút đó.
• Các nút trong nhánh phụ bên trái đại diện lấy mẫu từ phân phối xác suất ở bên trái của phạm vi đó.
• Các nút trong nhánh phụ phải thể hiện lấy mẫu từ phân phối xác suất ở bên phải của phạm vi đó.

Ví dụ: giả sử trọng số của chúng tôi là 3, 2, 2, 2, 2, 1 và 1 cho các sự kiện A, B, C, D, E, F và G. Chúng tôi xây dựng cây nhị phân này A, B, C, D, E, F và G:

   D 
      / \ 
      B  F 
     /\ /\ 
     A C E G 

Bây giờ, chúng tôi chú thích cây có xác suất.Vì A, C, E và G là tất cả các lá, chúng tôi cung cấp cho mỗi xác suất khối lượng một:

   D 
      / \ 
      B  F 
     /\ /\ 
     A C E G 
     1 1 1 1 

Bây giờ, hãy xem cây cho B. B có trọng lượng 2 được chọn, A có trọng lượng 3 được chọn, và C có xác suất 2 được chọn. Nếu chúng ta chuẩn hóa chúng thành phạm vi [0, 1), thì A sẽ chiếm 3/7 xác suất và B và C mỗi tài khoản trong 2/7 giây. Vì vậy, chúng tôi có nút cho B nói rằng bất cứ điều gì trong phạm vi [0, 3/7) đi đến subtree trái, bất cứ điều gì trong phạm vi [3/7, 5/7) bản đồ để B, và bất cứ điều gì trong phạm vi [5/7, 1) ánh xạ tới đúng cây con:

    D 
       / \ 
      B    F 
[0, 3/7)/\ [5/7, 1)/\ 
     A C   E G 
     1 1   1 1 

Tương tự, hãy xử lý F. E có trọng số 2 được chọn trong khi F và G có trọng số xác suất 1 được chọn. Vì vậy, subtree cho E chiếm 1/2 khối lượng xác suất ở đây, nút F chiếm 1/4, và subtree cho G chiếm 1/4. Điều này có nghĩa là chúng tôi có thể chỉ định xác suất là

     D 
        / \ 
      B      F 
[0, 3/7)/\ [5/7, 1) [0, 1/2)/\ [3/4, 1) 
     A C     E G 
     1 1     1 1 

Cuối cùng, hãy nhìn vào thư mục gốc. Trọng lượng kết hợp của cây con trái là 3 + 2 + 2 = 7. Trọng lượng kết hợp của cây con phải là 2 + 1 + 1 = 4. Trọng lượng của D chính là 2. Vì vậy, cây con trái có xác suất 7/13 của được chọn, D có xác suất 2/13 được chọn, và cây con phải có xác suất 4/13 được chọn. do đó chúng ta có thể hoàn thành các xác suất như

     D 
      [0, 7/13)/ \ [9/13, 1) 
      B      F 
[0, 3/7)/\ [5/7, 1) [0, 1/2)/\ [3/4, 1) 
     A C     E G 
     1 1     1 1 

Để tạo ra một giá trị ngẫu nhiên, bạn sẽ lặp lại như sau:

• Bắt đầu từ gốc rễ:
  • Chọn một giá trị thống nhất-ngẫu nhiên trong phạm vi [0, 1).
  • Nếu nó nằm trong phạm vi cho cây con trái, hãy đi sâu vào nó.
  • Nếu nó nằm trong phạm vi cho cây con phù hợp, hãy đi sâu vào nó.
  • Nếu không, hãy trả về giá trị tương ứng với nút hiện tại.

Xác suất bản thân có thể được xác định một cách đệ quy khi cây được xây dựng:

• trái và xác suất đúng là 0 đối với bất kỳ nút lá.
• Nếu một nút nội thất chính nó có trọng lượng W, cây trái của nó có tổng trọng lượng W _L, và cây quyền của mình có tổng trọng lượng W _R, sau đó xác suất trái là (W _L)/(W + W _L + W _R) và xác suất đúng là (W _R)/(W + W _L + W _R).

Lý do cải cách này hữu ích là nó cho chúng ta một cách để cập nhật xác suất trong thời gian O (log n) trên mỗi xác suất được cập nhật. Đặc biệt, chúng ta hãy suy nghĩ về những bất biến sẽ thay đổi nếu chúng ta cập nhật một số trọng lượng của nút cụ thể. Để đơn giản, giả sử nút bây giờ là một chiếc lá.Khi chúng tôi cập nhật trọng lượng của nút lá, xác suất vẫn chính xác cho nút lá, nhưng chúng không chính xác cho nút ngay phía trên nó, vì trọng số của một trong các subtrees của nút đó đã thay đổi. Do đó chúng ta có thể (trong thời gian O (1)) tính lại các xác suất cho nút cha bằng cách chỉ sử dụng công thức giống như trên. Nhưng sau đó, phụ huynh của nút đó không còn có giá trị chính xác vì một trong các trọng số subtree của nó đã thay đổi, vì vậy chúng tôi có thể tính toán lại xác suất ở đó. Quá trình này lặp lại tất cả các cách trở lại lên đến gốc của cây, với chúng tôi làm O (1) tính toán cho mỗi cấp độ để khắc phục các trọng số được giao cho mỗi cạnh. Giả sử rằng cây được cân bằng, do đó chúng ta phải thực hiện tổng công việc O (log n) để cập nhật một xác suất. Logic giống hệt nếu nút không phải là nút lá; chúng ta chỉ bắt đầu ở đâu đó trong cây.

Nói tóm lại, điều này sẽ cho

• O (n) thời gian để xây dựng cây (sử dụng một cách tiếp cận từ dưới lên),
• O (log n) thời gian để tạo ra một giá trị ngẫu nhiên, và
• O (nhật ký n) thời gian để cập nhật bất kỳ giá trị nào.

Hy vọng điều này sẽ hữu ích!

Answer 2

Thay vì mảng, lưu trữ tìm kiếm được cấu trúc dưới dạng cây nhị phân cân bằng. Mỗi nút của cây nên lưu trữ tổng trọng lượng của các phần tử chứa trong đó. Tùy thuộc vào giá trị của R, thủ tục tìm kiếm trả về nút hiện tại hoặc tìm kiếm thông qua cây con trái hoặc phải.

Khi trọng lượng của phần tử bị thay đổi, việc cập nhật cấu trúc tìm kiếm là vấn đề điều chỉnh trọng số trên đường dẫn từ phần tử đến gốc cây.

Vì cây được cân bằng, tìm kiếm và các hoạt động cập nhật trọng số đều là O (log N).

Answer 3

Đối với những người bạn của những người muốn một số mã, đây là một thực hiện python:

import numpy 


class DynamicProbDistribution(object): 
    """ Given a set of weighted items, randomly samples an item with probability 
    proportional to its weight. This class also supports fast modification of the 
    distribution, so that changing an item's weight requires O(log N) time. 
    Sampling requires O(log N) time. """ 

    def __init__(self, weights): 
    self.num_weights = len(weights) 
    self.weights = numpy.empty((1+len(weights),), 'float32') 
    self.weights[0] = 0 # Not necessary but easier to read after printing 
    self.weights[1:] = weights 
    self.weight_tree = numpy.zeros((1+len(weights),), 'float32') 
    self.populate_weight_tree() 

    def populate_weight_tree(self): 
    """ The value of every node in the weight tree is equal to the sum of all 
    weights in the subtree rooted at that node. """ 
    i = self.num_weights 
    while i > 0: 
     weight_sum = self.weights[i] 
     twoi = 2*i 
     if twoi < self.num_weights: 
     weight_sum += self.weight_tree[twoi] + self.weight_tree[twoi+1] 
     elif twoi == self.num_weights: 
     weight_sum += self.weights[twoi] 
     self.weight_tree[i] = weight_sum 
     i -= 1 

    def set_weight(self, item_idx, weight): 
    """ Changes the weight of the given item. """ 
    i = item_idx + 1 
    self.weights[i] = weight 
    while i > 0: 
     weight_sum = self.weights[i] 
     twoi = 2*i 
     if twoi < self.num_weights: 
     weight_sum += self.weight_tree[twoi] + self.weight_tree[twoi+1] 
     elif twoi == self.num_weights: 
     weight_sum += self.weights[twoi] 
     self.weight_tree[i] = weight_sum 
     i /= 2 # Only need to modify the parents of this node 

    def sample(self): 
    """ Returns an item index sampled from the distribution. """ 
    i = 1 
    while True: 
     twoi = 2*i 

     if twoi < self.num_weights: 
     # Two children 
     val = numpy.random.random() * self.weight_tree[i] 
     if val < self.weights[i]: 
      # all indices are offset by 1 for fast traversal of the 
      # internal binary tree 
      return i-1 
     elif val < self.weights[i] + self.weight_tree[twoi]: 
      i = twoi # descend into the subtree 
     else: 
      i = twoi + 1 

     elif twoi == self.num_weights: 
     # One child 
     val = numpy.random.random() * self.weight_tree[i] 
     if val < self.weights[i]: 
      return i-1 
     else: 
      i = twoi 

     else: 
     # No children 
     return i-1 


def validate_distribution_results(dpd, weights, samples_per_item=1000): 
    import time 

    bins = numpy.zeros((len(weights),), 'float32') 
    num_samples = samples_per_item * numpy.sum(weights) 

    start = time.time() 
    for i in xrange(num_samples): 
    bins[dpd.sample()] += 1 
    duration = time.time() - start 

    bins *= numpy.sum(weights) 
    bins /= num_samples 

    print "Time to make %s samples: %s" % (num_samples, duration) 

    # These should be very close to each other 
    print "\nWeights:\n", weights 
    print "\nBins:\n", bins 

    sdev_tolerance = 10 # very unlikely to be exceeded 
    tolerance = float(sdev_tolerance)/numpy.sqrt(samples_per_item) 
    print "\nTolerance:\n", tolerance 

    error = numpy.abs(weights - bins) 
    print "\nError:\n", error 

    assert (error < tolerance).all() 


#@test 
def test_DynamicProbDistribution(): 
    # First test that the initial distribution generates valid samples. 

    weights = [2,5,4, 8,3,6, 6,1,3, 4,7,9] 
    dpd = DynamicProbDistribution(weights) 

    validate_distribution_results(dpd, weights) 

    # Now test that we can change the weights and still sample from the 
    # distribution. 

    print "\nChanging weights..." 
    dpd.set_weight(4, 10) 
    weights[4] = 10 
    dpd.set_weight(9, 2) 
    weights[9] = 2 
    dpd.set_weight(5, 4) 
    weights[5] = 4 
    dpd.set_weight(11, 3) 
    weights[11] = 3 

    validate_distribution_results(dpd, weights) 

    print "\nTest passed" 


if __name__ == '__main__': 
    test_DynamicProbDistribution()