考虑,从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的.
每一条边的移除都可能影响每一对节点的最短路径开销.
所以可能更实际的方式是做子图划分.
以期望得到的子图是符合预期的.
尽管同样地,似乎这种划分也不见得就有一个很好的代价衡量方式.
2019-06-03
关于Ceph的CRUSH算法
考虑crush map的bucket选择.
对于一个obejct o,choose的时候需要经过一个hash过程得到一个pseudo random的id x.
也就是对于任何一种bucket 类型,有
x = bucket_hash(o).
假定bucket的长度为n,x的放置位置为y的话.
bucket specific的choose policy为p.
有y=p(x)
对于uniform bucket来说,这个p为
y=p_uniform(x) = x % n
除了uniform的bucket之外,其他bucket type都是有weight权重的.
同样,记录位置w_i为位置i的用权重值,且有0<=i1的prod替换的sum.
也就是,这里的straw其实是一个权重放大倍数比list高得多的一个进阶版本.
而且跟list不同的是,它的argmax没有< w_j的条件限定.
因此它的寻址复杂度是O(n)的.
而list因为条件限定的情况,实际平均表现最差也只是跟straw一致.
在考虑现在ceph的默认policy,steaw2.
这里对hash做个额外的限定,0
这个主要是ceph的实现里有个lookup table的优化.
给定0
所以实际上starw2的hash是一个到[0,1]区间的一个mapping.
对应的log(k)取值区间大概是[-11,0].
所以这里简单重定义-11<=hash(x)<=0
则
y=p_straw2(x) = argmax(\{j; hash(x)/w_j \})
这里可以看出,只要bucket item的权重不变.节点增减的变化只由argmax的骨架部分决定.
这个跟list也有点类似,但是它是位置无关的.
不像list有对于左右有相对确定的基础cost估计.
但也因为位置无关,所以它存在一些极端情况.
对于节点减少的话,则所有argmax为这个节点的数据都会受影响.
这个是符合intuition的.
对于增加节点,argmax的max value可能都指向变动的那个节点.
这样的极端情况就是造成整体数据的挪动.
但是由于w_j的存在,这个也是可干涉/存在可控性的.
而对于节点数量不变,只是权重改变的情况.
跟节点增加类似.
所以,straw2的基本上算是忠实指向w_j的.
然后考虑hash.
由于hash会对x走一个log的重新分布.
所以实际上考虑的数据分布性质的话,只需要考虑log分布之后的就行了.
也就是在大概[-11,0]的区间内的数据分布问题.
把w_j作为一个tuning parameter/placement parameter考虑的话.
那么理论上,针对现有的实际数据分布是可以做到人工精确干涉的.
而且这么考虑的话,其实starw2的计算也并不需要搞那么复杂.
因为归根到底还是通过w_j来控制的.
对于一个obejct o,choose的时候需要经过一个hash过程得到一个pseudo random的id x.
也就是对于任何一种bucket 类型,有
x = bucket_hash(o).
假定bucket的长度为n,x的放置位置为y的话.
bucket specific的choose policy为p.
有y=p(x)
对于uniform bucket来说,这个p为
y=p_uniform(x) = x % n
除了uniform的bucket之外,其他bucket type都是有weight权重的.
同样,记录位置w_i为位置i的用权重值,且有0<=i
也就是,这里的straw其实是一个权重放大倍数比list高得多的一个进阶版本.
而且跟list不同的是,它的argmax没有< w_j的条件限定.
因此它的寻址复杂度是O(n)的.
而list因为条件限定的情况,实际平均表现最差也只是跟straw一致.
在考虑现在ceph的默认policy,steaw2.
这里对hash做个额外的限定,0
这个主要是ceph的实现里有个lookup table的优化.
给定0
所以实际上starw2的hash是一个到[0,1]区间的一个mapping.
对应的log(k)取值区间大概是[-11,0].
所以这里简单重定义-11<=hash(x)<=0
则
y=p_straw2(x) = argmax(\{j; hash(x)/w_j \})
这里可以看出,只要bucket item的权重不变.节点增减的变化只由argmax的骨架部分决定.
这个跟list也有点类似,但是它是位置无关的.
不像list有对于左右有相对确定的基础cost估计.
但也因为位置无关,所以它存在一些极端情况.
对于节点减少的话,则所有argmax为这个节点的数据都会受影响.
这个是符合intuition的.
对于增加节点,argmax的max value可能都指向变动的那个节点.
这样的极端情况就是造成整体数据的挪动.
但是由于w_j的存在,这个也是可干涉/存在可控性的.
而对于节点数量不变,只是权重改变的情况.
跟节点增加类似.
所以,straw2的基本上算是忠实指向w_j的.
然后考虑hash.
由于hash会对x走一个log的重新分布.
所以实际上考虑的数据分布性质的话,只需要考虑log分布之后的就行了.
也就是在大概[-11,0]的区间内的数据分布问题.
把w_j作为一个tuning parameter/placement parameter考虑的话.
那么理论上,针对现有的实际数据分布是可以做到人工精确干涉的.
而且这么考虑的话,其实starw2的计算也并不需要搞那么复杂.
因为归根到底还是通过w_j来控制的.
2019-04-06
由铁路售票想起
候车的时候想了个问题.
其实列车售票是一个segment的allocation问题.
给定一条线路{s_0,s_1,...,s_n}.
一个从A->B的请求实际上是某个{[s_i,s_j]; 0<=i
那么一个naive的approach就是做一个atomic的能rollback的transaction,做一个decrease.
这样的话,在q_i <<< concurrent_request,远小于并发请求数的时候.
在给定collision分布的情况下,某些q_i就不停地<0导致transaction rollback,从而造成一个failed allocation.
考虑一个稍微简单的定义.
给定一个sequence或者whatever,{s_i;s_i=0 or s_i=1}
也就是这个离散连续区间的值为0或者1.
或者说,这条线路各站余票只有0或者1两种情况.
对于一个allocation request,a_i_j,则要求的是.
sum_i_j s_i = j-i+1,即使i,j区间均为1.
而一组concurrent request则可以认为给定一组a,求一个satisfied的allocation subset.
这个有点类似有冲突的广告bid.
或者所谓的背包算法还是什么?
考虑optimized的目标是让是个subset尽可能地大.
或者说有尽可能多的request被满足.
那么这个最优解怎么求呢.
从最大或者最小的span开始allocate是不行的.
因为很容易构造一个反例,使人如果这个最优解存在,这种策略是不work的.
考虑对non-overlay的span一次allocation.
这是一个not necessary optimal的solution.
因为没有conflict.
考虑这个allocation set中的某个请求r,存在另一个range conflict的请求r_c.
当r_c的span是r的一个子集的时候,用r_c替换r是可以improve的.
因为此时r_c release原来r range的某些slot.
这使得这些slot有可能被更多的请求allocate到,从而增大了allocation set.
如果反过来的r_c是r的一个super set的话,那么同理,是不能improve的.
考虑只是partial overlay的情况.
令L_r为r的长度,L_r_c为r_c的长度.
那么在把r剔除之后的空出来的长度L至少会是L_r + L_r_c - 1.
不然的话,r和r_c能够同时fill整个range,不会有overlay.
于是对于r的improve就递归为这个L区间的optimal solution了.
则当最终converge的时候,也就是对于当前solution的所有r,都找不到任何improve的时候.
这个是最优解么?
还是说只是一个local minimal?
应该说只是一个local minimal.
因为本质上这是个step one的back search.
存在且容易构造如果回退两步能fill 3个request的情况.
而回退两步能产生更优解的原因应该是在于有了更多的continual的space.
所以可能first fill的时候,应该以保持尽可地避免fragment?
于是理想的做法应该是优先给予线路两侧的短途?
其实列车售票是一个segment的allocation问题.
给定一条线路{s_0,s_1,...,s_n}.
一个从A->B的请求实际上是某个{[s_i,s_j]; 0<=i
那么一个naive的approach就是做一个atomic的能rollback的transaction,做一个decrease.
这样的话,在q_i <<< concurrent_request,远小于并发请求数的时候.
在给定collision分布的情况下,某些q_i就不停地<0导致transaction rollback,从而造成一个failed allocation.
考虑一个稍微简单的定义.
给定一个sequence或者whatever,{s_i;s_i=0 or s_i=1}
也就是这个离散连续区间的值为0或者1.
或者说,这条线路各站余票只有0或者1两种情况.
对于一个allocation request,a_i_j,则要求的是.
sum_i_j s_i = j-i+1,即使i,j区间均为1.
而一组concurrent request则可以认为给定一组a,求一个satisfied的allocation subset.
这个有点类似有冲突的广告bid.
或者所谓的背包算法还是什么?
考虑optimized的目标是让是个subset尽可能地大.
或者说有尽可能多的request被满足.
那么这个最优解怎么求呢.
从最大或者最小的span开始allocate是不行的.
因为很容易构造一个反例,使人如果这个最优解存在,这种策略是不work的.
考虑对non-overlay的span一次allocation.
这是一个not necessary optimal的solution.
因为没有conflict.
考虑这个allocation set中的某个请求r,存在另一个range conflict的请求r_c.
当r_c的span是r的一个子集的时候,用r_c替换r是可以improve的.
因为此时r_c release原来r range的某些slot.
这使得这些slot有可能被更多的请求allocate到,从而增大了allocation set.
如果反过来的r_c是r的一个super set的话,那么同理,是不能improve的.
考虑只是partial overlay的情况.
令L_r为r的长度,L_r_c为r_c的长度.
那么在把r剔除之后的空出来的长度L至少会是L_r + L_r_c - 1.
不然的话,r和r_c能够同时fill整个range,不会有overlay.
于是对于r的improve就递归为这个L区间的optimal solution了.
则当最终converge的时候,也就是对于当前solution的所有r,都找不到任何improve的时候.
这个是最优解么?
还是说只是一个local minimal?
应该说只是一个local minimal.
因为本质上这是个step one的back search.
存在且容易构造如果回退两步能fill 3个request的情况.
而回退两步能产生更优解的原因应该是在于有了更多的continual的space.
所以可能first fill的时候,应该以保持尽可地避免fragment?
于是理想的做法应该是优先给予线路两侧的短途?
2019-03-16
关于锁的一点想法
考虑namenode或者某种rpc service队列.
假设有k个处理线程,每个请求处理时间是r的话.
则有t时间内的throughput T=k*r.
如果每个请求会收到一个global/share lock或者之类的互斥影响的话.
那么单个请求的开销r应该增加一个extra cost c.
即T=k*(r+c).
对于锁竞争之类的,cost c通常不会是一个常数.
考虑存在一个概率p能描述这个dynamic的话.
即c=p(c)
则每个请求的开销为r+p(c).
考虑有n个请求的话,那么在并行k的情况下.
每个线程处理m_i个请求,则该线程处理时长为\sum_{m_i} r+p(c).
->
cost of thread m_i = r*m_i + \sum p(c).
其中有n=\sum_k m_i即所有线程的处理请求总数加和为n.
当each m_i sufficient large的情况下,
cost of thread m_i ~ r*m_i + m_i*mean(p(c)).
即竞争带来的dynamic cost趋向于它的期望.
考虑线程处理是work stealing的策略的话.
那么并行带来的处理时长应该是每条线程差不多.
因为考虑只有两条线程的情况.
其中a跑了一个task,那么另外一条b要么跑comparable的task,要么lighter,或者heavier.
如果是lither的话,那么b将先完成,并抢先执行下一个.
这时等价于将a的当前task的cost减去b的task的开销,重置回假设初始.
而如若是heavier的话,交换a b即可.
对于k>=2的情况可以将划分为logical两条线程divide and conquer.
于是在这种情况下每条线程都是equality comparable cost的.
而任意一条在m_i sufficient large的情况下有
cost=r*m_i + m_i*mean(p(c))
->
per request cost=r+mean(p(c))
在p(c) dominate r的情况下.
比如在lock contention的情况下,process cost << wait lock. 实际请求开销小于锁竞争的情况下. 那么throuthput ~ mean(p(c))的. 那么考虑p的实际分布可能的形式. 以读写锁为例. 请求require read lock的概率为p,write lock的概率为1-p. 有k个线程竞争. 则,request read lock的情况. 当,all read lock的概率为p^k 因为shareable,所以cost=(p^k)*0 = 0 at least one write lock的概率为1-p^k. 如果获得锁,则有cost=0. 未获得锁的话,存在另外一个描述lcurrl,lock cost under read request lose. 即cost=(1-p^k) * (lcurrl) 请求为write lock的情况下,且获得的情况不论概率,其cost为零. 获取失败的情况下,存在yet another描述,lcuwrl,lock cost under write request lose. 那么mean cost=(p) * ((1-p^k) * (lcurrl)) + (1-p)*lcuwrl. ->lcurrl*p - lcurrl*p^(k+1) + lcuwrl - p*lcuwrl
->(lcurrl-lcuwrl)*p + lcuwrl - lcurrl*p^(k+1)
由于lcurrl和lcuwrl都是在给定p下的某个分布的mean值.
所以对于给定的p,有
(lcurrl-lcuwrl)*p + lcuwrl - lcurrl*p^(k+1)
->
mean cost = a*p^(k+1) + b
其中,a>0,1>=p>=0,k>0,b>0
当p->0的时候,或者k越来越大的话,mean cost -> b -> lcuwrl.
即lock cost under write request lose.
也即写锁竞争失败之后的expected cost.
如果锁是fair的.
那么设计上来说,每个线程得到的几率都是对等的.
于是随着k的增加,lcuwrl也会相应增加.
因为稀释.
而如果是non-fair的,则依赖于具体实现了.
假设有k个处理线程,每个请求处理时间是r的话.
则有t时间内的throughput T=k*r.
如果每个请求会收到一个global/share lock或者之类的互斥影响的话.
那么单个请求的开销r应该增加一个extra cost c.
即T=k*(r+c).
对于锁竞争之类的,cost c通常不会是一个常数.
考虑存在一个概率p能描述这个dynamic的话.
即c=p(c)
则每个请求的开销为r+p(c).
考虑有n个请求的话,那么在并行k的情况下.
每个线程处理m_i个请求,则该线程处理时长为\sum_{m_i} r+p(c).
->
cost of thread m_i = r*m_i + \sum p(c).
其中有n=\sum_k m_i即所有线程的处理请求总数加和为n.
当each m_i sufficient large的情况下,
cost of thread m_i ~ r*m_i + m_i*mean(p(c)).
即竞争带来的dynamic cost趋向于它的期望.
考虑线程处理是work stealing的策略的话.
那么并行带来的处理时长应该是每条线程差不多.
因为考虑只有两条线程的情况.
其中a跑了一个task,那么另外一条b要么跑comparable的task,要么lighter,或者heavier.
如果是lither的话,那么b将先完成,并抢先执行下一个.
这时等价于将a的当前task的cost减去b的task的开销,重置回假设初始.
而如若是heavier的话,交换a b即可.
对于k>=2的情况可以将划分为logical两条线程divide and conquer.
于是在这种情况下每条线程都是equality comparable cost的.
而任意一条在m_i sufficient large的情况下有
cost=r*m_i + m_i*mean(p(c))
->
per request cost=r+mean(p(c))
在p(c) dominate r的情况下.
比如在lock contention的情况下,process cost << wait lock. 实际请求开销小于锁竞争的情况下. 那么throuthput ~ mean(p(c))的. 那么考虑p的实际分布可能的形式. 以读写锁为例. 请求require read lock的概率为p,write lock的概率为1-p. 有k个线程竞争. 则,request read lock的情况. 当,all read lock的概率为p^k 因为shareable,所以cost=(p^k)*0 = 0 at least one write lock的概率为1-p^k. 如果获得锁,则有cost=0. 未获得锁的话,存在另外一个描述lcurrl,lock cost under read request lose. 即cost=(1-p^k) * (lcurrl) 请求为write lock的情况下,且获得的情况不论概率,其cost为零. 获取失败的情况下,存在yet another描述,lcuwrl,lock cost under write request lose. 那么mean cost=(p) * ((1-p^k) * (lcurrl)) + (1-p)*lcuwrl. ->lcurrl*p - lcurrl*p^(k+1) + lcuwrl - p*lcuwrl
->(lcurrl-lcuwrl)*p + lcuwrl - lcurrl*p^(k+1)
由于lcurrl和lcuwrl都是在给定p下的某个分布的mean值.
所以对于给定的p,有
(lcurrl-lcuwrl)*p + lcuwrl - lcurrl*p^(k+1)
->
mean cost = a*p^(k+1) + b
其中,a>0,1>=p>=0,k>0,b>0
当p->0的时候,或者k越来越大的话,mean cost -> b -> lcuwrl.
即lock cost under write request lose.
也即写锁竞争失败之后的expected cost.
如果锁是fair的.
那么设计上来说,每个线程得到的几率都是对等的.
于是随着k的增加,lcuwrl也会相应增加.
因为稀释.
而如果是non-fair的,则依赖于具体实现了.
2017-05-13
关于word2vec的一点想法
考虑word to vector的intuition.
给定两个词,如果存在某种意义的相似性的话.
那么,这两个词对应的vector representation就具有某种意义上的近似.
tensorflow里给的example实现对这个近似的定义是cosin值.
直觉上来说,就是给定两个向量在某些维度的方向指向上有着某种趋同性.
从embedding的角度来说,假设对一组词有着某种未知的词性/词义等的归类方式的话.
这种cosin趋向性实际上就是指向的这个embedding的某些维度了.
考虑如果用L2 distance来定义similarity.
那么它表示的则是这些词对应的点具有一些cluster性质.
而这些性质有什么含义,则是相对拟合过程所用的loss function的意义有关的.
因为从结果上来说,它对应的是embedding的各个维度之间都要求只有细微的差别.
如果出来的结果对应的vector不是一个稀疏表示的话,可能并不能收敛地很好.
或者说结果有意义.
所以,从这个侧面上来说,可能logistics regression比较合适.
变成类似多label的classification,从而达到类似一个binary encode的vector形式.
对应的1/0则表示相应embedding的dimension是否具有对应特征的一种标识.
这样的话,对于结果的一种可能直觉上的解释就是类似某种词性划分.
因为在这种情况下,对于不同的词可能会对于到同一个vector形式.
或者在某些维度具有重合性.
于是反观cosin形式.
cosin形式除了维度指向之外,还有另外一个信息就是长度.
直觉上来说,类似长度但维度指向不同的vector,实际上是处在一个hypersphere上面的.
也就是说,理论上,如果构造合适的loss function的话,是可以让最终的vector包含更多的信息的.
比如cosin similarity作为词性,长度作为词义或者对应的使用场景等.
实际上来说,这个vector对应的就是个2-D的离散feature组合了.
然后考虑loss的构造.
tensorflow的example实现使用nce loss,noise contrastive estimation.
大致就是在minimize原本的cosin的时候,加入一个negative sample项,做类似adversarial的目的.
因为如果没有这个negative的话,一个可能的最终解就是所有vector具有同样的值.
所以某种程度上来说,是一个既要overfit,又不要overfit的过程.
直觉上来说,就是把一些vector move together的时候,separate the other.
大致看了下tensorflow nce的negative sample应该用的是log uniform distribution.
按照这个概率选取一些作为penalty.
所以,理论上来说,这个adversarial项如果选取的不够好的话,结果可能也就不会很理想.
比如training set里都是些垂直领域的词,从人的角度来说都具有类型的词性词义等.
但可能adversarial的选取大概率的是这些相近的词类.
那么结果自然是一直被penalty,loss收敛不下去结果不理想不stationary.
而tensorflow的恰恰好是高词频的会更容易被作为adversarial.
所以适合的是topic/context比较多样化的场景.
这样才可能比较好地被"cluster".
还有一点就是tensforflow里word pair/skip gram model的生成方式.
predicative pair是通过一个skip window控制的.
也就是选定一个词,然后随机地从前后一定范围内选取一个词作为predicate.
这样的话,考虑长句松散语意和短句紧凑语意风格的training set的话,结果应该也是有很大不同的.
如果行文风格比较短小精悍的话,可能词组配对频率分布会比较平坦.
这样的话按照原有的loss来做的话,结果可能就不太好了.
考虑如果是强行生成所有组合.
那么这些组合实际上暗含的信息就是任意两个词之间co-occurrence的概率.
在最终的vector space里,cluster的vector之间就是彼此具有类似的context的属性.
因为两两之间在共同出现的频率差不多,也就一定程度上地说明在文本的使用场景具有某种长度的相似性.
当然,可能最终还是相当程度地会收到adversarial的选取方式的影响.
有可能避免negative这种不确定因素么?
如果对一个batch的同一个feeding sample多做几次gradient decent的话.
直觉上就是让当场的sample更靠近一下.
期望的是通过这种reinforce变相地离其他sample更远一些.
然后如果是确实高频出现的话,同样的reinforce会及时地回调.
形式上来说,就类似于做了一个基于频率的倍数放大而已.
并不一定有什么用.
考虑下entropy.
对于给定的training set来说p(x)是确定的.
对于定义
entropy = p(x) * log(1/p(x))
对于词x,以及对应的相似词y有
entropy = p(x,y) * log(1/tanh(similarly(x,y)))
通过minimize这个entropy的话,会是什么结果呢?
形式上来说,它可能等价于
entropy = W(p) * similarly(x,y)
一个跟固有概率/频率相关的相似度.
那么对于低频的pair来说,w->0,GD的过程可能改动不大.
但对于高频的pair,GD的过程就可能会做相对幅度的变动.
也就是直觉上的对于低频pair不做改动,而仅仅对高频部分做调整.
当然,实际怎么样就是另外一回事了.
给定两个词,如果存在某种意义的相似性的话.
那么,这两个词对应的vector representation就具有某种意义上的近似.
tensorflow里给的example实现对这个近似的定义是cosin值.
直觉上来说,就是给定两个向量在某些维度的方向指向上有着某种趋同性.
从embedding的角度来说,假设对一组词有着某种未知的词性/词义等的归类方式的话.
这种cosin趋向性实际上就是指向的这个embedding的某些维度了.
考虑如果用L2 distance来定义similarity.
那么它表示的则是这些词对应的点具有一些cluster性质.
而这些性质有什么含义,则是相对拟合过程所用的loss function的意义有关的.
因为从结果上来说,它对应的是embedding的各个维度之间都要求只有细微的差别.
如果出来的结果对应的vector不是一个稀疏表示的话,可能并不能收敛地很好.
或者说结果有意义.
所以,从这个侧面上来说,可能logistics regression比较合适.
变成类似多label的classification,从而达到类似一个binary encode的vector形式.
对应的1/0则表示相应embedding的dimension是否具有对应特征的一种标识.
这样的话,对于结果的一种可能直觉上的解释就是类似某种词性划分.
因为在这种情况下,对于不同的词可能会对于到同一个vector形式.
或者在某些维度具有重合性.
于是反观cosin形式.
cosin形式除了维度指向之外,还有另外一个信息就是长度.
直觉上来说,类似长度但维度指向不同的vector,实际上是处在一个hypersphere上面的.
也就是说,理论上,如果构造合适的loss function的话,是可以让最终的vector包含更多的信息的.
比如cosin similarity作为词性,长度作为词义或者对应的使用场景等.
实际上来说,这个vector对应的就是个2-D的离散feature组合了.
然后考虑loss的构造.
tensorflow的example实现使用nce loss,noise contrastive estimation.
大致就是在minimize原本的cosin的时候,加入一个negative sample项,做类似adversarial的目的.
因为如果没有这个negative的话,一个可能的最终解就是所有vector具有同样的值.
所以某种程度上来说,是一个既要overfit,又不要overfit的过程.
直觉上来说,就是把一些vector move together的时候,separate the other.
大致看了下tensorflow nce的negative sample应该用的是log uniform distribution.
按照这个概率选取一些作为penalty.
所以,理论上来说,这个adversarial项如果选取的不够好的话,结果可能也就不会很理想.
比如training set里都是些垂直领域的词,从人的角度来说都具有类型的词性词义等.
但可能adversarial的选取大概率的是这些相近的词类.
那么结果自然是一直被penalty,loss收敛不下去结果不理想不stationary.
而tensorflow的恰恰好是高词频的会更容易被作为adversarial.
所以适合的是topic/context比较多样化的场景.
这样才可能比较好地被"cluster".
还有一点就是tensforflow里word pair/skip gram model的生成方式.
predicative pair是通过一个skip window控制的.
也就是选定一个词,然后随机地从前后一定范围内选取一个词作为predicate.
这样的话,考虑长句松散语意和短句紧凑语意风格的training set的话,结果应该也是有很大不同的.
如果行文风格比较短小精悍的话,可能词组配对频率分布会比较平坦.
这样的话按照原有的loss来做的话,结果可能就不太好了.
考虑如果是强行生成所有组合.
那么这些组合实际上暗含的信息就是任意两个词之间co-occurrence的概率.
在最终的vector space里,cluster的vector之间就是彼此具有类似的context的属性.
因为两两之间在共同出现的频率差不多,也就一定程度上地说明在文本的使用场景具有某种长度的相似性.
当然,可能最终还是相当程度地会收到adversarial的选取方式的影响.
有可能避免negative这种不确定因素么?
如果对一个batch的同一个feeding sample多做几次gradient decent的话.
直觉上就是让当场的sample更靠近一下.
期望的是通过这种reinforce变相地离其他sample更远一些.
然后如果是确实高频出现的话,同样的reinforce会及时地回调.
形式上来说,就类似于做了一个基于频率的倍数放大而已.
并不一定有什么用.
考虑下entropy.
对于给定的training set来说p(x)是确定的.
对于定义
entropy = p(x) * log(1/p(x))
对于词x,以及对应的相似词y有
entropy = p(x,y) * log(1/tanh(similarly(x,y)))
通过minimize这个entropy的话,会是什么结果呢?
形式上来说,它可能等价于
entropy = W(p) * similarly(x,y)
一个跟固有概率/频率相关的相似度.
那么对于低频的pair来说,w->0,GD的过程可能改动不大.
但对于高频的pair,GD的过程就可能会做相对幅度的变动.
也就是直觉上的对于低频pair不做改动,而仅仅对高频部分做调整.
当然,实际怎么样就是另外一回事了.
2016-12-22
关于神经网络的一点想法
以前谈过的一个问题.
比如经典的数字识别问题.
给定feature和对应的结果,实际上就是一个拟合问题.
当时基于的考虑和思路就是,即使给定feature空间并不是全息的.
或者说并不是事实上的对现实的足够描述.
但理论上也可以找到一个从低维空间project回高维空间的matrix.
同样的,在project回的高维表示下,就存在一个对output space的projector.
于是在这个思路下就变成了一个纯粹的解矩阵乘的问题了.
所以当时觉得activation function意义不是很大.
但这里有几个问题.
一个是project回高维的向量未必是正确或者说有意义的.
另一个是高维project回低维的时候也同样.
而且从等式层面来说,两者可以合并.
也就是说从结果上来说,即便有解,解也可能是无限的.
这样的话,其实就没意义了.
而且理论上来说,也不一定有解.
虽然对于output space的单一维度来说.
理解为一组weighted local minimum的方式也没什么太大的问题.
比如针对是否是数字0的一组regression.
但这里还是有个比较致命的隐含假设.
也就是因果性.
因为这个思路暗含的是output space是input space的一个因果性变换.
或者说在某种程度上,input是可以涵盖/推导出output的.
但实际上,对于手写数字识别这个来说,并不是.
它并不存在一个确定性的从手写到数字的映射关系.
更多的只是一种习惯性.
从人的直觉上来说,认为一个手写字体是数字几的过程实际上是一个认为它"应该"是几的过程.
所以本质上来说,这是一个概率问题.
更明确地说,是给定一组feature vector,如何把它变换到一个概率空间的问题.
也就是如何把一个向量变成一个概率描述.
所以多项式变化或者说某种标量化之后,再做某种density性质的函数分布变换就变地很有意义了.
因此从这个角度来说,training的过程不过是在给定的activation function的特性/density性质曲线上,把vector scale过去.
于是,从某种程度上来说,neural network本质上就是某种probability machine.
不同结构的neural network不过是概率组合思路的不同罢了.
比如经典的数字识别问题.
给定feature和对应的结果,实际上就是一个拟合问题.
当时基于的考虑和思路就是,即使给定feature空间并不是全息的.
或者说并不是事实上的对现实的足够描述.
但理论上也可以找到一个从低维空间project回高维空间的matrix.
同样的,在project回的高维表示下,就存在一个对output space的projector.
于是在这个思路下就变成了一个纯粹的解矩阵乘的问题了.
所以当时觉得activation function意义不是很大.
但这里有几个问题.
一个是project回高维的向量未必是正确或者说有意义的.
另一个是高维project回低维的时候也同样.
而且从等式层面来说,两者可以合并.
也就是说从结果上来说,即便有解,解也可能是无限的.
这样的话,其实就没意义了.
而且理论上来说,也不一定有解.
虽然对于output space的单一维度来说.
理解为一组weighted local minimum的方式也没什么太大的问题.
比如针对是否是数字0的一组regression.
但这里还是有个比较致命的隐含假设.
也就是因果性.
因为这个思路暗含的是output space是input space的一个因果性变换.
或者说在某种程度上,input是可以涵盖/推导出output的.
但实际上,对于手写数字识别这个来说,并不是.
它并不存在一个确定性的从手写到数字的映射关系.
更多的只是一种习惯性.
从人的直觉上来说,认为一个手写字体是数字几的过程实际上是一个认为它"应该"是几的过程.
所以本质上来说,这是一个概率问题.
更明确地说,是给定一组feature vector,如何把它变换到一个概率空间的问题.
也就是如何把一个向量变成一个概率描述.
所以多项式变化或者说某种标量化之后,再做某种density性质的函数分布变换就变地很有意义了.
因此从这个角度来说,training的过程不过是在给定的activation function的特性/density性质曲线上,把vector scale过去.
于是,从某种程度上来说,neural network本质上就是某种probability machine.
不同结构的neural network不过是概率组合思路的不同罢了.
2016-09-10
关于Softmax的一些想法
考虑softmax = e^{x_k} / \sum e^{x_i} .
如果令y=e^x的话,则是一个较为一般的形式:
softmax = y / \sum y_i.
更一般的,假设y>0的话,则其实是一个类似percentage的东西.
比如y是一个投资份额/资金比例,那么\sum y就是每个个体的资本之和.
也就是总资本.
所以本质上来说,这种情况下更类似于一种dimension contribution的衡量方式.
那么,如果 考虑下数据分布呢?
一个极端的情况就是y=y_c,也就是所有y具有同一个值.
也就是说每个dimension的contribution区分度不会太大.
宽松一点来说,如果 y的variance的不大的话.
那么softmax的值也不会有太大的偏差.
再考虑一种情况.
即对于y来说,存在两个value group,y_a和y_b.
且y_a << y_b,或者宽松一点,y_a < y_b. 如果整体\sum y比较大,或者dimension比较多. 那么即使是y_b/ \sum y 的值可能也不会比 y_a/ \sum y的值来地更显著. 但从数据分布的人工直觉上来说,y_a和y_b的 contribution应该是存在有区分度的. 所以,单从这个角度来说,softmax对于高维度的feature vector来说,可能并不是一个很好的选择. 或者从某个层面上来说,更适合于一组互斥的feature set或者说classification/category. 如果去掉y>0的约束呢?
如果允许y<=0的话,那么直觉上就不太能将之于contribution做关联/联想了. 考虑坐下变化. softmax=y / \sum y_i ->
softmax = (y/n) / mean(y)
对于给定的数据来说,n和mean(y)可以认为是一个常量.
那么这样的话,softmax实际上就是一个对于feature y的scalar function.
反过来说,对于每个特定的 feature set的 单个feature来说.
这个 scalar是在某种程度上encdoe/ embeded了n和mean(n)这个样本相关的信息的.
所以,从这个角度考虑的话,softmax更像是一种 relative measure.
而且是针对每个独立的feautre set的一种某种程度上来说是标准的映射/转换过程.
但,这种映射在不同的feature set/ vector之间是不是有可比性呢?
因为维度n是固定相同的.
所以,实际上就两张情况.
mean(y)相同或相近的情况自然不用说了.
考虑mean(y)差异比较大的情况.
假设mean_a(y) << mean_b(y). 那么,对于给定的y其对应的softmax的值对应的relative position就会有比较大的偏差了. 从直觉上来说,虽然可能再这些值当中存在着某种程度的structure/level. 但由于数值上的区分度差异或者说classification的需要. 这些差异信息就可能被从计量的层面上被抹掉. 所以,从信息完整程度上来说,softmax也不太适合这种差异比较大的情况. 当然,这个可能可以通过具体地再套一层 normalize function. 或者再加一层network layer去 project到更高的维度再做softmax. 但考虑y>0的情况的话,可能也不是一个好的解决方法.
某种程度上来说,就像softmax名字所说的,着重点在max,注意点在soft.
也就是针对某个单一 dominated的 feature的产生作用.
所以从这个角度考虑的话,也不是说DNN和NN有多大的本质区别.
可能只是一些数据分布差异所带来的工程化处理/解决方案/方式/方法而已.
如果令y=e^x的话,则是一个较为一般的形式:
softmax = y / \sum y_i.
更一般的,假设y>0的话,则其实是一个类似percentage的东西.
比如y是一个投资份额/资金比例,那么\sum y就是每个个体的资本之和.
也就是总资本.
所以本质上来说,这种情况下更类似于一种dimension contribution的衡量方式.
那么,如果 考虑下数据分布呢?
一个极端的情况就是y=y_c,也就是所有y具有同一个值.
也就是说每个dimension的contribution区分度不会太大.
宽松一点来说,如果 y的variance的不大的话.
那么softmax的值也不会有太大的偏差.
再考虑一种情况.
即对于y来说,存在两个value group,y_a和y_b.
且y_a << y_b,或者宽松一点,y_a < y_b. 如果整体\sum y比较大,或者dimension比较多. 那么即使是y_b/ \sum y 的值可能也不会比 y_a/ \sum y的值来地更显著. 但从数据分布的人工直觉上来说,y_a和y_b的 contribution应该是存在有区分度的. 所以,单从这个角度来说,softmax对于高维度的feature vector来说,可能并不是一个很好的选择. 或者从某个层面上来说,更适合于一组互斥的feature set或者说classification/category. 如果去掉y>0的约束呢?
如果允许y<=0的话,那么直觉上就不太能将之于contribution做关联/联想了. 考虑坐下变化. softmax=y / \sum y_i ->
softmax = (y/n) / mean(y)
对于给定的数据来说,n和mean(y)可以认为是一个常量.
那么这样的话,softmax实际上就是一个对于feature y的scalar function.
反过来说,对于每个特定的 feature set的 单个feature来说.
这个 scalar是在某种程度上encdoe/ embeded了n和mean(n)这个样本相关的信息的.
所以,从这个角度考虑的话,softmax更像是一种 relative measure.
而且是针对每个独立的feautre set的一种某种程度上来说是标准的映射/转换过程.
但,这种映射在不同的feature set/ vector之间是不是有可比性呢?
因为维度n是固定相同的.
所以,实际上就两张情况.
mean(y)相同或相近的情况自然不用说了.
考虑mean(y)差异比较大的情况.
假设mean_a(y) << mean_b(y). 那么,对于给定的y其对应的softmax的值对应的relative position就会有比较大的偏差了. 从直觉上来说,虽然可能再这些值当中存在着某种程度的structure/level. 但由于数值上的区分度差异或者说classification的需要. 这些差异信息就可能被从计量的层面上被抹掉. 所以,从信息完整程度上来说,softmax也不太适合这种差异比较大的情况. 当然,这个可能可以通过具体地再套一层 normalize function. 或者再加一层network layer去 project到更高的维度再做softmax. 但考虑y>0的情况的话,可能也不是一个好的解决方法.
某种程度上来说,就像softmax名字所说的,着重点在max,注意点在soft.
也就是针对某个单一 dominated的 feature的产生作用.
所以从这个角度考虑的话,也不是说DNN和NN有多大的本质区别.
可能只是一些数据分布差异所带来的工程化处理/解决方案/方式/方法而已.
2016-05-02
网络结构与经济系统
五一到开平走了走.
自然不自然地对会对物价和经济水平有点认识.
大概算了下,按房价来说,可能就是3-4k左右的水平.
跟老家那边4-5k来说算很便宜了.
尤其老家那边在广东在经济也算倒数的.
物价方面也可以说是相当地便宜.
有点比较有意思的是.
在某饭店吃完饭结账,看到老板在用算盘算账.
在看习惯了各种贴着微信支付宝支付标签的人来说.
而且看某些田地,据说还是以插秧方式耕作的.
某种微妙的时空错层感.
不过主要想到的是这种跟老家对比之下的,经济水平跟价格水平的不对称关系.
也就是说,经济的发达程度,跟本地价格水平似乎并不存在一个明显的对应关系.
经济较为发达也并不意味着价格水平就会相对高些.
但想想,也不是特别难理解.
如果一个地方的经济贸易主要是自给自足型的话,那么来自外来的价格因素影响就有限.
在这种情况下,价格因素应该是趋于较为稳定合理情况的.
因为从现金/交易流向的角度来看的话,可以认为这是一个闭合的系统.
无论内里的交易状况如何复杂,从总体上来说都是一个零和的结构.
把这里面的所有经济个体考虑为一个network或者graph的节点.
从flow的角度来说,如果任意一个节点出现了异常的流量变化.
那么由于整个系统的是零和的,则必然会对该节点的进出节点产生流量变化影响.
递归地,就会对全网的流量造成一个整体的调整.
在这个调整过程中,就有可能使得某些节点消失,从而改变整个网络的拓扑结构.
这个改变会带来两个可能的影响结果.
一个是保持网络依然是零和的流量系统.
另一个则是使得这个零和特性消失.
如果是后者的话,那么也就意味着自给自足型的经济模式被打破.
而如果是前者的话,其实也可以反过来考虑两种结论.
一个经济闭合体如果保持着零和的特性,那么也就意味着要么是处在一个均衡的状态.
要么就是处于一个依然维持零和的网络变换中间态.
均衡状态的话,没什么好说的.
结构和模式以及流向都是固定参数.
持续的动态零和的话,则说明系统的流量可能是一个不稳定的变化过程.
甚至可能节点的建立和湮灭也是一个频繁的事情.
前者的一个宏观体现可能是价格水平变动比较频繁,并且可能在种类之间尤其做切换.
后者则可能是一些经济模式的不断/快速变化.
不过总得来说,如果是构架一个闭合的零和经济系统的话,那么在给定的网络总流量的前提下.
应该是有办法设计和调控/制造一种均衡状态的.
那么对于非自给自足的经济体来说呢?
在这这情况下,对于的模型就应该是经济体自身做个一个大的super node,然后同时有流入流出的flow.
同样地,在这种模型下,依然在一个算术意义上的零和系统.
但跟完全闭合的系统所不同的是,由于进出的流量是一个外部因素/变量.
所以,虽然能够暂时制造一种均衡状态,但始终来说是一个带random variable的描述式.
但换个角度,如果把这个super node看成一个更大范围内的经济体系统的单一节点的话,则是有可能存在使得这个更大的经济系统均衡的方式的.
那么,就存在使得每个节点进出流量保持恒定状态的规划方式.
也就是说,通过递归的方式,保证一个上层经济系统均衡的情况下,可以让下层经济系统退化为一个semi-zero system.
然后应用同样的方式,使得这个semi-zero system保持均衡状态.
所以,简单来说,这个可以认为是某种形式的流量规划.
当然,现实条件可能更复杂些.
毕竟各种产业存在着不同级别的细分.
即使有办法全部细分归类,然后构建成一个layer/stacked network,也可能并不是feasible的.
因为每个network stack/plane之间可能存在着各种交叉连接的graph形式.
当然,理论上是有可能做一些特化,做些pruning的优化处理的.
比如针对跨network plane的graph节点先做均衡/stationary的处理,让stack稳定之后再做network plane的均衡处理.
不过说到底,最多定性层面的possible而已.
自然不自然地对会对物价和经济水平有点认识.
大概算了下,按房价来说,可能就是3-4k左右的水平.
跟老家那边4-5k来说算很便宜了.
尤其老家那边在广东在经济也算倒数的.
物价方面也可以说是相当地便宜.
有点比较有意思的是.
在某饭店吃完饭结账,看到老板在用算盘算账.
在看习惯了各种贴着微信支付宝支付标签的人来说.
而且看某些田地,据说还是以插秧方式耕作的.
某种微妙的时空错层感.
不过主要想到的是这种跟老家对比之下的,经济水平跟价格水平的不对称关系.
也就是说,经济的发达程度,跟本地价格水平似乎并不存在一个明显的对应关系.
经济较为发达也并不意味着价格水平就会相对高些.
但想想,也不是特别难理解.
如果一个地方的经济贸易主要是自给自足型的话,那么来自外来的价格因素影响就有限.
在这种情况下,价格因素应该是趋于较为稳定合理情况的.
因为从现金/交易流向的角度来看的话,可以认为这是一个闭合的系统.
无论内里的交易状况如何复杂,从总体上来说都是一个零和的结构.
把这里面的所有经济个体考虑为一个network或者graph的节点.
从flow的角度来说,如果任意一个节点出现了异常的流量变化.
那么由于整个系统的是零和的,则必然会对该节点的进出节点产生流量变化影响.
递归地,就会对全网的流量造成一个整体的调整.
在这个调整过程中,就有可能使得某些节点消失,从而改变整个网络的拓扑结构.
这个改变会带来两个可能的影响结果.
一个是保持网络依然是零和的流量系统.
另一个则是使得这个零和特性消失.
如果是后者的话,那么也就意味着自给自足型的经济模式被打破.
而如果是前者的话,其实也可以反过来考虑两种结论.
一个经济闭合体如果保持着零和的特性,那么也就意味着要么是处在一个均衡的状态.
要么就是处于一个依然维持零和的网络变换中间态.
均衡状态的话,没什么好说的.
结构和模式以及流向都是固定参数.
持续的动态零和的话,则说明系统的流量可能是一个不稳定的变化过程.
甚至可能节点的建立和湮灭也是一个频繁的事情.
前者的一个宏观体现可能是价格水平变动比较频繁,并且可能在种类之间尤其做切换.
后者则可能是一些经济模式的不断/快速变化.
不过总得来说,如果是构架一个闭合的零和经济系统的话,那么在给定的网络总流量的前提下.
应该是有办法设计和调控/制造一种均衡状态的.
那么对于非自给自足的经济体来说呢?
在这这情况下,对于的模型就应该是经济体自身做个一个大的super node,然后同时有流入流出的flow.
同样地,在这种模型下,依然在一个算术意义上的零和系统.
但跟完全闭合的系统所不同的是,由于进出的流量是一个外部因素/变量.
所以,虽然能够暂时制造一种均衡状态,但始终来说是一个带random variable的描述式.
但换个角度,如果把这个super node看成一个更大范围内的经济体系统的单一节点的话,则是有可能存在使得这个更大的经济系统均衡的方式的.
那么,就存在使得每个节点进出流量保持恒定状态的规划方式.
也就是说,通过递归的方式,保证一个上层经济系统均衡的情况下,可以让下层经济系统退化为一个semi-zero system.
然后应用同样的方式,使得这个semi-zero system保持均衡状态.
所以,简单来说,这个可以认为是某种形式的流量规划.
当然,现实条件可能更复杂些.
毕竟各种产业存在着不同级别的细分.
即使有办法全部细分归类,然后构建成一个layer/stacked network,也可能并不是feasible的.
因为每个network stack/plane之间可能存在着各种交叉连接的graph形式.
当然,理论上是有可能做一些特化,做些pruning的优化处理的.
比如针对跨network plane的graph节点先做均衡/stationary的处理,让stack稳定之后再做network plane的均衡处理.
不过说到底,最多定性层面的possible而已.
2016-03-10
一点发散
大概是下午还是晚上时候的一个思路.
不知道还接不接地上.
某种程度上来说,neural network有点像数字电路里的基本逻辑.
尤其如果把一个trained network看作一个single unit的话.
DNN实际上就是一堆unit的组合.
从程序语言的角度来说,有点像low level machine code和high level programing language.
把一些基础的底层抽象作为某种形式的feature,去构建更高纬度的描述.
就像一个简单的例子.
一个NN识别长方体,一个NN识别个数,一个NN识别角度关系.
组合一下,差不多就能够描述一张桌子了.
剩下的其实就是这么调参和组合/加权的问题.
而想想,人意识到是一张桌子的过程和采用的feature可能也差不多.
只不过会更复杂一些.
比如context里有屋子,有椅子.
然后概率性地会把对"桌子"的识别的搜索限定到"桌子"的范围内.
就像AlphaGo的policy network.
本质上就是把一些常规棋谱的模式encode进来,提供给value network做一些"常规"的"符合人类直觉"的选择.
只不过这里比较tricky的地方是,policy network encode的模式是一个snapshot.
下子之间不具有关联关系.
所以某种程度上来说,容易出现实际超长步数的策略建议.
回到NN的问题上.
既然一个DNN是一种NN的叠加和组合产生的高阶描述.
那么理论上来说,只要堆叠的NN足够多.
在不考虑运算力和存储等现实约束的前提下,进化出"智能"/"意识"也不是不可能的.
毕竟,人类的所谓学习/创造能力也不过是一些在现有learned feature上组合出来的.
尤其是如果数学推演能描述人类绝大多数甚至全部构成和行为的话.
那么在这点上,两者是完全没有区别的.
即使是matrix里提到的"感情"这种不等式存在.
在形式上来说,也是可以被精确描述和还原的.
所以,在这个层面上来说,讨论AI和人类的区别是没有意义的.
而实际上,这种堆叠不可能是无限细化和实时的.
某种程度上来说,人类对于NN based的AI来说,就是某种形式的laplace's demon.
至少从目前的技术角度来说,类DNN架构里,NN的数量相对于人类的神经系统来说还是非常有限的.
但是,如果换个角度来说,这里就可能存在某种形式的商业逻辑.
也就是一开始所说的数字电路/编程语言的思路.
考虑,如果把所有NN开放到互联网上,以某种公共协议的方式进行数据交换/交互的话.
那么就有可能把这种AI的智能程度提高一个层次.
就像桌子的例子.
通过全网的某种类RPC形式的交互调用可以得到某种encode比较丰富的feature vector.
它的dimension数量可能是想关于NN的数量的.
这么考虑的话,一个集中全网范围的存储和算力的类DNN架构,其"智能"程度也就可能超出现在的想象.
而对于"自主思考"这类问题,本质上来说不过是一些细化的feature组合之后,产生发现一个新的比较有区分度的sub space的过程而已.
比如对于一个自然数的加法group.
某个NN或者DNN能够infer/encode出5+5+5,3+3+3+3这类相同数字的连续加的结果的一些模式.
然后另外某些能够infer/encode出这里有连续数的+操作.
那么两者结合一下就有可能出来关于*的一个NN/DNN.
apply 回去的话,就是一个比较完整的关于*的创造性/学习/新的描述了.
实际上,AlphaGo的reinforced policy network就类似于对supervise policy network的一些模式encode.
对应与+操作的一些high level abstraction.
在基于此上的value network就是类似于infer出来的*操作了.
所以,从这个角度上来说AlphaGo确实是一种比较完整的对于人类思路的复刻.
某种程度上来说,大概所有DNN都是这种模仿方式.
只不过在实现上,由于各自选择的对于low level information的abstract角度不太一样罢了.
而在某些问题领域上,可供选择和考虑的抽象并不是特别多样化,所以是可能存在一定程度的重复工作的.
于是,以这个角度考虑一些做ML方案/平台的各种startup的话,方向倒也没错就是了.
从狭义上来说,都是各自提供了一些自己的pretrain的model给人做二次开发的.
如果能够推广一下,以某种公共协议或者调用方式对各种异构的NN做一个数据交换的话,大概人类文明能有一个比较大程度的飞跃.
尤其如果能推动到数学推演上面的话,以AlphaGo这种搜索方式的话,大概会有相当一部分问题能得到解/证明/证伪.
从这点上来说,AlphaGo的意义还是相当时代性的.
至少也是给通俗世界提供了一种新的思路.
就像前几年把DNN带到工业界的意义一样.
尽管,可能这些东西在学术界躺了几年甚至几十年了.
但终归,总会有像Google这种有能力有威望的人,把它带到人们面前.
创造或者提供一种全新的角度审视一些问题/东西.
不知道还接不接地上.
某种程度上来说,neural network有点像数字电路里的基本逻辑.
尤其如果把一个trained network看作一个single unit的话.
DNN实际上就是一堆unit的组合.
从程序语言的角度来说,有点像low level machine code和high level programing language.
把一些基础的底层抽象作为某种形式的feature,去构建更高纬度的描述.
就像一个简单的例子.
一个NN识别长方体,一个NN识别个数,一个NN识别角度关系.
组合一下,差不多就能够描述一张桌子了.
剩下的其实就是这么调参和组合/加权的问题.
而想想,人意识到是一张桌子的过程和采用的feature可能也差不多.
只不过会更复杂一些.
比如context里有屋子,有椅子.
然后概率性地会把对"桌子"的识别的搜索限定到"桌子"的范围内.
就像AlphaGo的policy network.
本质上就是把一些常规棋谱的模式encode进来,提供给value network做一些"常规"的"符合人类直觉"的选择.
只不过这里比较tricky的地方是,policy network encode的模式是一个snapshot.
下子之间不具有关联关系.
所以某种程度上来说,容易出现实际超长步数的策略建议.
回到NN的问题上.
既然一个DNN是一种NN的叠加和组合产生的高阶描述.
那么理论上来说,只要堆叠的NN足够多.
在不考虑运算力和存储等现实约束的前提下,进化出"智能"/"意识"也不是不可能的.
毕竟,人类的所谓学习/创造能力也不过是一些在现有learned feature上组合出来的.
尤其是如果数学推演能描述人类绝大多数甚至全部构成和行为的话.
那么在这点上,两者是完全没有区别的.
即使是matrix里提到的"感情"这种不等式存在.
在形式上来说,也是可以被精确描述和还原的.
所以,在这个层面上来说,讨论AI和人类的区别是没有意义的.
而实际上,这种堆叠不可能是无限细化和实时的.
某种程度上来说,人类对于NN based的AI来说,就是某种形式的laplace's demon.
至少从目前的技术角度来说,类DNN架构里,NN的数量相对于人类的神经系统来说还是非常有限的.
但是,如果换个角度来说,这里就可能存在某种形式的商业逻辑.
也就是一开始所说的数字电路/编程语言的思路.
考虑,如果把所有NN开放到互联网上,以某种公共协议的方式进行数据交换/交互的话.
那么就有可能把这种AI的智能程度提高一个层次.
就像桌子的例子.
通过全网的某种类RPC形式的交互调用可以得到某种encode比较丰富的feature vector.
它的dimension数量可能是想关于NN的数量的.
这么考虑的话,一个集中全网范围的存储和算力的类DNN架构,其"智能"程度也就可能超出现在的想象.
而对于"自主思考"这类问题,本质上来说不过是一些细化的feature组合之后,产生发现一个新的比较有区分度的sub space的过程而已.
比如对于一个自然数的加法group.
某个NN或者DNN能够infer/encode出5+5+5,3+3+3+3这类相同数字的连续加的结果的一些模式.
然后另外某些能够infer/encode出这里有连续数的+操作.
那么两者结合一下就有可能出来关于*的一个NN/DNN.
apply 回去的话,就是一个比较完整的关于*的创造性/学习/新的描述了.
实际上,AlphaGo的reinforced policy network就类似于对supervise policy network的一些模式encode.
对应与+操作的一些high level abstraction.
在基于此上的value network就是类似于infer出来的*操作了.
所以,从这个角度上来说AlphaGo确实是一种比较完整的对于人类思路的复刻.
某种程度上来说,大概所有DNN都是这种模仿方式.
只不过在实现上,由于各自选择的对于low level information的abstract角度不太一样罢了.
而在某些问题领域上,可供选择和考虑的抽象并不是特别多样化,所以是可能存在一定程度的重复工作的.
于是,以这个角度考虑一些做ML方案/平台的各种startup的话,方向倒也没错就是了.
从狭义上来说,都是各自提供了一些自己的pretrain的model给人做二次开发的.
如果能够推广一下,以某种公共协议或者调用方式对各种异构的NN做一个数据交换的话,大概人类文明能有一个比较大程度的飞跃.
尤其如果能推动到数学推演上面的话,以AlphaGo这种搜索方式的话,大概会有相当一部分问题能得到解/证明/证伪.
从这点上来说,AlphaGo的意义还是相当时代性的.
至少也是给通俗世界提供了一种新的思路.
就像前几年把DNN带到工业界的意义一样.
尽管,可能这些东西在学术界躺了几年甚至几十年了.
但终归,总会有像Google这种有能力有威望的人,把它带到人们面前.
创造或者提供一种全新的角度审视一些问题/东西.
2016-02-07
关于自动泊车及其他
考虑一个自动泊车的算法问题.
给定一个平面,考虑位置和车头朝向的话.
实际上就是一组(x,y,\theta)的三元向量p的描述.
对于传动/转向/制动系统来说,应该是存在一个函数变换f.
给定一组机械参数,对应的是位置和朝向的\delta值.
那么问题实际上就简化为,给定要给起始位置的描述向量A,和一个最终位置的向量B().
根据函数f的\delta变换约束,求一个AB的平滑曲线的问题.
直接的gradient descent求解的话存在几个问题.
一个是实际情况下存在一些障碍物的问题,也就是限制的\delta变换函数f的选择范围.
另一个是并不能保证最终求得的解是满足需求意愿的.
对于第一点来说,原则上只是在每一步改变cost function的问题.
但随之而来会带来跟第二个问题相同的境况.
某种程度上来说,这种greedy的搜索算法面临的问题始终是不一定存在这样的解.
而且,考虑到搜索的深度和广度问题,即使存在这样的解,在时间效率和复杂度上也可能不是很实用.
那么,能不能在不改变基本算法的前提下,尽可能地做写prune之类的降低复杂度和搜索空间呢?
考虑对于一个给定的点p,在一个f的变换下,存在一个关于x,y的偏移范围的L2-distance约束.
也即是说,每一次f变化所能造成的"最大"\"最小"差量是已知的.
于是,粗略的考虑的话,变换次数是跟AB两点间的L2-distance有关的.
换句话说,减少目标的L2-distance的话,就可能减少搜索空间的代价.
为什么是可能呢?
考虑点A的描述为(x,y,\theta),B的描述为(x,y,-\theta).
这两个向量在x,y空间的L2-distance是零.
但显然这时候的解并不是预期中的不用做什么.
那么,这个有什么实际意义呢?
毕竟,对于给定的AB两点,并不存在改变这两点xy纬度下的L2-distance的方式.
换个角度.
考虑存在一条经过B点的由f驱动的曲线S.
也就是存在一条预设定的泊车路线.
那么就存在一个可能的裁剪方式,把问题变换为求A点到这条预定曲线S上某点U的问题.
而U的求解可以简单的是上面提到的xy维度的L2-distance判定.
进一步地,给定一条曲线S的话,求解U的过程可以是直接的使用(x,y,\theta)坐标系的点到曲线最短距离来计算.
这样的话,就存在一定的可能性,使得算法的整体搜索空间有一定幅度的缩减.
但问题的根本并没有什么太大的改观.
依然是被一个约束限制着.
那就是这个搜索路径不一定存在所期望的路径解.
另一个问题是交互方面的.
不考虑硬件约束的话,是存在能得到周围障碍图的能力的.
基于此,以及车辆本身的一些参数,是存在自动寻找落点的方式的.
即使没有地面导引指示.
本质上可以理解为是一个空间填充问题.
但在一些极端情况下可能存在一些比较不太合理的方案.
一种情况就是,如果周围都是空旷地方的情况.
在这种情况下,filling slot的最有策略就是选择不动.
但实际预期的情况可能并不是如此.
考虑人工介入的情况.
给定一块触摸屏幕,通过一些简单的拖拽方式是可以以所见即所得的方式定义终点B的参数的.
因为基本上所有的物理/成象参数都存在一个固定已知的换算/变换关系.
所以这个方案在是现实并没有什么太大的困难.
实际上,扩展考虑下.
如果车辆设备全部能够电子通讯化的话,远程/遥控驾驶并不是一件非常复杂的事情.
之所以不能或者说没有实现的关键点可能在于通讯延时的问题.
考虑一个40km/h世俗,远程通讯延时是200ms的话.
那么"实时"传回的图像至少存在2米的距离参数.
再加上人体反应和round triptime的话,在人的角度看待做出的反应可能只是针对10米之前的情况做出的判断了.
这个对于交通安全来说,并不是一个能接受的事情.
但换个角度来说,如果是一个直连车辆的设备,那么延时就可能可以降低两个一两个数量级.
达到近似real time的情况.
也就是说,理论上,接个手柄或者键盘等输入设备来驾驶也不是完全不可能的.
给定一个平面,考虑位置和车头朝向的话.
实际上就是一组(x,y,\theta)的三元向量p的描述.
对于传动/转向/制动系统来说,应该是存在一个函数变换f.
给定一组机械参数,对应的是位置和朝向的\delta值.
那么问题实际上就简化为,给定要给起始位置的描述向量A,和一个最终位置的向量B().
根据函数f的\delta变换约束,求一个AB的平滑曲线的问题.
直接的gradient descent求解的话存在几个问题.
一个是实际情况下存在一些障碍物的问题,也就是限制的\delta变换函数f的选择范围.
另一个是并不能保证最终求得的解是满足需求意愿的.
对于第一点来说,原则上只是在每一步改变cost function的问题.
但随之而来会带来跟第二个问题相同的境况.
某种程度上来说,这种greedy的搜索算法面临的问题始终是不一定存在这样的解.
而且,考虑到搜索的深度和广度问题,即使存在这样的解,在时间效率和复杂度上也可能不是很实用.
那么,能不能在不改变基本算法的前提下,尽可能地做写prune之类的降低复杂度和搜索空间呢?
考虑对于一个给定的点p,在一个f的变换下,存在一个关于x,y的偏移范围的L2-distance约束.
也即是说,每一次f变化所能造成的"最大"\"最小"差量是已知的.
于是,粗略的考虑的话,变换次数是跟AB两点间的L2-distance有关的.
换句话说,减少目标的L2-distance的话,就可能减少搜索空间的代价.
为什么是可能呢?
考虑点A的描述为(x,y,\theta),B的描述为(x,y,-\theta).
这两个向量在x,y空间的L2-distance是零.
但显然这时候的解并不是预期中的不用做什么.
那么,这个有什么实际意义呢?
毕竟,对于给定的AB两点,并不存在改变这两点xy纬度下的L2-distance的方式.
换个角度.
考虑存在一条经过B点的由f驱动的曲线S.
也就是存在一条预设定的泊车路线.
那么就存在一个可能的裁剪方式,把问题变换为求A点到这条预定曲线S上某点U的问题.
而U的求解可以简单的是上面提到的xy维度的L2-distance判定.
进一步地,给定一条曲线S的话,求解U的过程可以是直接的使用(x,y,\theta)坐标系的点到曲线最短距离来计算.
这样的话,就存在一定的可能性,使得算法的整体搜索空间有一定幅度的缩减.
但问题的根本并没有什么太大的改观.
依然是被一个约束限制着.
那就是这个搜索路径不一定存在所期望的路径解.
另一个问题是交互方面的.
不考虑硬件约束的话,是存在能得到周围障碍图的能力的.
基于此,以及车辆本身的一些参数,是存在自动寻找落点的方式的.
即使没有地面导引指示.
本质上可以理解为是一个空间填充问题.
但在一些极端情况下可能存在一些比较不太合理的方案.
一种情况就是,如果周围都是空旷地方的情况.
在这种情况下,filling slot的最有策略就是选择不动.
但实际预期的情况可能并不是如此.
考虑人工介入的情况.
给定一块触摸屏幕,通过一些简单的拖拽方式是可以以所见即所得的方式定义终点B的参数的.
因为基本上所有的物理/成象参数都存在一个固定已知的换算/变换关系.
所以这个方案在是现实并没有什么太大的困难.
实际上,扩展考虑下.
如果车辆设备全部能够电子通讯化的话,远程/遥控驾驶并不是一件非常复杂的事情.
之所以不能或者说没有实现的关键点可能在于通讯延时的问题.
考虑一个40km/h世俗,远程通讯延时是200ms的话.
那么"实时"传回的图像至少存在2米的距离参数.
再加上人体反应和round triptime的话,在人的角度看待做出的反应可能只是针对10米之前的情况做出的判断了.
这个对于交通安全来说,并不是一个能接受的事情.
但换个角度来说,如果是一个直连车辆的设备,那么延时就可能可以降低两个一两个数量级.
达到近似real time的情况.
也就是说,理论上,接个手柄或者键盘等输入设备来驾驶也不是完全不可能的.
2015-12-08
由拉格朗日乘数想到
考虑lagrange multiplier的构造.
\mathcal{L}(X) = f(X) + \lambda*g(X)
这里一个比较有趣的地方是constraint function g作为一个余项引入.
根据g的定义,g(X) = 0.
也就是说实际上等价于
\mathcal{L}(X) = f(X)
考虑\mathcal{L}(X)的stationary points.
即满足\nabla \mathcal{L}(X) = 0的集合S.
如果s \in S且g(s) = 0的话,那么就是一个可能的solution.
这里的思路其实是通过构造一个零项保证function的mapping空间/关系不变.
但同时把问题简化为简单的stationary的解.
换个角度考虑的话,其实就是对一个现有space的某种形式的cut/prune/classify.
在保证某种特性不变的前提下,以g做出一定形式的划分.
考虑把f(X)看作是一种feature -> object的函数.
比如X是一组feature,object是一个用户标识.
也就是说假设存在一种描述,使得这个描述对某个用户唯一.
即通过feature vector可以unique地locate到某个用户.
然后考虑有一个对用户的label函数.
使得每个用户对应一个label.
重新如lagrange multiplier的形式的等式.
\mathcal{L}(X) = f(X) + \lambda_a*g_a(X) + \lambda_b*g_b(X) + ...
当X被归类为a的时候,其余的\lambda*g(X) = 0.
即此时的\mathcal{L}(X) - f(X) = \lambda_a*g_a(X) != 0.
如果令lambda都等于1的话,则形式为:
\mathcal{L}(X) = f(X) + g_a(X) + g_b(X) + ...
->
\mathcal{L}(X) = f(X) + col_sum(G*X).
G为一个dim(label)行feature列的matrix,col_sum为对列做的算数和.
那么就有可能解出一个matrix G,使得col_sum(G*X) = 0
对于一个给定的x,apply之后有col_sum(x;G) == 0 意味着什么呢?
意味如果x是在X中,且其对于label a的话,
\lambda_a*g_a(X) + \lambda_b*g_b(X) + ... == 0
->
\lambda_a*g_a(X) == 0即与label a的前提矛盾.
所以如果col_sum(x;G) == 0 的话,则表明x必定不在X中.
那么如果col_sum(x;G) != 0的话呢?
明显也不能说明x就在X中.
因为可能存在g_b(X) != 0等的情况.
如果G*X得到的vector形式V是[1,0,0,0,...]的某个维度值为1的unit vector呢?
也不能.
因为如果把G看作是X向feature space的project的话.
对于某个vector来说,project成unit vector也不足以说明就是在原来的X space.
所以,某种程度上来说,这个只是一个dim(X) -> dim(label)的某种形式的类bloom filter.
即G*X != unit vector的话,则必然不在原来的X中.
\mathcal{L}(X) = f(X) + \lambda*g(X)
这里一个比较有趣的地方是constraint function g作为一个余项引入.
根据g的定义,g(X) = 0.
也就是说实际上等价于
\mathcal{L}(X) = f(X)
考虑\mathcal{L}(X)的stationary points.
即满足\nabla \mathcal{L}(X) = 0的集合S.
如果s \in S且g(s) = 0的话,那么就是一个可能的solution.
这里的思路其实是通过构造一个零项保证function的mapping空间/关系不变.
但同时把问题简化为简单的stationary的解.
换个角度考虑的话,其实就是对一个现有space的某种形式的cut/prune/classify.
在保证某种特性不变的前提下,以g做出一定形式的划分.
考虑把f(X)看作是一种feature -> object的函数.
比如X是一组feature,object是一个用户标识.
也就是说假设存在一种描述,使得这个描述对某个用户唯一.
即通过feature vector可以unique地locate到某个用户.
然后考虑有一个对用户的label函数.
使得每个用户对应一个label.
重新如lagrange multiplier的形式的等式.
\mathcal{L}(X) = f(X) + \lambda_a*g_a(X) + \lambda_b*g_b(X) + ...
当X被归类为a的时候,其余的\lambda*g(X) = 0.
即此时的\mathcal{L}(X) - f(X) = \lambda_a*g_a(X) != 0.
如果令lambda都等于1的话,则形式为:
\mathcal{L}(X) = f(X) + g_a(X) + g_b(X) + ...
->
\mathcal{L}(X) = f(X) + col_sum(G*X).
G为一个dim(label)行feature列的matrix,col_sum为对列做的算数和.
那么就有可能解出一个matrix G,使得col_sum(G*X) = 0
对于一个给定的x,apply之后有col_sum(x;G) == 0 意味着什么呢?
意味如果x是在X中,且其对于label a的话,
\lambda_a*g_a(X) + \lambda_b*g_b(X) + ... == 0
->
\lambda_a*g_a(X) == 0即与label a的前提矛盾.
所以如果col_sum(x;G) == 0 的话,则表明x必定不在X中.
那么如果col_sum(x;G) != 0的话呢?
明显也不能说明x就在X中.
因为可能存在g_b(X) != 0等的情况.
如果G*X得到的vector形式V是[1,0,0,0,...]的某个维度值为1的unit vector呢?
也不能.
因为如果把G看作是X向feature space的project的话.
对于某个vector来说,project成unit vector也不足以说明就是在原来的X space.
所以,某种程度上来说,这个只是一个dim(X) -> dim(label)的某种形式的类bloom filter.
即G*X != unit vector的话,则必然不在原来的X中.
2014-07-06
概率性的有效数据
之前有过一个想法,就是把低维的数据往高维变换,然后再投影回另外一个较低维的空间.
这个想法的目的在于,在通常情况下,对于一组数据,只能猜出有限的几个feature.
而"真实的计算系统"里,还有更多的想不到的,或者没有考虑进来的影响.
也就是说,"真实"的数据心态,在"真实"的演算系统里,是一个更高维的数据.
那么,如果不知道这些额外的feature是什么,但是知道有多少个这样的额外维度,并且能够找到一种往高维变换的方式,使得经过变换后与"真实"维度的数据是等价的话,这些额外维度是什么的问题也就没那么重要了.
因为已经有一个等价的数据变换,剩下的就是相应地拟合出这个变换下的演算系统,也就等于知道真实的演算系统了.
而实际上,neural network就是这样一个类似的系统.
只不过每个layer之间并不是直接映射,而是经过了sigmoid做了个调整.
那么,如果把sigmoid去掉呢?
于是在input和ouput之间,接了两个随机(Hyper,Project)矩阵乘,想着forward propagate过去,然后backward回来做拟合的.
对于第二个(Project)矩阵的每一个cell,它的每一个delta变化,应该是能够让其关联的output里的相应cell差值也减少的.
想了一下,其实就是对于Project中(i,j)个cell而言,有关系的是Hyper的第i列和Output的第j列相关而已.
即minimize(Hyper[,i]*(Project(i,j)-delta) - Output(,j)).
直觉上就是让一个向量A伸缩后,与另一个向量B的L2距离变小而已.
也就是类似算B在A上的投影.
所以,这个delta是可以直接算出来的.
然后是用这个新算出来的Porject,和Output去校准原来的Hyper.
也就是,在X*Y=Z的矩阵乘里,拟合一下X.
对于Hyper矩阵里的每一个cell,它的delta变化都会反映到Ouput里的对应行里.
并且,这个变化是和Porject的列数相关的.
也就是说,对于Hyper的第(i,j)个cell变化一个delta,Ouput[i,]的所有列都会有差值变化.
更主要的是,这些列的变化可能不是同向增减的.
折中一下的话,就是只处理同向增减的情况.
这种情况下选一个能使得差值更接近于0的delta就可以了.
于是,用上述算法跑了下拟合.
收敛倒是收敛的,不过拟合出来的结果没什么价值和意义.
原因可能跟数据本身的性质有关.
因为这里的假设是线性系统,而实际可能是非线性的.
所以结果没意义.
后来再想了一下,其实如果是线性系统的话,也不用这么麻烦.
因为中间的两个矩阵乘完全是多余的.
等价于一个矩阵乘而已.
于是,转化一下,就是通常的已知A和B,求x使得A*x=Y的问题了.
只不过这里A,x,Y都是非square matrix而已,不能直接numpy/scipy求逆.
于是只能手写了一个naive的方法,先把A化成阶梯形,然后吧对应的化简operation apply到Y,再一个个地解x拼回目标矩阵.
因为是naive的方法,所以实际跑一个4k+行矩阵的时候,operation记录太长,看着内存本子swap了,就算了.
只能取个20行装个样子.
结果当然是100% fit.
只不过用第20个data row去predicate第21行数据的时候,差地离谱.
原因嘛,跟之前差不多.
而且,即使系统是线性的,但是解并一定唯一,所以错很正常.
加上实际上,这个数据集的各列的取值范围还是有约束的,这个根本就没反映进去.
于是数据合理才是不正常的.
不过从这个角度来说,除非是自己"设计"出来的数据.
不然,应该没什么办法衡量什么才是正确/有效的数据吧.
因为谁也不知道真正的运算式是什么.
所谓概率性的有效数据.
这个想法的目的在于,在通常情况下,对于一组数据,只能猜出有限的几个feature.
而"真实的计算系统"里,还有更多的想不到的,或者没有考虑进来的影响.
也就是说,"真实"的数据心态,在"真实"的演算系统里,是一个更高维的数据.
那么,如果不知道这些额外的feature是什么,但是知道有多少个这样的额外维度,并且能够找到一种往高维变换的方式,使得经过变换后与"真实"维度的数据是等价的话,这些额外维度是什么的问题也就没那么重要了.
因为已经有一个等价的数据变换,剩下的就是相应地拟合出这个变换下的演算系统,也就等于知道真实的演算系统了.
而实际上,neural network就是这样一个类似的系统.
只不过每个layer之间并不是直接映射,而是经过了sigmoid做了个调整.
那么,如果把sigmoid去掉呢?
于是在input和ouput之间,接了两个随机(Hyper,Project)矩阵乘,想着forward propagate过去,然后backward回来做拟合的.
对于第二个(Project)矩阵的每一个cell,它的每一个delta变化,应该是能够让其关联的output里的相应cell差值也减少的.
想了一下,其实就是对于Project中(i,j)个cell而言,有关系的是Hyper的第i列和Output的第j列相关而已.
即minimize(Hyper[,i]*(Project(i,j)-delta) - Output(,j)).
直觉上就是让一个向量A伸缩后,与另一个向量B的L2距离变小而已.
也就是类似算B在A上的投影.
所以,这个delta是可以直接算出来的.
然后是用这个新算出来的Porject,和Output去校准原来的Hyper.
也就是,在X*Y=Z的矩阵乘里,拟合一下X.
对于Hyper矩阵里的每一个cell,它的delta变化都会反映到Ouput里的对应行里.
并且,这个变化是和Porject的列数相关的.
也就是说,对于Hyper的第(i,j)个cell变化一个delta,Ouput[i,]的所有列都会有差值变化.
更主要的是,这些列的变化可能不是同向增减的.
折中一下的话,就是只处理同向增减的情况.
这种情况下选一个能使得差值更接近于0的delta就可以了.
于是,用上述算法跑了下拟合.
收敛倒是收敛的,不过拟合出来的结果没什么价值和意义.
原因可能跟数据本身的性质有关.
因为这里的假设是线性系统,而实际可能是非线性的.
所以结果没意义.
后来再想了一下,其实如果是线性系统的话,也不用这么麻烦.
因为中间的两个矩阵乘完全是多余的.
等价于一个矩阵乘而已.
于是,转化一下,就是通常的已知A和B,求x使得A*x=Y的问题了.
只不过这里A,x,Y都是非square matrix而已,不能直接numpy/scipy求逆.
于是只能手写了一个naive的方法,先把A化成阶梯形,然后吧对应的化简operation apply到Y,再一个个地解x拼回目标矩阵.
因为是naive的方法,所以实际跑一个4k+行矩阵的时候,operation记录太长,看着内存本子swap了,就算了.
只能取个20行装个样子.
结果当然是100% fit.
只不过用第20个data row去predicate第21行数据的时候,差地离谱.
原因嘛,跟之前差不多.
而且,即使系统是线性的,但是解并一定唯一,所以错很正常.
加上实际上,这个数据集的各列的取值范围还是有约束的,这个根本就没反映进去.
于是数据合理才是不正常的.
不过从这个角度来说,除非是自己"设计"出来的数据.
不然,应该没什么办法衡量什么才是正确/有效的数据吧.
因为谁也不知道真正的运算式是什么.
所谓概率性的有效数据.
2013-08-01
偶然的相关性
某天某人提出想用FastDTW做一些已有统计数据的相关性计算.
FastDTW算是DTW的一个优化方式.
而DTW简单来说,就是计算两组数据的所有组合方式,然后找出一个cost最小的数据X->数据Y的映射关系/路线/矩阵的对角路线.
当想到映射这个词的时候,有种豁然开朗的感觉.
所谓两组数据存在相关性,也就是存在一个变换T,使得Y=T(X)成立.
简单假设这个变换是线性的话.
那么两条曲线是否相似的问题就转化为,线性拟合后的曲线T(X)与Y的误差是否在合理范围内了.
所以,简单地对各条曲线做两两组合的线性拟合,然后看方差就大致可以得出那些曲线是存在相关性/联动的了.
更进一步地,曲线间做个相对序列平移的话(比如X[:-1]与Y平移4位后的Y[4:-1]),也可以做一个类似"因果"关系的拟合.
问题是,由于各组数据间的数量级不尽相同,直接的方差比较就没什么太大的意义了.
一个思路是对方差做normalize,使其规约到同等范围内.
另一个思路是直接对源数据做feature scaling.
对前一种思路并没有想到很好的方法.
直觉上应该都是需要跟源数据/期望做一些运算得出一个相对的scaling function/mapping/transform的.
这样的话,不如直接最开始就采用后者.
而且这个也有比较通常的做法.
对于给定数据X,简单的(X-mean(X))/std(X),源数值减去均值,然后对比标准差做个缩放.
而且由于前提假设是线性换掉拟合,因此,对于任意两组数据,X,Y,scale之后跟之前的差别不过再多一重线性变换而已.
因为mean(X),std(X)都可各自认为是常数.
于是,保证了变换后进行拟合的合理性.
剩下的就是蛮力地对所有可能的组合进行拟合比较方差了.
实际的实验是拿了大概200组各游戏的30天日统计数据.
也就是每组数据大概30个值吧.
组合之后,排除一些无意义的组合(自身跟自身,前后排列重复的),大概就剩下17k左右的拟合结果把.
随意选了一些方差小的来看,结果其实挺尴尬的.
比如有一个结果是某游戏的累计MAU(monthly active user)和另一个游戏的DNU(daily new user).
前者是个每天累计的值,原则上来说是每天递增的.
后者则是一个浮动值.
对于这个结果的解释,大概就是恰好DNU一直在下降吧.
于是就不小心负相关了.
而一些数据则是比较正常的.
比如某游戏的各地区汇总DAU和某主要地区DAU之间的正相关.
所以说,相关性这东西,只能说可能存在关系.
false positive的情况还是比较普遍的.
对于不能解释的相关性,如果硬要拿来作为决策的依据的话,感觉跟掷骰子赌一把没什么区别.
一个简单的例子就是,每次下雨的同时说一句要下雨了.
那么从数据上来说,下雨和说下雨是相关的.
而以观察某人是否说下雨来预报天气的话,多少显得儿戏.
尽管,严格来说,这种"气象预测"是准确的.
因为确实每次说下雨的时候都在下雨.
但矛盾点在于,它颠倒了因果关系.
虽然,用前面的话来说,通过一些平移可以做一些"因果关系"的拟合.
不过始终的,相关性只是说明了一个结论.
对于发生的过程并没有任何信息.
从科学的角度来说,相关并不一定是可"准确"重现的一个结论.
能不能有效,多数时候是"运气"使然.
所谓偶然的相关性.
FastDTW算是DTW的一个优化方式.
而DTW简单来说,就是计算两组数据的所有组合方式,然后找出一个cost最小的数据X->数据Y的映射关系/路线/矩阵的对角路线.
当想到映射这个词的时候,有种豁然开朗的感觉.
所谓两组数据存在相关性,也就是存在一个变换T,使得Y=T(X)成立.
简单假设这个变换是线性的话.
那么两条曲线是否相似的问题就转化为,线性拟合后的曲线T(X)与Y的误差是否在合理范围内了.
所以,简单地对各条曲线做两两组合的线性拟合,然后看方差就大致可以得出那些曲线是存在相关性/联动的了.
更进一步地,曲线间做个相对序列平移的话(比如X[:-1]与Y平移4位后的Y[4:-1]),也可以做一个类似"因果"关系的拟合.
问题是,由于各组数据间的数量级不尽相同,直接的方差比较就没什么太大的意义了.
一个思路是对方差做normalize,使其规约到同等范围内.
另一个思路是直接对源数据做feature scaling.
对前一种思路并没有想到很好的方法.
直觉上应该都是需要跟源数据/期望做一些运算得出一个相对的scaling function/mapping/transform的.
这样的话,不如直接最开始就采用后者.
而且这个也有比较通常的做法.
对于给定数据X,简单的(X-mean(X))/std(X),源数值减去均值,然后对比标准差做个缩放.
而且由于前提假设是线性换掉拟合,因此,对于任意两组数据,X,Y,scale之后跟之前的差别不过再多一重线性变换而已.
因为mean(X),std(X)都可各自认为是常数.
于是,保证了变换后进行拟合的合理性.
剩下的就是蛮力地对所有可能的组合进行拟合比较方差了.
实际的实验是拿了大概200组各游戏的30天日统计数据.
也就是每组数据大概30个值吧.
组合之后,排除一些无意义的组合(自身跟自身,前后排列重复的),大概就剩下17k左右的拟合结果把.
随意选了一些方差小的来看,结果其实挺尴尬的.
比如有一个结果是某游戏的累计MAU(monthly active user)和另一个游戏的DNU(daily new user).
前者是个每天累计的值,原则上来说是每天递增的.
后者则是一个浮动值.
对于这个结果的解释,大概就是恰好DNU一直在下降吧.
于是就不小心负相关了.
而一些数据则是比较正常的.
比如某游戏的各地区汇总DAU和某主要地区DAU之间的正相关.
所以说,相关性这东西,只能说可能存在关系.
false positive的情况还是比较普遍的.
对于不能解释的相关性,如果硬要拿来作为决策的依据的话,感觉跟掷骰子赌一把没什么区别.
一个简单的例子就是,每次下雨的同时说一句要下雨了.
那么从数据上来说,下雨和说下雨是相关的.
而以观察某人是否说下雨来预报天气的话,多少显得儿戏.
尽管,严格来说,这种"气象预测"是准确的.
因为确实每次说下雨的时候都在下雨.
但矛盾点在于,它颠倒了因果关系.
虽然,用前面的话来说,通过一些平移可以做一些"因果关系"的拟合.
不过始终的,相关性只是说明了一个结论.
对于发生的过程并没有任何信息.
从科学的角度来说,相关并不一定是可"准确"重现的一个结论.
能不能有效,多数时候是"运气"使然.
所谓偶然的相关性.
订阅：
博文 (Atom)