机器学习基础3-Softmax回归及C++实现

多分类问题

多分类问题在生活中很常见。例如,音乐可以被分类为民谣,古典,金属,流行等等。上一章介绍的二项逻辑回归可以很好的解决二分类问题,针对多分类问题二项逻辑回归就不太适用,Softmax回归可以很好的解决多分类问题。

Softmax回归模型

设特征数量为 $n$ 即,特征为 $x$,特征的参数为 $\theta$ ,我们定义如下:

\begin{align} \\ x & = \begin{bmatrix} 1 \ x_1 \ \cdots \ x_n \end{bmatrix} \\ \\ \theta & = \begin{bmatrix} \theta_0 \\ \theta_1 \\ \vdots \\ \theta_n \end{bmatrix} \\ \\ x\theta & = \theta_0 + \theta_1x_1 + \theta_2x_2 + \cdots + \theta_nx_n \\ \\ \end{align}

在在多分类问题中 $y$ 可以取 $k$ 个不同的值,也就是 $y\in\{0,1,2,...,k-1 \}$ 。因为每个类别都需要一个特征参数 $\theta$ ,所以有:

\begin{align} \\ \Theta & = \begin{bmatrix} \theta^{0} \ \theta^{1} \ \cdots \ \theta^{k-1} \end{bmatrix} \\ \end{align}

针对多分类问题,我们的概率函数应该给出每一种分类结果的概率,所以我们的概率函数应该输出一个 $k$ 维的向量,我们定义概率函数如下:

\begin{align} \\ h_\Theta(x) & = \begin{bmatrix} p(y=0|x;\Theta) \\ p(y=1|x;\Theta) \\ \vdots \\ p(y=k-1|x;\Theta) \end{bmatrix} = \frac{1}{\sum_{l=0}^{k-1}e^{x\theta^l}} \begin{bmatrix} e^{x\theta^0} \\ e^{x\theta^1} \\ \vdots \\ e^{x\theta^{k-1}} \end{bmatrix} \\ \end{align}

注意 $\frac{1}{\sum_{l=0}^{k-1}e^{x\theta^l}}$ 这一项为对概率分布进行归一化,使得所有概率和为1。

设训练样本数为 $m$,训练样本集为 $X$ ,训练输出集为 $Y$ ,如下: \begin{align} X & = \begin{bmatrix} x^{0} \\ x^{1} \\ \cdots \\ x^{m-1} \end{bmatrix} \\ \\ Y & = \begin{bmatrix} y^{0} \\ y^{1} \\ \vdots \\ y^{m-1} \end{bmatrix} \\ \end{align}

我们的目标是已知 $X$ 和 $Y$ 的情况下得到最优的 $\Theta$。

似然函数

哪个 $\Theta$ 是最优的?我们需要先定义似然函数:

\begin{align} \\ L(\Theta) &= \prod_{i=0}^{m-1} p(y^i \mid x^i) \\ \\ L(\Theta) &= \prod_{i=0}^{m-1} \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{e^{x^i\theta^j}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}} \\ \end{align}

上面的公式中 $1\{ \cdot \}$ 是示性函数,其取值规则为:

$$ 1\{ 值为真的表达式 \} = 1 $$

$$ 1\{ 值为假的表达式 \} = 0 $$

我们在似然函数中引入自然对数以方便后续的求导,则:

\begin{align} \\ L(\Theta) &= \log(\prod_{i=0}^{m-1} \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{e^{x^i\theta^j}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ L(\Theta) &= \sum_{i=0}^{m-1}\log(\sum_{j=0}^{k-1}1 \{y^i=j\} \frac{e^{x^i\theta^j}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ L(\Theta) &= \sum_{i=0}^{m-1}\sum_{j=0}^{k-1}1 \{y^i=j\} \log(\frac{e^{x^i\theta^j}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ L(\Theta) &= \sum_{i=0}^{m-1}\sum_{j=0}^{k-1}1 \{y^i=j\}(\log e^{x^i\theta^j} - \log \sum_{l=0}^{k-1}e^{x^i\theta^l}) \\ \\ L(\Theta) &= \sum_{i=0}^{m-1}\sum_{j=0}^{k-1}1 \{y^i=j\}(x^i\theta^j - \log \sum_{l=0}^{k-1}e^{x^i\theta^l}) \\ \end{align}

很明显似然函数最大值对应的 $\Theta$ 就是我们求解的目标,所以问题变为: $$ \max_\Theta L_\Theta $$

梯度上升法

使用梯度上升法可以帮助我们找到似然函数的最大值,参数 $\theta^t$ 的梯度为:

\begin{align} \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \frac{\partial}{\partial \theta^t} ( \sum_{i=0}^{m-1}\sum_{j=0}^{k-1}1 \{y^i=j\}(x^i\theta^j - \log \sum_{l=0}^{k-1}e^{x^i\theta^l}) ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}\frac{\partial}{\partial \theta^t}(\sum_{j=0}^{k-1}1 \{y^i=j\}(x^i\theta^j - \log \sum_{l=0}^{k-1}e^{x^i\theta^l}) ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}\frac{\partial}{\partial \theta^t}(\sum_{j=0}^{k-1}1 \{y^i=j\}x^i\theta^j - \sum_{j=0}^{k-1}1 \{y^i=j\} \log \sum_{l=0}^{k-1}e^{x^i\theta^l} ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T -\frac{\partial}{\partial \theta^t} ( \sum_{j=0}^{k-1}1 \{y^i=j\} \log \sum_{l=0}^{k-1}e^{x^i\theta^l}) ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T - \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{\partial}{\partial \theta^t} (\log \sum_{l=0}^{k-1}e^{x^i\theta^l}) ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T - \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{1}{\sum_{l=0}^{k-1}e^{x^i\theta^l}} \frac{\partial}{\partial \theta^t} \sum_{l=0}^{k-1}e^{x^i\theta^l} ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T - \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{1}{\sum_{l=0}^{k-1}e^{x^i\theta^l}} \frac{\partial}{\partial \theta^t} e^{x^i\theta^t} ) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T - \sum_{j=0}^{k-1}1 \{y^i=j\} \frac{(x^i)^T e^{x^i\theta^t}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(1 \{y^i=t\}(x^i)^T - \frac{(x^i)^T e^{x^i\theta^t}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(x^i)^T(1 \{y^i=t\} - \frac{e^{x^i\theta^t}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}}) \\ \\ \frac{\partial L(\Theta)}{\partial \theta^t} &= \sum_{i=0}^{m-1}(x^i)^T(1 \{y^i=t\} - p(y=t|x^i;\Theta)) \\ \end{align}

梯度上升法下的 $\theta^t$ 的更新公式为:

$$ \theta^t := \theta^t + \alpha \frac{\partial L(\Theta)}{\partial \theta^t} $$

Softmax回归模型参数化的特点

Softmax回归有一个不寻常的特点:它有一个“冗余”的参数集。假设我们从参数向量 $\theta^j$ 中减去向量 $\psi$ ,则概率函数变为:

\begin{align} \\ p(y=j|x;\Theta) &= \frac{e^{x^i(\theta^j-\psi)}}{\sum_{l=0}^{k-1}e^{x^i(\theta^l-\psi)}} \\ \\ p(y=j|x;\Theta) &= \frac{e^{x^i\theta^j}e^{-x^i\psi}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}e^{-x^i\psi}} \\ \\ p(y=j|x;\Theta) &= \frac{e^{x^i\theta^j}}{\sum_{l=0}^{k-1}e^{x^i\theta^l}} \\ \end{align}

我们看到从参数向量 $\theta^j$ 中减去向量 $\psi$ 并不影响概率函数的结果。也就是说我们可以得到多组参数值。所以可以设 $\psi = \theta^0$ ,这样的话 $\theta^0$ 就是一个零向量。也就是我们把 $\theta^0$设置为零向量后,我们只需要优化其他 $\theta$ 。

C++代码实现

我们定义如下的接口:

    /// @brief Softmax回归(多分类)
    class LSoftmaxRegression
    {
    public:
        /// @brief 构造函数
        LSoftmaxRegression();

        /// @brief 析构函数
        ~LSoftmaxRegression();

        /// @brief 训练模型
        /// 如果一次训练的样本数量为1, 则为随机梯度下降
        /// 如果一次训练的样本数量为M(样本总数), 则为梯度下降
        /// 如果一次训练的样本数量为m(1 < m < M), 则为批量梯度下降
        /// @param[in] xMatrix 样本矩阵, 每一行代表一个样本, 每一列代表样本的一个特征
        /// 样本矩阵数据最好归一化(即样本矩阵全部调整为0~1之间的值), 防止数据溢出
        /// @param[in] yMatrix 类标记矩阵, 每一行代表一个样本, 每一列代表样本的一个类别
        /// 如果样本属于该类别则标记为REGRESSION_ONE, 不属于则标记为REGRESSION_ZERO
        /// @param[in] alpha 学习速度, 该值必须大于0.0f
        /// @return 成功返回true, 失败返回false(参数错误的情况下会返回失败)
        bool TrainModel(IN const LRegressionMatrix& xMatrix, IN const LRegressionMatrix& yMatrix, IN float alpha);

        /// @brief 使用训练好的模型预测数据
        /// @param[in] xMatrix 需要预测的样本矩阵
        /// @param[out] yMatrix 存储预测的结果矩阵, 每一行代表一个样本, 每一列代表在该类别下的概率
        /// @return 成功返回true, 失败返回false(参数错误的情况下会返回失败)
        bool Predict(IN const LRegressionMatrix& xMatrix, OUT LRegressionMatrix& yMatrix) const;

        /// @brief 计算似然值, 似然值为0.0~1.0之间的数, 似然值值越大模型越好
        /// @param[in] xMatrix 样本矩阵, 每一行代表一个样本, 每一列代表样本的一个特征
        /// @param[in] yMatrix 类标记矩阵, 每一行代表一个样本, 每一列代表样本的一个类别
        /// 如果样本属于该类别则标记为REGRESSION_ONE, 不属于则标记为REGRESSION_ZERO
        /// @return 成功返回似然值, 失败返回-1.0f(参数错误的情况下会返回失败)
        float LikelihoodValue(IN const LRegressionMatrix& xMatrix, IN const LRegressionMatrix& yMatrix) const;

    private:
        CSoftmaxRegression* m_pSoftmaxRegression; ///< Softmax回归实现对象
    };

LMatrix是我们自定义的矩阵类,用于方便机器学习的一些矩阵计算,关于它的详细代码可以查看链接:猛戳我

我们为LSoftmaxRegression设计了三个方法TrainModel,Predict以及LikelihoodValue,用于训练模型,预测新数据以及计算似然值。

我们看一下TrainModel的实现:

    // 增加常数项后的样本矩阵
    LRegressionMatrix X;
    Regression::SamplexAddConstant(xMatrix, X);

    // 权重矩阵
    LRegressionMatrix& W = m_wMatrix;

    // 概率矩阵
    LRegressionMatrix P(X.RowLen, m_K, 0.0f);

    // 计算概率矩阵
    this->SampleProbK(X, W, P);

    LRegressionMatrix::SUB(yMatrix, P, P);

    // 权重向量(列向量)
    LRegressionMatrix dwVec(m_N + 1, 1, 0.0f);

    // 第一个权重值不优化, 解决Softmax回归参数有冗余的问题
    for (unsigned int k = 1; k < m_K; k++)
    {
        dwVec.Reset(m_N + 1, 1, 0.0f);
        for (unsigned int row = 0; row < X.RowLen; row++)
        {
            for (unsigned int col = 0; col < X.ColumnLen; col++)
            {
                dwVec[col][0] += X[row][col] * P[row][k];
            }
        }

        LRegressionMatrix::SCALARMUL(dwVec, alpha, dwVec);

        for (unsigned int row = 0; row < m_wMatrix.RowLen; row++)
        {
            m_wMatrix[row][k] += dwVec[row][0];
        }
    }

计算概率矩阵函数SampleProbK的代码如下:

    /// @brief 计算样本属于K个分类的各个概率
    /// @param[in] sampleMatrix 样本矩阵, m * n
    /// @param[in] weightMatrix 权重矩阵, n * k, 每一列为一个分类权重
    /// @param[out] probMatrix 概率矩阵, 存储每个样本属于不同分类的概率
    void SampleProbK(
        IN const LRegressionMatrix& sampleMatrix, 
        IN const LRegressionMatrix& weightMatrix, 
        OUT LRegressionMatrix& probMatrix) const
    {
        LRegressionMatrix::MUL(sampleMatrix, weightMatrix, probMatrix);

        for (unsigned int row = 0; row < probMatrix.RowLen; row++)
        {
            for (unsigned int col = 0; col < probMatrix.ColumnLen; col++)
            {
                probMatrix[row][col] = exp(probMatrix[row][col]);
            }
        }

        for (unsigned int row = 0; row < probMatrix.RowLen; row++)
        {
            float sum = 0.0f;
            for (unsigned int col = 0; col < probMatrix.ColumnLen; col++)
            {
                sum += probMatrix[row][col];
            }

            for (unsigned int col = 0; col < probMatrix.ColumnLen; col++)
            {
                probMatrix[row][col] = probMatrix[row][col]/sum;
            }
        }
    }

以上完整的代码可以在链接:猛戳我查看,我们的逻辑回归被定义在文件LRegression.h和LRegression.cpp中。

其他章节链接

机器学习基础1-线性回归及C++实现

机器学习基础2-二项逻辑回归及C++实现

机器学习基础3-Softmax回归及C++实现


赞助作者写出更好文章


您还未登录,登录GitHub账号发表精彩评论

 GitHub登录


最新评论

    还没有人评论...

 

 

刘杰

28岁, 现居苏州

微信:

BurnellLIU

邮箱:

burnell_liu@outlook.com

Github:

https://github.com/BurnellLiu

简介:

努力做一个快乐的程序员, good good study, day day up!

本站: 登录 注册   友情链接: Will Mao

苏ICP备16059872号. Copyright © 2017. http://www.coderjie.com. All rights reserved.

账号登录

注册 忘记密码