<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 情報組織化・検索論 補足資料1
潜在的意味解析
このページは演習ではありません．講義の理解を深めるために役立ててください．
参考文献
Step1:  特異値分解
Step2:  低ランク近似
Step3:  文書ベクトルの次元削減
$M_k = U_k \Sigma_k V_t^T$
$M_k$は$m\times n$行列であった．これを，特徴-文書，つまり$k \times n$行列で表現することを考える．
両辺に左から$U_k^T$を掛けると， 
$U_k^T M_k  = \Sigma_k V_k^T$ 
ここで，$U_k U_k^T=I$を利用した（$U$が正規直交行列のため）．
$U_k^T M_k=D_k = ({\bf d}_1^{(k)}, \ldots, {\bf d}_n^{(k)})$とおくと，
$D_k = \Sigma_k V_k^T  $
${\bf d}i^{(k)}$を特徴空間上での文書ベクトルとして利用することができる．　なお， ${\bf d}{i}^{(k)} は {\bf d}_{i}^{(k)} = U_k^T {\bf d}_j$としても求められる．
Step4:  文書$d1$と$d2$の特徴空間上での類似度を計算してみよう．
Step5:  このように，次元削減された文書ベクトル${{\bf d}_i^{(k)}}$間のコサイン類似度が，低ランク近似された単語-文書行列$M_k$における文書ベクトル間のコサイン類似度と一致することが分かる．
クエリの特徴空間での表現
いま，$m$次元クエリべトル${\bf q}$が与えられたとき，特徴空間上でのベクトル表現${\bf q}^{(k)}$は以下の式で得られる．
${\bf q}^{(k)} = U_k^T {\bf q}$
Step6:  単語ベクトルの次元削減
$M_k = U_k \Sigma_k V_t^T$
文書ベクトルと同様に，今度は両辺に右から$V_k$をかけると
$M_k V_k = U_k \Sigma_k$ （$V_k^T V_k=I$より)
$U_k \Sigma_k =T_k $とおくと，
$T_k = U_k \Sigma_k$
Step7:  $T$の$i$行目と$j$行目がそれぞれ単語$i，j$の特徴空間上でのベクトル表現になる
<ASSISTANT_TASK:>
Python Code:
import numpy as np
import scipy.linalg as lg
from scipy.spatial.distance import cosine
import matplotlib.pyplot as plt 
import pandas as pd
np.set_printoptions(precision=2)
pd.set_option('precision', 2)
%matplotlib inline
%precision 2
def sim(v1,v2): #コサイン類似度
    return 1-cosine(v1,v2)
# IIR exercise 18.4 の内容を用意
M = np.array(
    [[1,0,1,0,0,0],
    [0,1,0,0,0,0],
    [1,1,0,0,0,0],
    [1,0,0,1,1,0],
    [0,0,0,1,0,1]]
)
print(M)
print(M.shape)
print("Rank(M) =", np.linalg.matrix_rank(M)) #行列Mのランクは5
doc_names = ["d1", "d2", "d3", "d4", "d5", "d6"]
term_names = ["ship", "boat", "ocean", "voyge", "trip"]
df = pd.DataFrame(M, 
                  columns=doc_names, index=term_names) 
df
Explanation: 情報組織化・検索論 補足資料1
潜在的意味解析
このページは演習ではありません．講義の理解を深めるために役立ててください．
参考文献: Christopher D. Manning et al., Introduction to Information Retrieval, Cambridge University Press. 2008.
End of explanation
U, sigma, Vt = lg.svd(M) #SVD．なお，sigmaは行列ではなく特異値が降順に並んだ配列
Sigma = lg.diagsvd(sigma, M.shape[0], M.shape[1]) #確認のため truncateしていないSigmaを作成する．特異値集合からMxN対角行列を作成する．
print(Sigma.shape)
print(Sigma)
M_r = np.dot(np.dot(U, Sigma), Vt) #分解した結果が本当にMと一致するのか確認 M = U x Sigma x V^T
np.linalg.norm(M - M_r) # フロベニウスノルム
Explanation: 特異値分解
End of explanation
k = 2 #次元数
U_k = U[:, :k] #m-k行列にカット
Vt_k = Vt[:k,:] #k-n行列にカット
Sigma_k = Sigma[:k,:k] #特異値上位k個のみを用いる
print("U_k ="),
print(U_k)
print("Sigma_k=")
print(Sigma_k)
print("V_k^T ="),
print(Vt_k)
M_k = np.dot(np.dot(U_k, Sigma_k), Vt_k) #低ランク近似
print("M_k=")
print(M_k)
doc_names = ["d1", "d2", "d3", "d4", "d5", "d6"]
term_names = ["ship", "boat", "ocean", "voyge", "trip"]
df = pd.DataFrame(M_k, 
                  columns=doc_names, index=term_names) 
df
print("|| M - M_k || =", lg.norm(M-M_k)) # フロベニウスノルム
print("Rank(M_k) =", np.linalg.matrix_rank(M_k)) #ランク2の行列になっていることを確認
print(lg.norm(M-M_k)**2) # フロベニウスノルムの二乗が，k+1以降の特異値の平方和に等しいことを確認
print(sum(map(lambda x: x ** 2, sigma[k:]))) # k+1以降の特異値の平方和
Explanation: 低ランク近似
End of explanation
D_k = np.dot(Sigma_k, Vt_k)
D_k
axis_names = ["z1", "z2"]
doc_names = ["d1", "d2", "d3", "d4", "d5", "d6"]
df = pd.DataFrame(D_k.T, 
                  columns=axis_names, index=doc_names) # np.r_ は行列同士の連結
print("D_k=")
df.T
fig, ax = plt.subplots()
df.plot.scatter(x="z1", y="z2", ax=ax)
ax.axvline(x=0, lw=2, color='red') #x軸とy軸に線を引く
ax.axhline(y=0, lw=2, color='red') 
ax.set_xlim(-0.5, 2.0)
ax.set_ylim(-1.0, 1.5)
ax.grid(True)
for k, v in df.iterrows():
    ax.annotate(k, xy=(v[0]+0.05,v[1]+0.05),size=15) #データ点にラベル名を付与
Explanation: 文書ベクトルの次元削減
$M_k = U_k \Sigma_k V_t^T$
$M_k$は$m\times n$行列であった．これを，特徴-文書，つまり$k \times n$行列で表現することを考える．
両辺に左から$U_k^T$を掛けると， 
$U_k^T M_k  = \Sigma_k V_k^T$ 
ここで，$U_k U_k^T=I$を利用した（$U$が正規直交行列のため）．
$U_k^T M_k=D_k = ({\bf d}_1^{(k)}, \ldots, {\bf d}_n^{(k)})$とおくと，
$D_k = \Sigma_k V_k^T  $
${\bf d}i^{(k)}$を特徴空間上での文書ベクトルとして利用することができる．　なお， ${\bf d}{i}^{(k)} は {\bf d}_{i}^{(k)} = U_k^T {\bf d}_j$としても求められる．
End of explanation
# d1とd2の特徴空間上での類似度を計算する
print("特徴空間上でのコサイン類似度 =",sim(D_k[:,0], D_k[:,1]))
print("M_k上での文書ベクトルのコサイン類似度 =", sim(M_k[:,0], M_k[:,1]))
print("なお，元の文書ベクトル上でのコサイン類似度 =", sim(M[:,0],M[:,1]))
Explanation: 文書$d1$と$d2$の特徴空間上での類似度を計算してみよう．
End of explanation
q = np.array([1,0,1,1,0]) #文書d1と同じものをクエリとして用いてみる
q_k = np.dot(U_k.T, q)  #k次元特徴空間へ射影
print(q_k) # d_j^{k} と一致していることを確認
print("sim(q, d) =",sim(q_k, D_k[:,0])) #文書d1との特徴空間上での類似度
Explanation: このように，次元削減された文書ベクトル${{\bf d}_i^{(k)}}$間のコサイン類似度が，低ランク近似された単語-文書行列$M_k$における文書ベクトル間のコサイン類似度と一致することが分かる．
クエリの特徴空間での表現
いま，$m$次元クエリべトル${\bf q}$が与えられたとき，特徴空間上でのベクトル表現${\bf q}^{(k)}$は以下の式で得られる．
${\bf q}^{(k)} = U_k^T {\bf q}$
End of explanation
T_k  = np.dot(U_k, Sigma_k)
axis_names = ["z1", "z2"]
term_names = ["ship", "boat", "ocean", "voyge", "trip"]
df = pd.DataFrame(T_k, 
                  columns=axis_names, index=term_names) # np.r_ は行列同士の連結
df
Explanation: 単語ベクトルの次元削減
$M_k = U_k \Sigma_k V_t^T$
文書ベクトルと同様に，今度は両辺に右から$V_k$をかけると
$M_k V_k = U_k \Sigma_k$ （$V_k^T V_k=I$より)
$U_k \Sigma_k =T_k $とおくと，
$T_k = U_k \Sigma_k$
End of explanation
# 特徴空間上の単語ベクトルをプロット
fig, ax = plt.subplots()
df.plot.scatter(x="z1", y="z2", ax=ax)
ax.axvline(x=0, lw=2, color='red') #x軸とy軸に線を引く
ax.axhline(y=0, lw=2, color='red') 
ax.set_xlim(-0.5, 2.0)
ax.set_ylim(-1.0, 1.5)
ax.grid(True)
for k, v in df.iterrows():
    ax.annotate(k, xy=(v[0]+0.05,v[1]+0.05),size=15) #データ点にラベル名を付与
t_1 = T_k[0,:] #ship
t_2 = T_k[1,:] #boat
print("k次元特徴空間での類似度")
print("sim(ship, boat) =", sim(t_1, t_2))
print("元の空間での類似度")
print("sim(ship, boat) =", sim(M[0,:], M[1,:]))
Explanation: $T$の$i$行目と$j$行目がそれぞれ単語$i，j$の特徴空間上でのベクトル表現になる
End of explanation
<END_TASK>