SEACells 代码学习 （2）

Archetypal Analysis 是一种用于数据分析的技术，它旨在找出数据集中的“极端类型”或“原型”（archetypes），并将每个数据点表示为这些原型的混合或组合。这种方法可以揭示数据的潜在结构，尤其是在需要理解数据多样性和极端情况的场景中非常有用。

数据集中的每个观测值（如个体、案例等）被表示为这些原型的加权组合。
这种表示揭示了每个观测值与不同原型之间的关系。

在实现上，Archetypal Analysis 通常涉及以下步骤：

1. 选择原型数量：

首先确定要在数据中寻找多少个原型。这个数目是一个超参数，需要根据数据集的特性和分析目的来确定。

2. 初始化：

随机或使用特定策略选择原型的初始估计。

3. 迭代优化：

使用数学优化方法（如梯度下降、Frank-Wolfe算法等）迭代地更新原型和数据点的表示，以最小化表示误差。

Frank-Wolfe算法是一种用于解决带有线性约束的优化问题的迭代算法。在 _updateA 方法中，它被用于更新分配矩阵 A，这是一个关键步骤，用于在模型中确定如何将各个细胞分配给不同的SEACells（即archetype）。更新 A 矩阵是为了找到最优的细胞到SEACells的分配，从而最小化给定目标函数的值。

 def _updateA(self, B, A_prev):
        """Update step for assigment matrix A.

        Given archetype matrix B and using kernel matrix K, compute assignment matrix A using constrained gradient
        descent via Frank-Wolfe algorithm.

        :param B: (n x k csr_matrix) defining SEACells as weighted combinations of cells
        :param A_prev: (n x k csr_matrix) defining previous weights used for assigning cells to SEACells
        :return: (n x k csr_matrix) defining updated weights used for assigning cells to SEACells
        """
        n, k = B.shape
        A = A_prev

        t = 0  # current iteration (determine multiplicative update)

        # precompute some gradient terms
        t2 = (self.K @ B).T
        t1 = t2 @ B

        # update rows of A for given number of iterations
        while t < self.max_FW_iter:
            # compute gradient (must convert matrix to ndarray)
            G = 2.0 * np.array(t1 @ A - t2)

            # # get argmins - shape 1 x n
            amins = np.argmin(G, axis=0)
            amins = np.array(amins).reshape(-1)

            # # loop free implementation
            e = csr_matrix((np.ones(len(amins)), (amins, np.arange(n))), shape=A.shape)

            A += 2.0 / (t + 2.0) * (e - A)
            t += 1

        return A

    

Frank-Wolfe 算法通过迭代地选择一个方向（在这个案例中是由 e 指定）并更新当前解决方案，逐步优化目标函数。在每次迭代中，算法评估当前解决方案的质量（通过梯度 G），并决定如何改进（通过计算 e 并更新 A）。这种方法允许算法在遵守给定约束的同时，逐步改进解决方案，最终找到满足条件的最优或近似最优解。