优化问题解空间定义问题求助

[nealot]

在数据挖掘、机器学习任务中，我们可能需要通过梯度下降、模拟退火、遗传算法等方法寻找某个问题的最优解

为了解决这个问题，首先需要定义一个解空间，比如一个简单的解空间可以是 (0,0,0) 到 (9,9,9) 之间的 10x10x10 立方体

我现在遇到的问题是这样的: 有一个 n 维的特征，比如假设是 10 维的，选取其中的 3 个维度，赋予每个维度一个 0-9 之间的权重，所以权重向量可以是像这样的：

[0 0 a 0 b 0 0 0 c 0]

我们需要选取 3 个最佳的子特征，然后赋予其最佳的权重

如果直接把解空间定义成 (0,0,0,0,0,0,0,0,0,0) 到 (9,9,9,9,9,9,9,9,9,9) 显然是非常低效的，搜索产生的大部分解都不符合题设

一种思路是我们先把 a, b, c 三者的 index 取出来，然后再接上其权重，构成一个长度是 6 的向量:

[2 4 8 a b c]

然后在此基础上进行优化，但是这还是会带来一个问题：本质上我们需要的是一个组合，但是这个向量的前 3 位构成的是一个排列 (2 4 8 和 4 2 8 是重复的)

如果我们限定 v[0] < v[1] < v[2]，确实可以把解限定为不重复的排列，但是当 v[0] 很大时，比如 v = [7 8 9 a b c] 时，此时我们能调整的只有 v[0] 和 v[3] v[4] v[5]

此时我们必须通过一个过滤器，把无效解给过滤掉，但是这又会造成优化搜索过度偏向于权重 a b c (有 75% 的概率是在调整 a b c)，使得最优解的搜索变得低效

---

求助各位，对于这样的一个问题：在一个较长的特征中，选取其中 n 个子特征，然后赋予其最佳的权重的较为合理的实现方式是什么？

[0 0 a 0 b 0 0 0 c 0]
     ~   ~       ~

修正一下，这里的目标是寻找较优解，不是最优解

[dbw9580]

所谓最佳权重的衡量标准是什么？
建议看一下最优化理论，把问题写成标准优化问题的形式，有约束条件，有目标函数。不出意外有大把现成的优化算法可以用。这种数学问题千万不要自己造轮子，有可能都已经解决了几百年了……

[nealot]

@dbw9580 对于解空间中的一个解，有个代价函数 cost_function(v)，这个函数可能是较耗时的，而且结果也较难预测，但是基本上是连续的，因此暴力搜索效率不高，但是梯度下降和遗传算法效果会较好

[dbw9580]

好吧几百年有点夸张了，几十年差不多：
https://zh.m.wikipedia.org/zh-hans/%E6%9C%80%E4%BC%98%E5%8C%96

[dbw9580]

@nealot 代价函数的形式不知道吗？

[nealot]

@dbw9580 不知道，比如可能是 KNN 生成的一个交叉验证有效率

[dbw9580]

@nealot 这就比较难办了～难道是在调神经网络的权值吗？

[sw0rd3n]

“ No free lunch ”尤其说明非凸最优化问题。具体最优化方法还要结合目标函数特征，对于一般高纬度搜索，模拟退火、遗传算法和一些变种都能给出较优解。

梯度下降、BFGS 和牛顿算法这种基于梯度的算法适用范围更小，不过相对能更快收敛。

不建议楼主自己造轮子，没有数学证明很难保证结果可信度。

[nealot]

@sw0rd3n 遗传算法是挺好的，但是主要问题是上面提到的，约束条件下存在演化方向不平衡问题