def dist1(vec1, vec2): # eqn1 
    diff_vec = vec1 - vec2
    return 1 + 2 * norm(diff_vec) / ((1 - norm(vec1)) * (1 - norm(vec2)))

# 范數(shù)計(jì)算
def norm(x):
    return np.dot(x, x)

# 距離函數(shù)對(duì)\theta求偏導(dǎo)
def compute_distance_gradients(theta, x, gamma):
    alpha = (1.0 - np.dot(theta, theta))
    norm_x = norm(x)
    beta = (1 - norm_x)
    c_ = 4.0 / (alpha * beta * sqrt(gamma ** 2 - 1))
    return c_ * ((norm_x - 2 * np.dot(theta, x) + 1) / alpha * theta - x)

# 更新公式
def update(emb, grad, lr): 
    c_ = (1 - norm(emb)) ** 2 / 4
    upd =  lr * c_ * grad
    emb = emb - upd
    if (norm(emb) >= 1):
        emb = emb / sqrt(norm(emb)) - eps
    return emb

def plotall(ii):
    fig = plt.figure(figsize=(10, 10))
    # 繪制所有節(jié)點(diǎn)
    for a in emb:
        plt.plot(emb[a][0], emb[a][1], marker = 'o', color = [levelOfNode[a]/(last_level+1),levelOfNode[a]/(last_level+1),levelOfNode[a]/(last_level+1)])
    for a in network:
        for b in network[a]:
            plt.plot([emb[a][0], emb[b][0]], [emb[a][1], emb[b][1]], color = [levelOfNode[a]/(last_level+1),levelOfNode[a]/(last_level+1),levelOfNode[a]/(last_level+1)])
            circle = plt.Circle((0, 0), 1, color='y', fill=False)
            plt.gcf().gca().add_artist(circle)
    plt.xlim(-1, 1)
    plt.ylim(-1, 1)
    fig.savefig('~/GitHub/hyperE/fig/' + str(last_level) + '_' + str(ii) + '.png', dpi = 200)

emb = {}
for node in levelOfNode:
    emb[node] = np.random.uniform(low = -0.001, high = 0.001, size = (2, ))

vocab = list(emb.keys())
eps = 1e-5    
lr = 0.1       # 學(xué)習(xí)率
num_negs = 10  # 負(fù)樣本個(gè)數(shù)

# 繪制初始化權(quán)重
plotall("init")
for epoch in range(1000):
    loss = []
    random.shuffle(vocab)
    
    # 下面需要抽取不同的樣本：pos2 與 pos1 相關(guān)；negs 不與 pos1 相關(guān)
    for pos1 in vocab:
        if not network[pos1]: # 葉子節(jié)點(diǎn)則不進(jìn)行訓(xùn)練
            continue
        pos2 = random.choice(network[pos1]) # 隨機(jī)選取與pos1相關(guān)的節(jié)點(diǎn)pos2
        dist_pos_ = dist1(emb[pos1], emb[pos2]) # 保留中間變量gamma，加速計(jì)算
        dist_pos = np.arccosh(dist_pos_) # 計(jì)算pos1與pos2之間的距離
        
        # 下面抽取負(fù)樣本組（不與pos1相關(guān)的樣本組）
        negs = [[pos1, pos1]]
        dist_negs_ = [1] 
        dist_negs = [0]
        
        while (len(negs) < num_negs):
            neg = random.choice(vocab)
            
            # 保證負(fù)樣本neg與pos1沒(méi)有邊相連接
            if not (neg in network[pos1] or pos1 in network[neg] or neg == pos1): 
                dist_neg_ = dist1(emb[pos1], emb[neg])
                dist_neg = np.arccosh(dist_neg_)
                negs.append([pos1, neg])
                dist_negs_.append(dist_neg_) # 保存中間變量gamma，加速計(jì)算
                dist_negs.append(dist_neg)
        
        # 針對(duì)一個(gè)樣本的損失
        loss_neg = 0.0
        for dist_neg in dist_negs:
            loss_neg += exp(-1 * dist_neg)
        loss.append(dist_pos + log(loss_neg))
        
        # 損失函數(shù) 對(duì) 正樣本對(duì) 距離 d(u, v) 的導(dǎo)數(shù)
        grad_L_pos = -1
        
        # 損失函數(shù) 對(duì) 負(fù)樣本對(duì) 距離 d(u, v') 的導(dǎo)數(shù)
        grad_L_negs = []
        for dist_neg in dist_negs:
            grad_L_negs.append(exp(-dist_neg) / loss_neg)
            
        # 計(jì)算正樣本對(duì)中兩個(gè)樣本的embedding的更新方向
        grad_pos1 = grad_L_pos * compute_distance_gradients(emb[pos1], emb[pos2], dist_pos_)
        grad_pos2 = grad_L_pos * compute_distance_gradients(emb[pos2], emb[pos1], dist_pos_)
        
        # 計(jì)算負(fù)樣本對(duì)中所有樣本的embedding的更新方向
        grad_negs_final = []
        for (grad_L_neg, neg, dist_neg_) in zip(grad_L_negs[1:], negs[1:], dist_negs_[1:]):
            grad_neg0 = grad_L_neg * compute_distance_gradients(emb[neg[0]], emb[neg[1]], dist_neg_)
            grad_neg1 = grad_L_neg * compute_distance_gradients(emb[neg[1]], emb[neg[0]], dist_neg_)
            grad_negs_final.append([grad_neg0, grad_neg1])
            
        # 更新embeddings
        emb[pos1] = update(emb[pos1], -grad_pos1, lr)
        emb[pos2] = update(emb[pos2], -grad_pos2, lr)
        for (neg, grad_neg) in zip(negs, grad_negs_final):
            emb[neg[0]] = update(emb[neg[0]], -grad_neg[0], lr)
            emb[neg[1]] = update(emb[neg[1]], -grad_neg[1], lr)
    
    # 輸出損失
    if ((epoch) % 10 == 0):
        print(epoch + 1, "---Loss: ", sum(loss))
        
    # 繪制二維embeddings
    if ((epoch) % 100 == 0):
        plotall(epoch + 1)