| 查看: 833 | 回复: 4 | |||
[求助]
coreset construction in complexity O(logn)?
|
| 给定一个loss函数和数据集D，需要找到一个有代表性的集合(epsilon-coreset), 比如k-median, 除了原始情形的o(nlogn)复杂度的算法，以及one-pass(streaming)算法o(n)外，有没有更优的动态规划/贪心算法？(直觉上，算法搜索的过程含有某些信息，这些信息可以指导后面的搜索，甚至主动选取样本进行测试) |
回复此楼» 猜你喜欢
08工学调剂
已经有17人回复
-
340求调剂
已经有4人回复
-
311求调剂
已经有3人回复
-
0805 316求调剂
已经有5人回复
-
食品专硕 一志愿双一流 328
已经有4人回复
-
材料调剂
已经有6人回复
-
300分，材料，求调剂，英一数二
已经有5人回复
-
求调剂，一志愿:南京航空航天大学大学 ，080500材料科学与工程学硕，总分289分
已经有5人回复
-
085600材料与化工调剂
已经有13人回复
-
材料与化工考研调剂
已经有7人回复
feixiaolin
荣誉版主 (文坛精英)
-
专家经验: +518 - 应助: 942 (博后)
- 贵宾: 1.275
- 金币: 3880
- 散金: 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
- 金币: 3880
- 散金: 58785
- 红花: 532
- 沙发: 11
- 帖子: 24215
- 在线: 2601.8小时
- 虫号: 2139575
- 注册: 2012-11-21
- 专业: 光学信息获取与处理
- 管辖: 数学
4楼2014-10-07 22:13:49
5楼2014-10-07 22:19:46
