Đang chuẩn bị liên kết để tải về tài liệu:
Information Theory, Inference, and Learning Algorithms phần 5

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Đây là kết quả quan trọng. Chúng tôi thấy rằng dung lượng của kênh Gaussian là một chức năng của v tỷ lệ tín hiệu-to-noise / σ 2. Kết luận được đưa ra một phân phối đầu vào Gaussian | Copyright Cambridge University Press 2003. On-screen viewing permitted. Printing not permitted. http www.cambridge.org 0521642981 You can buy this book for 30 pounds or 50. See http www.inference.phy.cam.ac.uk mackay itila for links. 16.3 Finding the lowest-cost path 245 the resulting path a uniform random sample from the set of all paths Hint imagine trying it for the grid of figure 16.8. There is a neat insight to be had here and I d like you to have the satisfaction of figuring it out. fU Exercise 16.2. 2 p 247 Having run the forward and backward algorithms between points A and B on a grid how can one draw one path from A to B uniformly at random Figure 16.11. Figure 16.11. a The probability of passing through each node and b a randomly chosen path. The message-passing algorithm we used to count the paths to B is an example of the sum-product algorithm. The sum takes place at each node when it adds together the messages coming from its predecessors the product was not mentioned but you can think of the sum as a weighted sum in which all the summed terms happened to have weight 1. 16.3 Finding the lowest-cost path Imagine you wish to travel as quickly as possible from Ambridge A to Bognor B . The various possible routes are shown in figure 16.12 along with the cost in hours of traversing each edge in the graph. For example the route A-I-L-N-B has a cost of 8 hours. We would like to find the lowest-cost path without explicitly evaluating the cost of all paths. We can do this efficiently by finding for each node what the cost of the lowest-cost path to that node from A is. These quantities can be computed by message-passing starting from node A. The message-passing algorithm is called the min-sum algorithm or Viterbi algorithm. For brevity we ll call the cost of the lowest-cost path from node A to node x the cost of x . Each node can broadcast its cost to its descendants once it knows the costs of all its possible predecessors. Let s step through the algorithm by .