如何计算重量以减小方差？

Question

给定多个向量：

x1 = [3 4 6]
x2 = [2 8 1]
x3 = [5 5 4]
x4 = [6 2 1]

我想要为每个项目找到权重w1、w2、w3，并获得每个向量的加权和：yi = w1*i1 + w2*i2 + w3*i3。例如：y1 = 3*w1 + 4*w2 + 6*w3，以使这些值（y1、y2、y3、y4）的方差最小。

注意：w1、w2、w3应该>0，并且w1 + w2 + w3 = 1

我不知道它应该是什么样的问题...以及如何在Python或Matlab中解决它？

- MarStarck

---

y-值的方差是多少？这些是固定值... - Willem Van Onsem

重量需要确定... w1、w2、w3 不是固定的。 - MarStarck

w1，...有限制吗？如果没有，请将所有的w设为零。 - pypypy

是的，添加了约束。 - MarStarck

看起来这是一个优化问题，因此可能需要使用动态规划方法来获得精确解。否则，您可以尝试梯度下降算法。 - pypypy

这个问题在MATLAB中解决起来应该很容易。让我花几分钟时间处理一下，我们就能找到答案了。 - Royi

Answer 1

您可以从构建损失函数开始，说明方差和对 w 的限制。平均值为 m = (1/4)*(y1 + y2 + y3 + y4)。方差为 (1/4)*((y1-m)^2 + (y2-m)^2 + (y3-m)^2 + (y4-m)^2)，约束条件为 a*(w1+w2+w3 - 1)，其中 a 是拉格朗日乘数。在我的看法中，该问题是具有凸约束的凸优化问题，因为损失函数相对于目标变量（w1、w2、w3）是二次的，而约束是线性的。您可以寻找符合所提供约束的投影梯度下降算法。请参阅此处 http://www.ifp.illinois.edu/~angelia/L5_exist_optimality.pdf。一般情况下，这种问题没有直截了当的解析解。

- Ufuk Can Bicici

---

谢谢！你真的理解我的问题并给了我一个提示。 - MarStarck

你可以使用投影次梯度法来解决它。请查看我的答案。 - Royi

Answer 2

w = [5, 6, 7]
x1 = [3, 4, 6]
x2 = [2, 8, 1]
x3 = [5, 5, 4]
y1, y2, y3 = 0, 0, 0
for index, i in enumerate(w):
    y1 = y1 + i * x1[index]
    y2 = y2 + i * x2[index]
    y3 = y3 + i * x3[index]
print(min(y1, y2, y3))

我认为我可能理解了你的问题目的。但是如果你想要找到最小值，我希望这可以帮助你。 我只是使值固定，当你看到这个时，你可以将其变成def，这是解决你的问题的一种方法。

- cwl

---

这是输出结果。 - cwl

Answer 3

我的完整解决方案可以在PDF中查看。

关键是将向量x_i作为矩阵X的列。
然后，将问题写成一个带有解决方案约束的凸问题，使其位于单位单纯形上。

我使用投影次梯度法来解决它。
我计算了目标函数的梯度，并创建了一个投影到单位单纯形的方法。

现在只需要迭代它们。
我使用CVX验证了我的解决方案。

% StackOverflow 44984132
% How to calculate weight to minimize variance?
% Remarks:
%   1.  sa
% TODO:
%   1.  ds
% Release Notes
% - 1.0.000     08/07/2017
%   *   First release.


%% General Parameters

run('InitScript.m');

figureIdx           = 0; %<! Continue from Question 1
figureCounterSpec   = '%04d';

generateFigures = OFF;


%% Simulation Parameters

dimOrder    = 3;
numSamples = 4;

mX = randi([1, 10], [dimOrder, numSamples]);
vE = ones([dimOrder, 1]);


%% Solve Using CVX

cvx_begin('quiet')
    cvx_precision('best');
    variable vW(numSamples)
    minimize( (0.5 * sum_square_abs( mX * vW - (1 / numSamples) * (vE.' * mX * vW) * vE )) )
    subject to
        sum(vW) == 1;
        vW >= 0;
cvx_end

disp([' ']);
disp(['CVX Solution -                       [ ', num2str(vW.'), ' ]']);


%% Solve Using Projected Sub Gradient

numIterations   = 20000;
stepSize        = 0.001;
simplexRadius   = 1; %<! Unit Simplex Radius
stopThr         = 1e-6;

hKernelFun  = @(vW) ((mX * vW) - ((1 / numSamples) * ((vE.' * mX * vW) * vE)));
hObjFun     = @(vW) 0.5 * sum(hKernelFun(vW) .^ 2);
hGradFun    = @(vW) (mX.' * hKernelFun(vW)) - ((1 / numSamples) * vE.' * (hKernelFun(vW)) * mX.' * vE);

vW = rand([numSamples, 1]);
vW = vW(:) / sum(vW);

for ii = 1:numIterations
    vGradW = hGradFun(vW);
    vW = vW - (stepSize * vGradW);

    % Projecting onto the Unit Simplex
    % sum(vW) == 1, vW >= 0.
    vW = ProjectSimplex(vW, simplexRadius, stopThr);
end

disp([' ']);
disp(['Projected Sub Gradient Solution -    [ ', num2str(vW.'), ' ]']);


%% Restore Defaults

% set(0, 'DefaultFigureWindowStyle', 'normal');
% set(0, 'DefaultAxesLooseInset', defaultLoosInset);

您可以在StackOverflow Q44984132中查看完整的代码（PDF也可用）。

- Royi

Answer 4

我对优化问题不是很了解，但我理解梯度下降的思想，所以我尝试减少最高分和最低分之间的权重，我的脚本如下：

# coding: utf-8
import numpy as np
#7.72
#7.6
#8.26

def get_max(alist):
    max_score = max(alist)
    idx = alist.index(max_score)
    return max_score, idx

def get_min(alist):
    max_score = min(alist)
    idx = alist.index(max_score)
    return max_score, idx

def get_weighted(alist,aweight):
    res = []
    for i in range(0, len(alist)):
        res.append(alist[i]*aweight[i])
    return res

def get_sub(list1, list2):
    res = []
    for i in range(0, len(list1)):
        res.append(list1[i] - list2[i])
    return res

def grad_dec(w,dist, st = 0.001):
    max_item, max_item_idx = get_max(dist)
    min_item, min_item_idx = get_min(dist)
    w[max_item_idx] = w[max_item_idx] - st
    w[min_item_idx] = w[min_item_idx] + st

def cal_score(w, x):
    score = []
    print 'weight', w ,x
    for i in range(0, len(x)):
        score_i = 0
        for j in range(0,5):
            score_i = w[j]*x[i][j] + score_i
        score.append(score_i)
    # check variance is small enough
    print 'score', score
    return score

    # cal_score(w,x)

if __name__ == "__main__":
    init_w = [0.2, 0.2, 0.2, 0.2, 0.2, 0.2]
    x = [[7.3, 10, 8.3, 8.8, 4.2], [6.8, 8.9, 8.4, 9.7, 4.2], [6.9, 9.9, 9.7, 8.1, 6.7]]
    score = cal_score(init_w,x)
    variance = np.var(score)
    round = 0
    for round in range(0, 100):
        if variance < 0.012:
            print 'ok'
            break
        max_score, idx = get_max(score)
        min_score, idx2 = get_min(score)
        weighted_1 = get_weighted(x[idx], init_w)
        weighted_2 = get_weighted(x[idx2], init_w)
        dist = get_sub(weighted_1, weighted_2)
        # print max_score, idx, min_score, idx2, dist
        grad_dec(init_w, dist)
        score = cal_score(init_w, x)
        variance = np.var(score)
        print 'variance', variance

    print score

在我的实践中，它确实可以减少方差。我很高兴，但我不知道我的解决方案在数学上是否稳固。

- MarStarck