考虑,从set S中根据偏好P选取一个元素E.
本质上就是用P对S进行排序的问题.
或者说order的问题.
考虑通常意义上的三个关系.
大于,等于,小于.
考虑没有symmetry/cyclic的情况.
即,大于小于的一个order chain不构成一个环.
那么大于小于可以合并为一个符号.
定义等于为=,非对称的大于小于为!=.
则给定任意a,b.
两者要么是=,要么是!=.
换一套符号表示的话.
f({a,b})= {=,!=} = {0,1}就算某种形式的binary classification.
考虑到前面的非对称限定,f({a,b})可能undefined的话.
回归三值,=,>和<,就是triple/muti classification.
那么从这个角度看.
排序的数组就是某种形式的index结构.
索引的是所有可能组合的分类结果情况.
也就是从element e->number index -> {=,>,<}的一个路径.
formalize的话.
就是给定一个set X,如果存在一个映射f.
满足f(x \in X) = N.
使得C(f(a),f(b)) = {=,!=} = {0,1}
如果是一个multi class的话,给定number of class=K
C(f(a),f(b)) = C_k(f(a),f(b)) = 1; C_{k-1}(f(a),f(b)) = 0.
也就是将为零的递归下去.
但是这个f不一定存在.
因为可能根本不是有序定义的.
但如果存在的话,如何去寻找这一个f呢?
如果ab所在的set S是有限的话.
那么实际上C是一个确定的集合.
此时的f只要任意一组满足C的数列就行了.
而这样的数列可以在排序过程中构建.
如果S是不确定的呢?
这样的S可以分开为一个确定的集合S_0和一个非确定的集合S_u.
确定的部分如上构建.
S_u的元素可以是S_0中相邻gap之间的任意一个数.
因为未知的S_u的元素必然是在S_0的L(S_0)+1的区间内.
于是未知元素的问题就是对于这几个区间归属的概率问题.
实际上,如果这个f确实存在,且是严格有序的.
那么新元素的问题实际上是一个插入问题.
所以f_u实际上是一个关于f的插入生成.
如果f不存在呢?
考虑S都是可比较的情况.
f不存在以图视角看待的话,S的路径存在回环.
因为如果不存在的回环的话,意味着元素都存在单向路径.
也就是存在严格的有序状态.
那么一个近似的解自然就是切断回环路径.
这样的话,主要就是图的partition问题了.
但这可能没有一个很好的方式去估算?
因为实际上这个图是fully connected的.
每一条边的移除都可能影响每一对节点的最短路径开销.
所以可能更实际的方式是做子图划分.
以期望得到的子图是符合预期的.
尽管同样地,似乎这种划分也不见得就有一个很好的代价衡量方式.
网友评论