逻辑回归中函数最大值问题（相关搜索：最大值|回归模型|机器学习）

Question

问题描述
二分类问题是指，给定一个多维数据，将其分为两类中其中一类的问题。例如，给定一个人的身高，体重，学历数据，判断这个人是男是女。记第i个多维数据(假设为d维)为向量xi。xi有d个分量，记其二分类结果为yi=0或者1。（按上述例子，d=3, 而y=0,1可以分别代表男或者女）。
逻辑回归(Logistic Regression)是一种广义线性回归模型(Generalized Linear Model）。它可以对一类二分类问题进行建模，并基于该模型进行预测，是一种基础的机器学习模型。 
逻辑回归大致包括三个步骤：

1. 读取大量训练数据，这些数据包含其数据向量，以及分类结果。
2. 建模得到d维权重向量w。
3. 计算w与待分类数据向量xi的向量积，若其大于0则判断yi=1， 小于0则判断为yi=0。
   经过一系列概率统计分析之后，逻辑回归计算w的过程（第2步）最终可转化为求函数最大值问题，即求解：

其中xi为第i组数据， yi=0或者1为xi的二分类结果，w为权重向量。L(w)被称为最大似然估计(maximum likehood estimation)。为了防止过拟合，提高拟合精度，一般会使用2范数对该函数进行规范(regularization)。因而最终转化为求解下图所示函数最大值问题，其中lambda>0。本题中取lambda = 0.01即可。

该函数为凸函数，因此许多凸优化方法都可以数值解出该函数的全局最大值。
本次实验要求同学们自己实现一种数值算法解决该问题。
（不建议使用普通的梯度下降法，不建议根据迭代次数或者样本数手动控制步长，不建议舍弃部分训练集。否则可能会使编程体验很差。）
为了简化判题规则，固定一个权重向量w_origin来生成训练数据。OJ将同学们的程序最终拟合出来的w与w_origin进行比较，检测夹角大小来判定该题是否通过。只要该夹角的余弦大于0.98，则判定通过。
输入格式
第一行依次输入两个正整数，分别代表逻辑回归中每组数据xi的长度M，以及训练集大小N。
M<=2e2，N<=1e5，MN <= 2e6。
接下来有N行，每一行表示一组测试数据。
每行由M+1个浮点数组成，第一个数为1或者0，代表该组数据的分类。
之后的M个浮点数为该组数据每个维度的值。
每行的不同数据由一个空格分开。
输出格式
输出逻辑回归计算出来的权重向量w。
一行，共M个浮点数，由空格分开。
要求||w||2=1
输入样例
/

• 请注意：
• 由于4个数据点过少，无法得到确定性的回归结果，因此该样例仅作为输入输出格式的展示。
• /

2 4
0.0 -0.47019442830805513 0.25569211489219734
0.0 0.3051096614164499 0.012039799060534984
1.0 0.01075785699466636 -0.05008124001230352
1.0 0.051814866931391035 -0.24206065827582368
输出样例
/*

• 以下输出仅代表输入样例的一种合理的回归结果。
• 输出的有效数字位数不要求与该样例相同。
• /

-0.38064724459086946 -0.9247203226843124
提示
建议选用收敛速度较快并且计算复杂度较低的算法，各种数值算法的比较请参考文献[1]的结论部分。选用和实现算法时，可参考CMU凸优化课程对应算法slides的推导和结论[3]。如需要进行数学推导，如矩阵求导等，可以参考文献[2]。
其他：

1. 为了避免正负号混淆，建议先将本问题从求最大值转化为求最小值。
2. 可以使用双精度浮点数。
3. 注意迭代方向与步长的区分。如何确定步长可参考MSE的问题[4]，或其他资料。
4.  计算中exp函数可能超过浮点数最大允许值。

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void logisticRegression(vector<vector<double>> data, int M, int N, double lambda) {
    // Initialize weight vector w
    vector<double> w(M, 0.0);
    
    // Initialize learning rate
    double alpha = 0.01;
    
    // Iterate until convergence
    for (int iter = 0; iter < 1000; iter++) {
        vector<double> grad(M, 0.0);  // Gradient vector
        
        // Calculate gradient for each data point
        for (int i = 0; i < N; i++) {
            double y = data[i][0];
            double z = 0.0;  // z = w*x + b, where x is the data vector without the label
            for (int j = 1; j <= M; j++) {
                z += w[j-1] * data[i][j];
            }
            double h = 1.0 / (1.0 + exp(-z));  // sigmoid function
            
            // Update gradient
            for (int j = 1; j <= M; j++) {
                grad[j-1] += (h - y) * data[i][j];
            }
        }
        
        // Update weight vector
        for (int j = 0; j < M; j++) {
            w[j] = w[j] - alpha * (grad[j] + lambda * w[j]);
        }
    }
    
    // Normalize weight vector
    double norm_w = 0.0;
    for (int j = 0; j < M; j++) {
        norm_w += pow(w[j], 2.0);
    }
    norm_w = sqrt(norm_w);
    
    // Print normalized weight vector
    for (int j = 0; j < M; j++) {
        cout << w[j] / norm_w << " ";
    }
}

int main() {
    int M, N;
    cin >> M >> N;
    
    vector<vector<double>> data(N, vector<double>(M+1));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= M; j++) {
            cin >> data[i][j];
        }
    }
    
    double lambda = 0.01;
    
    logisticRegression(data, M, N, lambda);
    
    return 0;
}