C1W4.LAB.Vector manipulation+Hash functions and multiplanes

理论课：C1W4.Machine Translation and Document Search

理论课： C1W4.Machine Translation and Document Search

Python 中的矢量操作

使用 NumPy 库完成一些数组和矩阵的高级操作。

Transforming vectors

向量的变换主要有三种：

• 缩放
• 平移
• 旋转

前面的课程已经应用了前两种变换。下面学习如何使用向量的基本变换，即旋转。旋转操作改变了向量的方向，但不影响其维数和常模。

Example 1

import numpy as np                     # Import numpy for array manipulation
import matplotlib.pyplot as plt        # Import matplotlib for charts
from utils_nb import plot_vectors      # Function to plot vectors (arrows)

# Create a 2 x 2 matrix
R = np.array([[2, 0],[0, -2]])x = np.array([[1, 1]]) # Create a 1 x 2 matrix

向量与方阵之间的点乘会产生原始向量的旋转和缩放。推荐的在 Python 中获取点积的方法是 np.dot(a,b)：

y = np.dot(x, R) # Apply the dot product between x and R
y

结果：
array([[ 2, -2]])
这样看不是很直观，借助utils_nb.py中的plot_vectors把结果绘制出来，先在笛卡尔平面中绘制 $\vec{x}=[1,1]$，笛卡尔平面将以 [0,0]为中心，其 x 和 y 极限将介于 [-4,+4]之间。

plot_vectors([x], axes=[4, 4], fname='transform_x.svg')

在相同坐标系绘制要点积矩阵后的结果（蓝色）：
$$Ro=\left[\begin{array}{cc}2& 0\\ 0& -2\end{array}\right]$$

$$y=x\cdot Ro=[[2,-2]]$$

plot_vectors([x, y], axes=[4, 4], fname='transformx_and_y.svg')

Example 2

接下来使用 Pyplot 直观地检测旋转对二维向量的影响。数据由 2 个真实属性组成，属于 $R\times R$ 或 $R^2$ 空间。$R^2$空间中的旋转矩阵将会使给定向量 $\vec{x}$ 顺时针旋转一个角度 $\theta$，旋转矩阵可写为：
$$Ro=\left[\begin{array}{cc}cos\theta & -sin\theta \\ sin\theta & cos\theta \end{array}\right]$$
顺时针旋转可写成：
$$y=x\cdot Ro$$
逆时针旋转：
$$y=Ro\cdot x^T$$
注意：在Numpy中使用的是弧度不是角度，例如：以下代码定义一个旋转矩阵，该矩阵可将向量旋转 $100^o$ 。

angle = 100 * (np.pi / 180) #convert degrees to radiansRo = np.array([[np.cos(angle), -np.sin(angle)],[np.sin(angle), np.cos(angle)]])x2 = np.array([2, 2]).reshape(1, -1) # make it a row vector
y2 = np.dot(x2, Ro)print('Rotation matrix')
print(Ro)
print('\nRotated vector')
print(y2)print('\n x2 norm', np.linalg.norm(x2))
print('\n y2 norm', np.linalg.norm(y2))
print('\n Rotation matrix norm', np.linalg.norm(Ro))

结果：
Rotation matrix
[[-0.17364818 -0.98480775]
[ 0.98480775 -0.17364818]]

Rotated vector
[[ 1.62231915 -2.31691186]]

x2 norm 2.8284271247461903

y2 norm 2.82842712474619

Rotation matrix norm 1.414213562373095
可视化后：

plot_vectors([x2, y2], fname='transform_02.svg')

注意：
1.输入向量的范数与输出向量的范数相同。旋转矩阵不会改变向量的范数，只会改变其方向。
2.任何 $R^2$空间的旋转矩阵的范数均为：$\sqrt{2}=1.414221$

Frobenius Norm

Frobenius范数是$R^2$向量的模一般化表达：
$$\Vert \vec{a}\Vert =\sqrt{\vec{a}\cdot \vec{a}}$$
对于给定的 $R^2$ 矩阵 A，Frobenius范数的定义为：
$$\Vert \mathrm{A}{\Vert }_F\equiv \sqrt{\sum _{i=1}^m\sum _{j=1}^n{\left|a_{ij}\right|}^2}$$
下面是手工计算：

A = np.array([[2, 2],[2, 2]])

先算各个元素平方：

A_squared = np.square(A)
A_squared

在累加后开方：

A_Frobenius = np.sqrt(np.sum(A_squared))
A_Frobenius

当然有现成的函数：np.linalg.norm()

print('Frobenius norm of the Rotation matrix')
print(np.sqrt(np.sum(Ro * Ro)), '== ', np.linalg.norm(Ro))

Hash functions and multiplanes

使用哈希函数进行查找的一个关键点是计算为给定条目分配的哈希密钥或桶 ID。下面我们将学习：

• 基本哈希表
• 多平面
• 随机平面

Basic Hash tables

先导入包

import numpy as np                # library for array and matrix manipulation
import pprint                     # utilities for console printing 
from utils_nb import plot_vectors # helper function to plot vectors
import matplotlib.pyplot as plt   # visualization librarypp = pprint.PrettyPrinter(indent=4) # Instantiate a pretty printer

下面代码定义了一个直接用于整数的哈希函数。函数将接收一个整数列表和所需的散列数量。函数将生成一个以字典形式存储的哈希表，其中键包含哈希键，值提供输入列表中的哈希元素。
哈希函数只是每个元素与所需的桶数之间的整除余数。

def basic_hash_table(value_l, n_buckets):def hash_function(value, n_buckets):return int(value) % n_bucketshash_table = {i:[] for i in range(n_buckets)} # Initialize all the buckets in the hash table as empty listsfor value in value_l:hash_value = hash_function(value,n_buckets) # Get the hash key for the given valuehash_table[hash_value].append(value) # Add the element to the corresponding bucketreturn hash_table

测试：

value_l = [100, 10, 14, 17, 97] # Set of values to hash
hash_table_example = basic_hash_table(value_l, n_buckets=10)
pp.pprint(hash_table_example)

结果：
{ 0: [100, 10],
1: [],
2: [],
3: [],
4: [14],
5: [],
6: [],
7: [17, 97],
8: [],
9: []}
这里的桶键是每个数字最右边的数字。

Planes

多平面散列函数（Multi-plane Hashing，简称MPH）是一种哈希函数的设计方法，它通过将输入数据分割成多个部分，并在不同的平面上独立地对这些部分进行哈希处理，然后将结果组合起来生成最终的哈希值。这种方法在某些应用中可以提高哈希函数的性能和安全性。在下面的代码中，我们将展示多平面原理的最基本形式。首先是单平面：

P = np.array([[1, 1]]) # Define a single plane. 
fig, ax1 = plt.subplots(figsize=(8, 8)) # Create a plotplot_vectors([P], axes=[2, 2], ax=ax1) # Plot the plane P as a vector# Plot  random points. 
for i in range(0, 10):v1 = np.array(np.random.uniform(-2, 2, 2)) # Get a pair of random numbers between -2 and 2side_of_plane = np.sign(np.dot(P, v1.T)) # Color the points depending on the sign of the result of np.dot(P, point.T)if side_of_plane == 1:ax1.plot([v1[0]], [v1[1]], 'bo') # Plot blue pointselse:ax1.plot([v1[0]], [v1[1]], 'ro') # Plot red pointsplt.show()

结果：

上图中可以看到，定义平面的矢量并不是平面两边的边界。它标记的是找到平面 "正 "边的方向，这样看其实非常不直观。可用一条线来把这个面表示出来：

P = np.array([[1, 2]])  # Define a single plane. You may change the direction# Get a new plane perpendicular to P. We use a rotation matrix
PT = np.dot([[0, 1], [-1, 0]], P.T).T  fig, ax1 = plt.subplots(figsize=(8, 8)) # Create a plot with custom sizeplot_vectors([P], colors=['b'], axes=[2, 2], ax=ax1) # Plot the plane P as a vector# Plot the plane P as a 2 vectors. 
# We scale by 2 just to get the arrows outside the current box
plot_vectors([PT * 4, PT * -4], colors=['k', 'k'], axes=[4, 4], ax=ax1)# Plot 20 random points. 
for i in range(0, 20):v1 = np.array(np.random.uniform(-4, 4, 2)) # Get a pair of random numbers between -4 and 4 side_of_plane = np.sign(np.dot(P, v1.T)) # Get the sign of the dot product with P# Color the points depending on the sign of the result of np.dot(P, point.T)if side_of_plane == 1:ax1.plot([v1[0]], [v1[1]], 'bo') # Plot a blue pointelse:ax1.plot([v1[0]], [v1[1]], 'ro') # Plot a red pointplt.show()

结果：

下面对几个点进行计算，判断其相对平面的位置：

P = np.array([[1, 1]])      # Single plane
v1 = np.array([[1, 2]])     # Sample point 1
v2 = np.array([[-1, 1]])    # Sample point 2
v3 = np.array([[-2, -1]])   # Sample point 3

np.dot(P, v1.T)

结果：array([[3]])

np.dot(P, v2.T)

结果：array([[0]])

np.dot(P, v3.T)

结果：array([[-3]])

把这块判断写成一个函数：

def side_of_plane(P, v):dotproduct = np.dot(P, v.T) # Get the dot product P * v'sign_of_dot_product = np.sign(dotproduct) # The sign of the elements of the dotproduct matrix sign_of_dot_product_scalar = sign_of_dot_product.item() # The value of the first itemreturn sign_of_dot_product_scalar

判断实例：

side_of_plane(P, v1) # In which side is [1, 2]

结果：1

side_of_plane(P, v2) # In which side is [-1, 1]

结果：0

side_of_plane(P, v3) # In which side is [-2, -1]

结果：-1

Hash Function with multiple planes

下面代码在二维平面上定义了三个平面：

P1 = np.array([[1, 1]])   # First plane 2D
P2 = np.array([[-1, 1]])  # Second plane 2D
P3 = np.array([[-1, -1]]) # Third plane 2D
P_l = [P1, P2, P3]  # List of arrays. It is the multi plane# Vector to search
v = np.array([[2, 2]])

然后可以定义函数，查找想所在平面，它接受两个参数：平面列表 P_l 和要搜索的向量 。

# 定义多平面散列函数
def hash_multi_plane(P_l, v):# 初始化哈希值hash_value = 0# 遍历每个平面for i, P in enumerate(P_l):# 计算向量v相对于平面P的位置，这里假设side_of_plane函数存在并返回一个整数# 该整数表示向量v在平面的哪一侧：1表示同侧，-1表示异侧，0表示在平面上sign = side_of_plane(P, v)# 根据sign的值，设置当前平面的哈希位为0或1hash_i = 1 if sign >= 0 else 0# 将当前平面的哈希位左移i位（i为当前平面的索引），然后加到总哈希值上# 这样做可以确保每个平面的贡献被编码到哈希值的不同位上hash_value += 2**i * hash_i# 返回计算得到的哈希值return hash_value# 调用多平面散列函数，传入平面列表P_l和向量v，计算向量v的哈希值
# 注意：这里side_of_plane函数需要被定义，否则代码将无法运行
print(hash_multi_plane(P_l, v))

结果：3

Random Planes

先创建3个随机平面：

np.random.seed(0)
num_dimensions = 2 # is 300 in assignment
num_planes = 3 # is 10 in assignment
random_planes_matrix = np.random.normal(size=(num_planes,num_dimensions))
print(random_planes_matrix)
# 定义一个向量v，它将用于计算它相对于每个平面的位置
v = np.array([[2, 2]])

结果：
[[ 1.76405235 0.40015721]
[ 0.97873798 2.2408932 ]
[ 1.86755799 -0.97727788]]

# 定义一个函数side_of_plane_matrix，它接受一个平面矩阵P和一个向量v
def side_of_plane_matrix(P, v):# 使用numpy的dot函数计算平面矩阵P和向量v的转置（即每个平面的法向量与向量v的点积）dotproduct = np.dot(P, v.T)# 使用numpy的sign函数获取点积的符号，这将返回一个与dotproduct形状相同的矩阵# 矩阵中的每个元素将是-1、0或1，分别表示点积是负数、零或正数sign_of_dot_product = np.sign(dotproduct) # 返回点积的符号矩阵return sign_of_dot_product

对向量[2, 2]判断其对以上随机平面的位置。

sides_l = side_of_plane_matrix(random_planes_matrix, v)
sides_l

结果：
array([[1.],
[1.],
[1.]])
使用上面函数定义多平面哈希函数：

def hash_multi_plane_matrix(P, v, num_planes):sides_matrix = side_of_plane_matrix(P, v) # Get the side of planes for P and vhash_value = 0for i in range(num_planes):sign = sides_matrix[i].item() # Get the value inside the matrix cellhash_i = 1 if sign >=0 else 0hash_value += 2**i * hash_i # sum 2^i * hash_ireturn hash_value

对向量v = [2, 2]进行测试：

hash_multi_plane_matrix(random_planes_matrix, v, num_planes)

结果：
7

Document vectors

思考下面代码什么作用？

word_embedding = {"I": np.array([1,0,1]),"love": np.array([-1,0,1]),"learning": np.array([1,0,1])}
words_in_document = ['I', 'love', 'learning', 'not_a_word']
document_embedding = np.array([0,0,0])
for word in words_in_document:document_embedding += word_embedding.get(word,0)print(document_embedding)

结果：[1 0 3]