| 查看: 771 | 回复: 4 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
[求助]
coreset construction in complexity O(logn)?
|
|||
| 给定一个loss函数和数据集D，需要找到一个有代表性的集合(epsilon-coreset), 比如k-median, 除了原始情形的o(nlogn)复杂度的算法，以及one-pass(streaming)算法o(n)外，有没有更优的动态规划/贪心算法？(直觉上，算法搜索的过程含有某些信息，这些信息可以指导后面的搜索，甚至主动选取样本进行测试) |
回复此楼» 猜你喜欢
职称评审没过，求安慰
已经有55人回复
-
最近几年招的学生写论文不引自己组发的文章
已经有5人回复
-
26申博自荐
已经有3人回复
-
A期刊撤稿
已经有4人回复
5楼2014-10-07 22:19:46
feixiaolin
荣誉版主 (文坛精英)
-
专家经验: +518 - 应助: 942 (博后)
- 贵宾: 1.275
- 金币: 3430
- 散金: 58785
- 红花: 532
- 沙发: 11
- 帖子: 24215
- 在线: 2601.8小时
- 虫号: 2139575
- 注册: 2012-11-21
- 专业: 光学信息获取与处理
- 管辖: 数学
2楼2014-10-07 13:46:11
|
谢谢，我先看看 我是想做active learning/selective sampling,希望在被动的识别过程当中、通过主动行为改变算法的性能. 一个经典的例子（一维情形）有n层楼，需要检测nokia手机的抗摔性，问需要多少台机器能得出这个性能参数 将这个问题进行抽象,假定有n个d维数据(数据的位置不知道).设计一个算法，使用尽量少的样本，获得全体数据的性能 这个问题的难点是如何形式化“当下的历史状态(已经测试了某些细节），对未来行为的指导意义"，而不仅仅是类似于0-1那样的loss度量。这是一个离散事物，似乎有一定的难度。目前看到的处理思路是引入概率函数记录历史状态，同时通过大数律（偏离均值的范围与\sqrt(已有样本)*方差和想要的精度参数\delta-\epsilon有关)对未来进行指导 |
3楼2014-10-07 17:03:08
feixiaolin
荣誉版主 (文坛精英)
-
专家经验: +518 - 应助: 942 (博后)
- 贵宾: 1.275
- 金币: 3430
- 散金: 58785
- 红花: 532
- 沙发: 11
- 帖子: 24215
- 在线: 2601.8小时
- 虫号: 2139575
- 注册: 2012-11-21
- 专业: 光学信息获取与处理
- 管辖: 数学
4楼2014-10-07 22:13:49