V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nealot
V2EX  ›  程序员

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

  •  
  •   nealot · 2018-08-10 21:20:03 +08:00 · 1454 次点击
    这是一个创建于 2056 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    为了解决这个问题,首先需要定义一个解空间,比如一个简单的解空间可以是 (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]
         ~   ~       ~
    
    第 1 条附言  ·  2018-08-10 21:52:21 +08:00
    修正一下,这里的目标是寻找较优解,不是最优解
    8 条回复    2018-08-10 21:51:33 +08:00
    dbw9580
        1
    dbw9580  
       2018-08-10 21:33:04 +08:00 via Android
    所谓最佳权重的衡量标准是什么?
    建议看一下最优化理论,把问题写成标准优化问题的形式,有约束条件,有目标函数。不出意外有大把现成的优化算法可以用。这种数学问题千万不要自己造轮子,有可能都已经解决了几百年了……
    nealot
        2
    nealot  
    OP
       2018-08-10 21:35:46 +08:00
    @dbw9580 对于解空间中的一个解,有个代价函数 cost_function(v),这个函数可能是较耗时的,而且结果也较难预测,但是基本上是连续的,因此暴力搜索效率不高,但是梯度下降和遗传算法效果会较好
    dbw9580
        3
    dbw9580  
       2018-08-10 21:35:53 +08:00 via Android
    好吧几百年有点夸张了,几十年差不多:
    https://zh.m.wikipedia.org/zh-hans/%E6%9C%80%E4%BC%98%E5%8C%96
    dbw9580
        4
    dbw9580  
       2018-08-10 21:36:37 +08:00 via Android
    @nealot 代价函数的形式不知道吗?
    nealot
        5
    nealot  
    OP
       2018-08-10 21:40:03 +08:00
    @dbw9580 不知道,比如可能是 KNN 生成的一个交叉验证有效率
    dbw9580
        6
    dbw9580  
       2018-08-10 21:42:33 +08:00 via Android
    @nealot 这就比较难办了~难道是在调神经网络的权值吗?
    sw0rd3n
        7
    sw0rd3n  
       2018-08-10 21:48:53 +08:00 via iPhone   ❤️ 1
    “ No free lunch ”尤其说明非凸最优化问题。具体最优化方法还要结合目标函数特征,对于一般高纬度搜索,模拟退火、遗传算法和一些变种都能给出较优解。

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

    不建议楼主自己造轮子,没有数学证明很难保证结果可信度。
    nealot
        8
    nealot  
    OP
       2018-08-10 21:51:33 +08:00
    @sw0rd3n 遗传算法是挺好的,但是主要问题是上面提到的,约束条件下存在演化方向不平衡问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4416 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:10 · PVG 18:10 · LAX 03:10 · JFK 06:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.