面向大规模网络测量的数据恢复算法：基于关联学习的张量填充

欧阳与点, 谢鲲, 谢高岗, 文吉刚

A Data Recovery Algorithm for Large-Scale Network Measurements: Association Learning Based Tensor Completion

OUYANG Yu-dian, XIE Kun, XIE Gao-gang, WEN Ji-gang

算法1 基于关联学习的张量填充算法ALTC

输入:吞吐量测量张量 $X$ ,往返时延测量张量 $Y$ ,吞吐量测量样本索引集 $Ω$ ,吞吐量缺失样本索引集 $\bar{Ω}$ ,特征维度 $D$ ,卷积核通道数 $C$ ,秩 $R$ ,误差平衡权重 $λ$ ,迭代停止条件StopCondition.

输出:吞吐量估计张量 $\hat{X}$

/*第一步:吞吐量-往返时延关联学习模型(ALM)*/

1:随机初始化关联学习模型参数 $Θ$

2:WHILE StopCondition!= true DO

3: REPEAT

4: $(i, j, k) \leftarrow$ 从 $Ω$ 中选取本轮还未选取过的测量样本索引

5: $y_{: j k}$ , $y_{i : k}$ , $y_{i j :} \leftarrow$ 从往返时延张量 $Y$ 中提取纤维

6: 输入关联学习模型计算吞吐量推测值 $x_{i j k}^{'} = f (y_{: j k}, y_{i : k}, y_{i j :} | Θ)$

7: 通过梯度下降算法优化式(5),更新关联学习模型的参数 $Θ$

8: UNTIL $Ω$ 中所有的测量样本索引都已被选取

9: StopCondition $\leftarrow$ 计算迭代停止条件

10: END WHILE

11: $X^{'} \leftarrow$ 将 $\bar{Ω}$ 中的所有缺失样本索引输入训练好的关联学习模型,计算吞吐量张量的推测值

12: $\tilde{X} \leftarrow$ 根据式(6)计算预填充的吞吐量张量

/*第二步:基于关联学习的张量填充模型(ALTC)*/

13:随机初始化因子矩阵 $A$ , $B$ 和 $C$

14:WHILE StopCondition!= true DO

15: REPEAT

16: $(i, j, k) \leftarrow$ 从 $Ω$ 中选取本轮还未读取过的测量样本索引

17: $a_{i}$ , $b_{j}$ , $c_{k} \leftarrow$ 从因子矩阵中分别提取因子向量

18: 计算吞吐量估计值 ${\hat{x}}_{i j k} = a_{i} \cdot b_{j} \cdot c_{k} = \sum_{r = 1}^{R} a_{i r} b_{j r} c_{k r}$

19: 通过梯度下降算法优化式(8),更新因子矩阵 $A$ , $B$ 和 $C$

20: UNTIL $Ω$ 中所有的测量样本索引都已被读取

21: StopCondition $\leftarrow$ 计算迭代停止条件

22:END WHILE

23: $\hat{X} \leftarrow$ 使用训练好的因子矩阵计算吞吐量张量的估计值