维特比解码（Viterbi Decoding）是一种用于解码卷积编码（Convolutional Coding）的算法，由 Andrew Viterbi 在 1968 年提出。卷积编码是一种前向纠错编码技术，用于提高数据传输的可靠性。在卷积编码中，数据被组织成一定大小的块，并用一个纠错码附加到数据块中。在接收端，维特比解码算法根据接收到的编码数据，通过比较不同可能的解码路径的权重，来找到最有可能的解码路径，从而实现对数据的解码。
维特比解码算法的主要步骤如下：
- 初始化：首先，需要为输入数据和纠错码生成一个对应的软输入软输出矩阵（Soft Input Soft Output Matrix），其中软输入是接收到的编码数据，软输出是待解码的数据。
- 动态规划：在维特比解码过程中，需要对所有可能的解码路径进行评估，并记录每个路径的权重。这一步通常采用动态规划方法，自底向上地计算路径权重，并沿路径剪去权重较小的路径。
- 存活路径：在所有可能的解码路径中，存活路径是指在剪枝过程中仍然保持权重的路径。这些路径被认为是最有可能的解码路径。
- 回溯：从存活路径中，可以根据路径权重回溯找到最有可能的解码路径。回溯过程中，需要根据软输入软输出矩阵重新构造解码数据。
- 输出解码结果：得到最有可能的解码路径后，可以根据该路径从软输出矩阵中提取解码数据，从而实现对原始数据的解码。
总之，维特比解码是一种用于解码卷积编码的算法，通过比较不同解码路径的权重来找到最有可能的解码路径。在实际应用中，维特比解码算法被广泛应用于通信系统、数据存储和计算机视觉等领域。
Self-organizing map
Import TensorFlow and NumPy:
%matplotlib inline
import tensorflow as tf
import numpy as np
Define a class called SOM. The constructor builds a grid of nodes, and also defines some helper ops:
class SOM:
def __init__(self, width, height, dim):
self.num_iters = 100
self.width = width
self.height = height
self.dim = dim
self.node_locs = self.get_locs()
# Each node is a vector of dimension `dim`
# For a 2D grid, there are `width * height` nodes
nodes = tf.Variable(tf.random_normal([width*height, dim]))
self.nodes = nodes
# These two ops are inputs at each iteration
x = tf.placeholder(tf.float32, [dim])
iter = tf.placeholder(tf.float32)
self.x = x
self.iter = iter
# Find the node that matches closest to the input
bmu_loc = self.get_bmu_loc(x)
self.propagate_nodes = self.get_propagation(bmu_loc, x, iter)
def get_propagation(self, bmu_loc, x, iter):
'''
Define the weight propagation function that will update weights of the best matching unit (BMU).
The intensity of weight updates decreases over time, as dictated by the `iter` variable.
'''
num_nodes = self.width * self.height
rate = 1.0 - tf.div(iter, self.num_iters)
alpha = rate * 0.5
sigma = rate * tf.to_float(tf.maximum(self.width, self.height)) / 2.
expanded_bmu_loc = tf.expand_dims(tf.to_float(bmu_loc), 0)
sqr_dists_from_bmu = tf.reduce_sum(tf.square(tf.subtract(expanded_bmu_loc, self.node_locs)), 1)
neigh_factor = tf.exp(-tf.div(sqr_dists_from_bmu, 2 * tf.square(sigma)))
rate = tf.multiply(alpha, neigh_factor)
rate_factor = tf.stack([tf.tile(tf.slice(rate, [i], [1]), [self.dim]) for i in range(num_nodes)])
nodes_diff = tf.multiply(rate_factor, tf.subtract(tf.stack([x for i in range(num_nodes)]), self.nodes))
update_nodes = tf.add(self.nodes, nodes_diff)
return tf.assign(self.nodes, update_nodes)
def get_bmu_loc(self, x):
'''
Define a helper function to located the BMU:
'''
expanded_x = tf.expand_dims(x, 0)
sqr_diff = tf.square(tf.subtract(expanded_x, self.nodes))
dists = tf.reduce_sum(sqr_diff, 1)
bmu_idx = tf.argmin(dists, 0)
bmu_loc = tf.stack([tf.mod(bmu_idx, self.width), tf.div(bmu_idx, self.width)])
return bmu_loc
def get_locs(self):
'''
Build a grid of nodes:
'''
locs = [[x, y]
for y in range(self.height)
for x in range(self.width)]
return tf.to_float(locs)
def train(self, data):
'''
Define a function to training the SOM on a given dataset:
'''
with tf.Session() as sess:
sess.run(tf.global_variables_initializer())
for i in range(self.num_iters):
for data_x in data:
sess.run(self.propagate_nodes, feed_dict={self.x: data_x, self.iter: i})
centroid_grid = [[] for i in range(self.width)]
self.nodes_val = list(sess.run(self.nodes))
self.locs_val = list(sess.run(self.node_locs))
for i, l in enumerate(self.locs_val):
centroid_grid[int(l[0])].append(self.nodes_val[i])
self.centroid_grid = centroid_grid
Time to use our newfound powers. Let's test it out on some data:
import matplotlib.pyplot as plt
colors = np.array(
[[0., 0., 1.],
[0., 0., 0.95],
[0., 0.05, 1.],
[0., 1., 0.],
[0., 0.95, 0.],
[0., 1, 0.05],
[1., 0., 0.],
[1., 0.05, 0.],
[1., 0., 0.05],
[1., 1., 0.]])
som = SOM(4, 4, 3)
som.train(colors)
plt.imshow(som.centroid_grid)
plt.show()
