精华内容
下载资源
问答
  • 计算方法——共轭梯度法求解线性方程组计算方法上机报告计算方法上机报告1 共轭梯度法求解线性方程组1.1 算法原理及程序框图当线性方程组Ax = b 的系数矩阵A 是对称正定矩阵是,可以采用共轭梯度法对该方程组进行...

    计算方法——共轭梯度法求解线性方程组

    计算方法上机报告

    计算方法上机报告

    1 共轭梯度法求解线性方程组

    1.1 算法原理及程序框图

    当线性方程组Ax = b 的系数矩阵A 是对称正定矩阵是,可以采用共轭梯度法对该

    方程组进行求解,可以证明,式(1)所示的n 元二次函数

    1 T T

    f (x ) x Ax b x (1)

    2

    *

    取得极小值点x 是方程Ax = b 的解。共轭梯度法是把求解线性方程组的问题转化为求

    解一个与之等价的二次函数极小化的问题。从任意给定的初始点出发,沿一组关于矩

    阵A 的共轭方向进行线性搜索,在无舍入误差的假定下,最多迭代n 次(其中n 为矩

    阵A 的阶数),就可求得二次函数的极小点,也就求得线性方程组Ax = b 的解。其迭

    代格式为公式(2) 。

    x(k 1) x(k )  d (k ) (2)

    k

    共轭梯度法中关键的两点是迭代格式(2) 中最佳步长 和搜索方向d (k) 的确定。其

    k

    中 可以通过一元函数f (x(k)+d(k)) 的极小化来求得,其表达式为公式(3) ;取d (0)

    k

    = r(0) = b-Ax (0) ,则d(k+ 1) = r(k+1) + d(k) ,要求d(k+ 1)满足 (d(k+ 1) , Ad(k)) = 0 ,可得 的表达

    k k

    式(4) 。

    k T k

    r  d  

    k k T k (3)

    d   Ad  

    r(k 1)T Ad (k )

      (4)

    k d (k )T Ad (k )

    经过一系列的证明和简化,最终可得共轭梯度法的计算过程如下,计算程序框图

    如图1。

    (1) 给定初始计算向量x(0) 即精度>0 ;

    (2) 计算r(0) = b -Ax (0) ,取d(0) = r(0) ;

    (3) for k =0 to n- 1 do

    展开全文
  • 迭代 syms x y; % F = inline(['x + x * sin(y) - 2.2378';'x^2 - y + 2*cos(y)'], 'x', 'y'); F = [x + x * sin(y);x^2 - y + 2*cos(y)]; x0 = [0 1]; eps = 1e-5; [r, n] = netNewtonfun(F, x0, eps) function ...

    迭代法

    syms x y;
    % F = inline(['x + x * sin(y) - 2.2378';'x^2 - y + 2*cos(y)'], 'x', 'y');
    F = [x + x * sin(y);x^2 - y + 2*cos(y)];
    x0 = [0 1];
    eps = 1e-5;
    [r, n] = netNewtonfun(F, x0, eps)
    
    function [r, n] = netNewtonfun(F, x0, eps)
    
    if nargin == 2
        eps = 1e-6;
    end
    
    x0 = transpose(x0);
    n = 1;
    tol = 1;
    while tol>eps
        r = subs(F, findsym(F), x0);
        tol = norm(r - x0);
        n = n + 1;
        x0 = r;
        if n>10000
            disp('迭代步数太多,可能不收敛!');
            return;
        end
    end
    end
    
    

    牛顿迭代法
    步骤为:
    (1) 选取初始点x(0),最大迭代次数N和精度要求eps,置k = 0。
    (2) 计算F(x(k))和dF(x(k))。
    (3) 如果Jacobi矩阵dF(x(k))为奇异矩阵,则停止计算;否则解:

    x(k + 1) = x(k) - F(x(k))/dF(x(k))
    

    (4) 如果 | x(k + 1) - x(k) | < eps,则停止计算
    (5) 如果 k = N,则停止计算;否则,置 k = k + 1,转到(2)。
    matlab代码如下:

    x0 = [-0.1 -0.2]';
    eps = 1e-6;
    nmax = 20;
    [x, n, error] = newtoneqs(@li_fun, @Fli_fun, x0, eps, nmax)
    
    function [x, n, error] = newtoneqs(F, JF, x0, eps, nmax)
    x = x0;
    Y = feval('li_fun', x0);
    for k = 1: nmax
        J = feval('Jli_fun', x0);
        Q = x0 - (J \ Y);
        Y = feval('li_fun', Q);
        error = norm(Q - x0);
        x0 = Q;
        x = [x x0];
        n = k;
        if error < eps
            break
        end
    end
    end
    
    function F = li_fun(X)
    x = X(1);
    y = X(2);
    F = zeros(2, 1);
    F(1) = x^2 - y - 0.2;
    F(2) = y^2 - x - 0.3;
    end
    
    function J = Jli_fun(X)
    x = X(1);
    y = X(2);
    J = [2 * x, -1;-1, 2*y];
    end
    

    梯度下降法

    syms x y;
    F = [x^2 - 2^x - y + 0.5;x^2 + 4*y^2 - 4];
    x0 = [1 0];
    h = 1e-8;
    [r, n] = FastDownGroudfun(F, x0, h)
    function [r, n] = FastDownGroudfun(F, x0, h, eps)  % h:步长
    format long;
    if nargin == 3
        eps = 1e-6;
    end
    
    m = length(x0);
    x0 = transpose(x0);
    n = 1;
    tol = 1;
    while tol > eps
        fx = subs(F, findsym(F), x0);
        J = zeros(m, m);
        for i = 1: m
            x1 = x0;
            x1(i) = x1(i) + h;
            J(:,i) = (subs(F, findsym(F), x1) - fx)/h;
        end
        lamda = fx/sum(diag(transpose(J) * J));
        r = x0 - J*lamda;
        fr = subs(F, findsym(F), r);
        tol = dot(fr, fr);
        x0 = r;
        n = n + 1;
        if n>100000
            disp('迭代次数太多,可能不收敛!');
            return;
        end
    end
    format short;
    end
    
    展开全文
  • 求解对称非线性方程组的 混合共轭梯度方法,蔡晓梅,顾广泽,本文主要求解对称非线性方程组问题.利用混合梯度共轭修正方法(HS方法),结合适当的线搜索方法,建立了无导数的求解对称非线性方程�
  • mulStablePoint 用不动点迭代法求非线性方程组的一个根 mulNewton 用牛顿法法求非线性方程组的一个根 ...mulConj 用共轭梯度法非线性方程组的一组解 mulDamp 用阻尼最小二乘法求非线性方程组的一组解
  • 共轭梯度法 (CG) 解线性方程组

    千次阅读 2019-01-08 14:58:22
    共轭梯度法 (CG) 解线性方程组 Ax=b, 方阵 A 必须是对称正定的

    求解线性方程组: A x = b Ax = b Ax=b其中 A ∈ S + + m ⊂ R m × m A\in S^m_{++} \subset \R^{m\times m} AS++mRm×m b ∈ R m b \in \R^m bRm

    共轭梯度法的matlab实现:

    function [x] = CG(A,b)
    
    x = 0;   // 迭代初值
    r = b;   // 初始残差
    i_max = 50;  // 最大迭代次数
    yita = 1e-6; // 残差限度
    
    i = 0;
    while sqrt(r'*r)> yita && i<i_max
        i = i+1;
        if i == 1
            p = r;
        else
            beta = r'*r/(r_before'*r_before);
            p = r + beta*p;
        end
        alpha = r'*r/(p'*A*p);
        x = x + alpha*p;
        r_before = r;
        r = r - alpha*A*p;
    end
    

    短短几行,效果奇佳。

    测试:

    A = rand(20,20);
    A = A*A';
    
    xs = randn(20,1);
    
    b = A*xs;
    
    norm(xs - CG(A,b))
    

    输出:

    ans =
    
       1.8305e-08
    

    需要注意的是,方阵 A 必须是对称正定的,否则无法得到正确结果例如:

    A = rand(20,19);
    A = A*A';  % 此时 A 的秩为 19, 非满秩,半正定!
    
    xs = randn(20,1);
    
    b = A*xs;
    
    norm(xs - CG(A,b))
    

    误差就很大了!

    ans =
    
        0.3442
    
    展开全文
  • 共轭梯度法是一种算法,用于求解线性方程组的特定系统,即矩阵且方程组的数值解。 共轭梯度法通常实现为,适用于太大而无法通过直接实现或其他直接方法(例如Cholesky分解)处理的稀疏系统。 成本函数 假设我们要求...
  • 为了提高求解大规模非线性方程组的算法效率,克服存储需求大、算法复杂等缺点,本文在经典CD共轭梯度法基础上提出一个新的搜索方向公式,并结合线搜索技术和投影技术,设计一种修正的CD共轭梯度算法。该算法优点:(1)能够...
  • 非线性方程组求解matlab程序

    热门讨论 2010-02-04 16:55:12
    mulStablePoint 用不动点迭代法求非线性方程组的一个根 mulNewton 用牛顿法法求非线性方程组的一个根 ...mulConj 用共轭梯度法非线性方程组的一组解 mulDamp 用阻尼最小二乘法求非线性方程组的一组解
  • 提供了不精确牛顿类的仿射内点离散共轭梯度法求解有界变量约束的非线性方程系统.通过构建仿射离散共轭梯度路径结合不精确牛顿步获得了搜索方向,并使用内点回代线搜索技术获得迭代步长.在合理的条件下,证明了算法的...
  • 目前主流的方法有两种:随机梯度下降 (简称 SGD,stochastic gradient decent) 和交替最小二乘法 (简称 ALS,alternating least squares),而本文的重点是后者,在阐述其基本原理的同时,引入共轭梯度法来加速模型...

    协同过滤是一类基于用户行为数据的推荐方法,主要是利用已有用户群体过去的行为或意见来预测当前用户的偏好,进而为其产生推荐。能用于协同过滤的算法很多,大致可分为:基于最近邻推荐和基于模型的推荐。其中基于最近邻推荐主要是通过计算用户或物品之间的相似度来进行推荐,而基于模型的推荐则通常要用到一些机器学习算法。矩阵分解可能是被研究地最多的基于模型的推荐算法,在著名的 Netflix 大赛中也是大放异彩,核心思想是利用低维隐向量为每个用户和物品建模,进而推测用户对物品的偏好。现在的关键问题是如果要用矩阵分解的方法,该如何训练模型,即该如何获得隐向量? 目前主流的方法有两种:随机梯度下降 (简称 SGD,stochastic gradient decent) 和交替最小二乘法 (简称 ALS,alternating least squares),而本文的重点是后者,在阐述其基本原理的同时,引入共轭梯度法来加速模型的训练。

    矩阵分解想要解决的问题

    这里采用最常见的矩阵分解技术,由 SVD 演化而来。设共有 \(m\) 个用户,\(n\) 个物品,那么用户 - 物品 - 评分矩阵为 \(R \in \mathbb{R}^{m \times n}\) ,其中评分表示用户对物品的偏好。这个矩阵通常非常稀疏,其中大部分的评分元素都是缺失的,而我们的任务就是预测里面的缺失值。对于每个用户 \(u\) 设定一个用户向量 \(x_u \in \mathbb{R}^f\) ,每个物品 \(i\) 设定一个物品向量 \(y_i \in \mathbb{R}^f\) ,那么预测值用二者的内积表示 \(\hat{r}_{ui} = x_u^{\top}y_i\) 。于是可写出想要优化的目标函数:
    \[ \mathcal{L} \;=\; \min_{x_*,y_*} \sum\limits_{r_{u,i}\,\text{is}\,\text{known}} (r_{ui} - x_u^\top y_i)^2 + \lambda \left(\sum\limits_{u}||x_u||^2 + \sum\limits_{i}||y_i||^2 \right) \tag{1.1} \]

    想要最小化 \((1.1)\) 式最常用的方法就是 SGD (其中 \(\gamma\) 是学习率):
    \[ e_{ui} \overset{def}{=} r_{ui} - x_u^\top y_i \\[1ex] x_u \leftarrow{x_u + \gamma \,(e_{ui} \cdot y_i - \lambda \cdot x_u)} \\[1ex] y_i \leftarrow{y_i + \gamma \,(e_{ui} \cdot x_u - \lambda \cdot y_i)} \]

    SGD 是一种迭代优化方法 (iterative method),而另一种方法,即本文的主角 ALS ,则是一种直接法 (direct method)。由于 \((1.1)\) 式中 \(x_u\)\(y_i\) 都未知,所以该函数非凸,难以直接优化。然而如果将所有的 \(y_i\) 固定住视其为常数,那么 \((1.1)\) 式就变成了一个 关于 \(x_u\) 的最小二乘问题,可以直接求出解析解。于是可以先固定 \(y_i\) 求出 \(x_u\) ,再固定 \(x_u\) 求出 \(y_i\) ,二者不断交替,这个流程不断重复直至收敛。因而 ALS 全称为交替最小二乘法 (alternating least squares),这其实有点类似于 EM 算法中 E 步和 M 步的交替求解。

    下面详细推导 ALS 的算法流程,上面已经定义了用户向量 \(x_u \in \mathbb{R}^f\) ,物品向量 \(y_i \in \mathbb{R}^f\) ,则所有用户可组合成一个矩阵 \(X \in \mathbb{R}^{m \times f}\) ,所有物品组合成一个矩阵 \(Y \in \mathbb{R}^{n \times f}\) ,整个评分矩阵为 \(R = XY^\top \in \mathbb{R}^{m \times n}\) 。则对 \((1.1)\) 式固定 \(Y\)\(x_u\) 求偏导:
    \[ \begin{align*} \frac{\partial \mathcal{L}}{\partial\,x_u} &= -2\sum\limits_{i \in r_{u*}} (r_{ui} - x_u^\top y_i)y_i + 2 \lambda\, x_u = 0 \quad \implies \\ x_u &= \left(\sum\limits_{i \in r_{u*}} y_i y_i^\top + \lambda\, I\right)^{-1} \sum\limits_{i \in r_{u*}}r_{ui}y_i = (Y_u^\top Y_u + \lambda \,I)^{-1}Y_u^\top R_u \tag{1.2} \end{align*} \]
    其中 \(r_{u*}\) 表示用户 \(u\) 评分过的所有物品, \(Y_u \in \mathbb{R}^{|r_{u*}| \times f}\) 表示用户 \(u\) 评分过的所有物品的矩阵,\(R_u \in \mathbb{R}^{|r_{u*}|}\) 表示用户 \(u\) 所有的物品评分向量。同理固定 \(X\)\(y_i\) 求偏导:
    \[ y_i = \left(\sum\limits_{u \in r_{*i}} x_u x_u^\top + \lambda\, I\right)^{-1} \sum\limits_{u \in r_{*i}}r_{ui}x_u = (X_i^\top X_i + \lambda \,I)^{-1}X_i^\top R_i \tag{1.3} \]

    ALS 相对于 SGD 有两个好处:

    (1) 注意到 \((1.2)\)\((1.3)\) 式每个 \(x_u\)\(y_i\) 的计算都是独立的,因而可以并行计算提高速度。

    (2) 对于隐式反馈数据集来说,用户和物品的组合太多,分分钟到亿级别。若有10000个用户,10000个物品,则会有 \(10000 \times 10000 = 10^8\) 种组合,用 SGD 一个个迭代是比较困难的。当然也可以为每个用户进行少量负采样,但这不是本文的重点,在此略过。而用 ALS 则可以通过一些矩阵转换技巧来高效计算,不过在这之前,先来看下何为隐式反馈数据集?

    显式反馈 Vs. 隐式反馈

    上文 ALS 的推导使用的是显式反馈数据,特点是都有显式评分,比如 MovieLens 数据集中的 1-5 分或是豆瓣上的 1 到 5 星。这些评分很能反映用户对物品的偏好,像豆瓣上打 5 星表示力荐,打 1 星表示很差。相较而言,隐式反馈数据大都来源于用户的行为,如物品的购买记录,网页的浏览记录,视频的观看时长等等。隐式反馈一般有如下特点:

    (1) 数据总量大。比如很多人都在淘宝上买东西留下记录,却很少人会去给好评差评;每天在网上浏览了很多文章,却很少点赞。

    (2) 没有负反馈。这点是比较致命的,比如看过一部电影代表对其的偏好,但若没看过一部电影并不代表不喜欢这部电影,可能是在待观看列表里面,然而从数据中这一点无法得知,这导致数据的噪音大。而如果只用有反馈的数据进行建模,会导致严重的过拟合。

    如上面第一点所述,实际生活中显式反馈的评分数据是比较少的,而隐式反馈数据却非常丰富,因而重要性越来越高。为了解决其没有负反馈的问题,这里采用 Hu 等人在论文Collaborative Filtering for Implicit Feedback Datasets中描述的方法,引入用户对于物品的偏好系数 \(p_{ui}\) :
    \[ p_{ui} = \begin{cases} \;1 \quad \text{if}\;\; r_{ui} > 0 \\ \;0 \quad \text{if}\;\; r_{ui} = 0 \end{cases} \]
    \(r_{ui}\) 表示用户对物品的反馈,如购买、搜索等行为,上式表明只要有反馈,\(p_{ui}\) 皆为 \(1\) 。此外还引入用户对于物品的置信度 $c_{ui} = 1 + \alpha, r_{ui} $, 可以看出即使 \(r_{ui} = 0\)\(c_{ui}\) 也不为零,并且随着 \(r_{ui}\) 的增长而增长。Hu 的论文中的场景是电视剧推荐,因而 \(r_{ui}\) 表示观看时长或收看次数。于是写出目标函数:
    \[ \mathcal{L}_\text{implicit} \;=\; \min_{x_*,y_*} \sum\limits_{u,i} c_{ui}\left(p_{ui} - x_u^\top y_i \right)^2 + \lambda \left(\sum\limits_{u}||x_u||^2 + \sum\limits_{i}||y_i||^2 \right) \tag{1.4} \]
    \((1.4)\)\((1.1)\) 式虽然长得很像,但实际使用会有很大区别,\((1.1)\) 式仅考虑用户评过分的样本,而 \((1.4)\) 式是考虑所有用户和物品的组合,比如 MovieLens 1M 数据集有100万样本,6000个用户,3500部电影,总的组合数是 \(6000 \times 3500 = 2.1 \times 10 ^7\) ,是样本数的 21 倍,如果用 SGD 那将会比显式数据集慢很多。

    另外仔细观察 \((1.1)\) 式,固定所有的 \(y_i\) ,求解最优的 \(x_u\) ,从形式上来说就是一个 Ridge Regression 问题,因而 \((1.4)\) 式相当于为每个用户 - 物品组合加上了权重 \(c_{ui}\),因而该算法也被称为 WRR (weighted ridge regression) 。

    要优化 \((1.4)\) 式,还是 ALS 的思路,固定 \(Y\)\(x_u\) 求偏导:
    \[ \begin{align*} \frac{\partial \mathcal{L}_\text{implicit}}{\partial\, x_u} &= -2\sum\limits_{u,i} c_{ui}(p_{ui} - x_u^\top y_i)y_i + 2 \lambda\, x_u = 0 \quad \implies \\ x_u &= \left(\sum\limits_{u,i} c_{ui}y_iy_i^\top + \lambda\,I\right)^{-1}\sum\limits_{u,i} c_{ui}p_{ui}y_i \tag{1.5} \\[1ex] &= (Y^\top C^uY + \lambda \,I)^{-1}Y^\top C^up(u) \tag{1.6} \end{align*} \]

    其中 \(Y \in \mathbb{R}^{n \times f}\) 为所有物品隐向量组成的矩阵,\(C^u \in \mathbb{R}^{n \times n}\) 为对角矩阵,其对角线上的元素为用户 \(u\) 对所有物品的置信度 \(c_{ui}\),即 \(C^u_{ii} = c_{ui}\) ,由上文可知因为 \(r_{ui} \geqslant 0\) ,所以 \(c_{ui} \geqslant 1\)\(p(u) \in \mathbb{R}^n\) ,其元素为用户 \(u\) 对所有物品的偏好 \(p_{ui}\)

    \((1.6)\) 式中的 \(Y^\top C^u Y\) 的计算复杂度达到了 \(\mathcal{O}(f^2n)\) ,在 \(n\) 很大的情况下是难以承受的,因而可以拆分成 \(Y^\top C^u Y = Y^\top Y + Y^\top (C^u - I)Y\),对于每个用户 \(u\) 来说, \(Y^\top Y\) 都是一样的,因而可以提前计算,而 \(C^u\) 对角线的元素大部分都为 \(1\) ,因而 \(C^u - I\) 是一个稀疏矩阵,整体 \(Y^\top C^u Y\) 的计算复杂度降到 \(\mathcal{O}(f^2n_u)\)\(n_u\) 是用户 \(u\) 产生过行为的物品数量,通常 \(n_u << n\)

    同理,固定 \(X\)\(y_i\) 求偏导得:
    \[ \begin{align*} y_i &= \left(\sum\limits_{u,i} c_{ui}x_u x_u^\top + \lambda\,I\right)^{-1}\sum\limits_{u,i} c_{ui}p_{ui}x_u \\[1ex] &= (X^\top C^{\,i} X + \lambda \,I)^{-1} X^\top C^{\,i} p(i) \end{align*} \]

    下面给出 \((1.6)\) 式的 Python 代码:

    import numpy as np
    from scipy.sparse import csr_matrix
    
    def ALS(dataset, X, Y, reg, n_factors, alpha=10, user=True):
        if user:
            data = dataset.train_user # data是所有用户-物品-标签的嵌套字典,形如 {1:{2:1, 3:1, 5:1 ...}, 2: {2:1, 3:1 ...} ...}
            m_shape = dataset.n_items
        else:
            data = dataset.train_item # data是所有物品-用户-标签的嵌套字典
            m_shape = dataset.n_users
    
        YtY = Y.T.dot(Y) + reg * np.eye(n_factors)
        for s in data:
            Cui_indices = list(data[s].keys())
            labels = list(data[s].values())
            Cui_values = np.array(labels) * alpha
            Cui = csr_matrix((Cui_values, (Cui_indices, Cui_indices)), shape=[m_shape, m_shape])  # 构建 C^u - I 稀疏矩阵
            pui_indices = list(data[s].keys())
            pui = np.zeros(m_shape)
            pui[pui_indices] = 1.0
            A = YtY + np.dot(Y.T, Cui.dot(Y))
    
            C = Cui + sparse.eye(m_shape, format="csr")
            cp = C.dot(pui)
            b = np.dot(Y.T, cp)
            X[s] = np.linalg.solve(A, b)

    另外根据 \((1.5)\) 式也可以拆分成 :
    \[ \begin{align*} x_u &= \left(\sum\limits_{u,i} c_{ui}y_iy_i^\top + \lambda\,I\right)^{-1} \sum\limits_{u,i} c_{ui}p_{ui}y_i \\[1ex] &= \left(\sum\limits_{u,i} y_iy_i^\top + \sum\limits_{u,i} \left(c_{ui} - 1\right)y_iy_i^\top + \lambda\,I\right)^{-1} \sum\limits_{u,i} c_{ui}p_{ui}y_i \qquad \#\; 对于 p_{ui} = 0 的物品,c_{ui}-1=0 \\[1ex] &= \left(Y^\top Y + \sum\limits_{i \in r_{u*}} \left(c_{ui} - 1\right)y_iy_i^\top + \lambda\,I\right)^{-1} \sum\limits_{i \in r_{u*}} c_{ui}\cdot1 \cdot y_i \qquad\qquad\qquad\qquad\qquad\qquad\qquad (1.7) \end{align*} \]

    所以还有另一种代码更少且更快的实现方式:

    def ALS(dataset, X, Y, reg, n_factors, alpha=10, user=True):
        if user:
            data = dataset.train_user
        else:
            data = dataset.train_item
    
        YtY = Y.T.dot(Y)
        for s in data:
            A = YtY + reg * np.eye(n_factors)
            b = np.zeros(n_factors)
            for i in data[s]:
                factor = Y[i]
                confidence = 1 + alpha * data[s][i]
                A += (confidence - 1) * np.outer(factor, factor) # 计算外积
                b += confidence * factor
    
            X[s] = np.linalg.solve(A, b)
    假设 \((Y^\top C^uY + \lambda \,I)^{-1}\) 的矩阵求逆操作复杂度为 \(\mathcal{O}(f^3)\),那么所有用户 \(u\) 的总体计算复杂度为 \(\mathcal{O}(f^2 \mathcal{N}_u + f^3m)\) ,其中 \(\mathcal{N}_u = \sum_un_u\) ,为所有用户行为总量。可以看出该算法的计算复杂度虽然与总体数据量呈线性增长关系,然而会随着 \(f\) 的增加呈指数增长。 总之虽然比原来有改善但其实还是比较慢,所以接下来就轮到共轭梯度法出场了,但在此之前,先来 看看传统的梯度下降法有什么问题。

    梯度下降法的问题

    我们的目标是最小化 \((1.4)\) 式,使得推荐结果和真实值越接近越好,传统的梯度下降法有两个缺点: 一是数据量大时迭代慢,二是函数等高线呈椭球面时,容易呈现一种来回震荡的趋势。下图显示出一种典型的“之字形”优化路径,同样的迭代方向可能不只走了一次,这造成了优化效率低下。

    www.wityx.com

    而比较理想的情况应该是这样,每一步的搜索方向都向最优点的方向靠拢:

    www.wityx.com

    因此很自然的想法是,能不能找一组 n 个迭代方向,每次沿着一个方向只走一次达到该方向的最优解,那么最多走 n 次就能收敛到最优解了。这种方法究竟有没有呢?当然是有的(汗,要是没有我写这篇文章还有什么意义。。),就是共轭梯度法嘛。

    共轭梯度法 (conjugate gradient)

    共轭梯度法天性适合求解大规模稀疏线性方程组问题,而本文中的矩阵分解恰好可转化为这一类问题。首先来看什么是“共轭”,设 \(\boldsymbol{A}\) 为对称正定矩阵,对于两个非零向量 \(\boldsymbol{u}\)\(\boldsymbol{v}\) ,若 \(\boldsymbol{u}^\top \boldsymbol{A} \boldsymbol{v} = 0\) ,则称 \(\boldsymbol{u}\)\(\boldsymbol{v}\) 关于 \(\boldsymbol{A}\) 共轭。对于 \(n\) 维二次型函数 \(f(\boldsymbol{x}) = \frac12 \boldsymbol{x^\top A x} - \boldsymbol{x^\top b}\)\(\boldsymbol{x} \in \mathbb{R}^n\) ,最好的迭代方向为关于 \(\boldsymbol{A}\) 的共轭方向,每次迭代其中一个方向,那么最多 \(n\) 步之后就能到达最优点。

    于是剩下的问题是如何得到一组关于 \(\boldsymbol{A}\) 的共轭方向? 所谓的共轭梯度法可理解为 “共轭方向 + 梯度 $\Longrightarrow $ 新共轭方向” ,这样就避免了需要预先给定一组共轭方向,而是每一轮迭代中根据上一轮共轭向量和梯度的线性组合来确定新方向,这样就节约了很多空间。

    对于上述的二次型函数,其梯度为 \(\nabla f(\boldsymbol{x}) = \boldsymbol{Ax} - \boldsymbol{b}\) ,若令其为零则等价于求方程 \(\boldsymbol{Ax} = \boldsymbol{b}\) 的解。在上文 ALS 算法中是直接矩阵求逆得 \(\boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b}\) ,而共轭梯度法作为一种迭代方法来说,设第 \(k\) 步的搜索方向为 \(\boldsymbol{p}_k\) ,则第 \(k + 1\) 步的解为 \(\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \alpha_k \boldsymbol{p}_k\) 。新的共轭方向为上一轮共轭方向和负梯度的线性组合,即 \(\boldsymbol{p}_{k+1} = - \nabla f( \boldsymbol{x} ) + \beta_k \boldsymbol{p}_k\) 。设残差 \(\boldsymbol{r} = \boldsymbol{b} - \boldsymbol{A x}\) ,则对于二次型函数 \(f(\boldsymbol{x})\) 来说,负梯度就是残差,则 \(\boldsymbol{p}_{k+1} = \boldsymbol{r}_k + \beta_k \boldsymbol{p}_k\) 。而对于新一轮的残差: \(\boldsymbol{r}_{k+1} = \boldsymbol{b} - \boldsymbol{A}\boldsymbol{x}_{k+1} = \boldsymbol{b} - \boldsymbol{A}(\boldsymbol{x}_k + \alpha_k \boldsymbol{p}_k) = \boldsymbol{r}_k - \alpha_k \boldsymbol{Ap}_k\) 。于是完整的共轭梯度法如下所示:

    www.wityx.com

    \(\boldsymbol{p}\) 即为每一轮的共轭搜索方向,其初始方向依据梯度下降法设定为梯度的负方向,即残差 \(\boldsymbol{p}_0 = \boldsymbol{r}_0\)。由 \(\boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b}\) ,那么根据 \((1.6)\)\((1.7)\) 式:
    \[ \begin{align*} \boldsymbol{A} &= Y^\top C^uY + \lambda \,I = Y^\top Y + \sum\limits_{i \in r_{u*}} \left(c_{ui} - 1\right)y_iy_i^\top + \lambda\,I \\[1ex] \boldsymbol{b} &= Y^\top C^up(u) = \sum\limits_{i \in r_{u*}} c_{ui}\cdot1 \cdot y_i \\[1ex] \boldsymbol{r} &= \boldsymbol{b} - \boldsymbol{Ax} = \sum\limits_{i \in r_{u*}}\left(c_{ui} - (c_{ui} - 1)y_i^\top x\right)\cdot y_i - (Y^\top Y + \lambda\,I)^\top x \end{align*} \]

    下面给出共轭梯度法的实现代码:

    def conjugate_gradient(dataset, X, Y, reg, n_factors, alpha=10, cg_steps=3, user=True):
        if user:
            data = dataset.train_user
        else:
            data = dataset.train_item
    
        YtY = Y.T.dot(Y) + reg * np.eye(n_factors)
        for s in data:
            x = X[s]
            r = -YtY.dot(x)
            for item, label in data[s].items():
                confidence = 1 + alpha * label
                r += (confidence - (confidence - 1) * Y[item].dot(x)) * Y[item]  # b - Ax
    
            p = r.copy()
            rs_old = r.dot(r)
            if rs_old < 1e-10:
                continue
    
            for it in range(cg_steps):
                Ap = YtY.dot(p)
                for item, label in data[s].items():
                    confidence = 1 + alpha * label
                    Ap += (confidence - 1) * Y[item].dot(p) * Y[item]
    
                # standard CG update
                alpha = rs_old / p.dot(Ap)
                x += alpha * p
                r -= alpha * Ap
                rs_new = r.dot(r)
                if rs_new < 1e-10:
                    break
                p = r + (rs_new / rs_old) * p
                rs_old = rs_new
            X[s] = x

    完整代码可见推荐系统库 LibRecommender 中的实现

    从计算效率上来看,共轭梯度法介于梯度下降法和牛顿法之间,克服了梯度下降法收敛慢的问题,也避免了牛顿法需要计算 Hessian 矩阵的缺点。其计算复杂度为 \(\mathcal{O}(\mathcal{N}_u\, E)\) ,空间复杂度为 \(\mathcal{O}(\mathcal{N}_u)\), 其中\(E\) 为迭代次数,而 \(\mathcal{N}_u = \sum_un_u\) ,为所有用户行为总量, 通常每个用户只对少量的物品产生行为,因而可以看到共轭梯度法充分利用了数据的稀疏性,提高了计算效率。

    上文提到共轭梯度法最多在 \(n\) 步内即可收敛,然而对于高维数据 (超过百万维的数据并不鲜见) 而言,这依然不能让人满意。不过可以证明,若正定矩阵 \(\boldsymbol{A}\)\(i\) 个不同的特征值,那么共轭梯度法最多可在 \(i\) 步内收敛,这样又大大提高了优化效率。下面使用 MovieLens 1m 数据集进行测试,并与传统的 ALS 进行比较,\(f\) 统一设为 \(100\), 评估指标为 ROC 下 AUC,下图显示共轭梯度法在迭代 3 步后就已经接近收敛了 (注: 这里的 3 步指的是一个 epoch 内的迭代步数,而非 3 个 epoch):

    www.wityx.com

    接下来对比训练速度,共轭梯度法展现出惊人的速度,随着 \(f\) 的增长训练时间几乎不变,而相比之下传统 ALS 的训练时间增长神速,可见 \(f\) 越大,提升越明显:

    www.wityx.com

    /

    展开全文
  • 共轭梯度法求解带约束的非线性方程组,有两个测试问题
  • 通过为 bicgstab 提供函数句柄来求解线性方程组,用函数句柄代替系数矩阵 A 来计算 A*x。gallery 生成的 Wilkinson 测试矩阵之一是 21×21 三对角矩阵。预览该矩阵。A = gallery('wilk',21)A = 21×2110 1 0 0 0 0 0...
  • 线性方程组共轭梯度算法的MATLAB程序
  • 共轭梯度法简介

    2019-11-12 18:39:21
    共轭梯度法简介 关键词:共轭梯度法;预处理;收敛分析 文章目录共轭梯度法简介introductionnotationThe Quadratic Form(二次型)The Method of Steepest Descent ...共轭梯度法求解稀疏线性方程组最...
  • 共轭梯度法(CGV)

    2018-04-21 17:24:13
    此程序为Fortran语言编写的最小二乘共轭梯度算法,可求解非正定对称方程组,此算法收敛速度快,适合求解大型线性方程组
  • 无约束优化-----共轭梯度法 文章目录无约束优化-----共轭梯度法1线性共轭方向法二次函数极小值问题的共栀方向法共栀方向的定义共轭...共轭梯度法是用来求解线性方程 Ax=bAx = bAx=b ,称为线性共轭方向法。后来,有人
  • 共轭梯度法

    2014-10-11 21:26:00
    共轭梯度法(英语:Conjugate gradient method),是求解数学特定线性方程组的数值解的方法,其中那些矩阵为对称和正定。共轭梯度法是一个迭代方法,它适用于稀疏矩阵线性方程组,因为这些系统对于像Cholesky分解...
  • 由于求解本问题等价于一个严格凸泛函的极小化问题,所以本文中所提到的多重网格法均采用以下三种非线性无约束最优化方法:Polack-Ribiere共轭梯度法,Hooke-Jeeves模式搜索法及不含线搜索的SSC梯度法作为非线性磨光...
  • 共轭梯度法的推导与完整算法

    万次阅读 多人点赞 2017-10-09 19:51:17
    共轭梯度法学习自知乎:https://www.zhihu.com/question/27157047和非线性规划课程简介在数值线性代数中,共轭梯度法是一种求解对称正定线性方程组Ax=b的迭代方法。事实上,求解Ax=b等价于求解: min||Ax−b||22min|...
  • 最优化共轭梯度法的matlab代码实现,可以用于求解非线性方程的解非约束性最优化问题
  • 它仅需利用一阶导数信息,既克服了梯度下降法收敛慢的缺点,又避免了牛顿法需要存储和计算海塞矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。...
  • http://blog.csdn.net/pipisorry/article/details/39891197共轭梯度法(Conjugate Gradient)共轭梯度法(英语:Conjugate gradient method),是求解数学特定线性方程组的数值解的方法,其中那些矩阵为对称和正定。...
  • python实现共轭梯度法

    千次阅读 2017-10-23 10:58:53
    它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。...
  • 共轭梯度法原理与实现

    万次阅读 多人点赞 2015-05-29 23:24:47
    作者:金良(golden1314521@gmail.com) csdn博客: 共轭...定义 共轭方向的性质 共轭方向法 算法描述 算法的收敛性 搜索步长kalpha_k的确定 共轭梯度法 共轭梯度法的原理 共轭梯度算法描述 共轭梯度算法Python实现 r
  • 最优化方法-共轭梯度法

    千次阅读 2019-03-31 17:16:23
    共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出的。其基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜素,求出目标函数的极小点。根据共轭...
  • 为了更加高效求解大规模非线性单调方程组,克服其他算法存在的如算法复杂、编程难、储存量大等不足,在传统三项HS算法基础上,设计了一个新的搜索方向,并采用投影技术和新型线搜索构建了修正HS投影算法。该算法不依赖...
  • 共轭梯度法(Conjugate Gradient)

    千次阅读 2019-03-03 16:34:18
    它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。...
  • 最速下降法和共轭梯度法

    千次阅读 2017-09-07 11:49:36
    利用最速下降法求解对称正定矩阵的线性方程组
  • ## 求助 matlab求解非线性多元方程组

    千次阅读 2019-05-10 15:11:20
    求助 matlab求解非线性多元方程组 方程如下: Q1=5.7345e+04; Q2=7.1642e+04; Q3=9.1609e+06; Q4=5.8704e+12; Kw=1.0030e-14; BT=0.0185; x×y-Kw=0 B1-Q1×B0×y=0 B2-Q2×B0^2×y=0 B3-Q3×B0^3×y=0 B4-Q4×B0^4×...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,244
精华内容 497
关键字:

共轭梯度法求解非线性方程组