Git的想象力

最近因为发现git gc --prune能省不少空间,于是就想起去翻翻git的文档.

虽然用git也算有几年了,但多数还是当作一种version control的东西来用.
看了之后才发觉,这个不单跟传统的version control有很大区别,甚至跟version control本身也有相当程度的不同.

官方文档给出的直观解释是git本身是一个类似的snapshot的管理工具.
跟version control不同,它目的似乎不是为了存储变更记录,而是存储变更本身.

换句话说,version control做的事情的专注点在于replay changeset.
而git的侧重点似乎在于各个snapshot之间的traversal了.

虽然看上去好像是差不多的事情,但是对个人来说,还是挺大的一个观念转变的.

以每一个单独的文件为视角的话,其实就是一个类似state transfer的graph,不同的branch以及sub tree就是不同的edge set.

考虑到每个transfer都是一个文件hash为基础的,那么就存在一些merge或者rebase,使得这个文件的history graph不是一个单纯的树.
而是存在一些环壮结构.
因为可能后面的改动会使得文件跟之前的某个"版本"一致.

从repo的角度看的话,就是一个文件代表着一个这样的graph.
而repo角度的change set则是这个repo下面的某些文件集合的change set构成的.

也就是说,对于这个repo的某个"version"来说,相当于在这些文件的graph之间,以这个version标记的change set产生了联系.
也就是直观上的,把每个文件的graph以version的维度连接了起来.

因为repo本身有多个version.
所以,这些被连接起来的graph,在不同的version层次又有着不同的连接.

也就是说,原来的一个graph forest变成了一个hyper graph.

如果再以类似github这种地方,把各个repo的hyper graph以文件为基准连接起来的话,就是一个更复杂的hyper graph了.

这个隐含的假设是,不同的项目之间,存在着相同的文件/实现.
通过这些共同点,就有可能把各个repo连接起来.

这样的话,就存在一个联通的hyper graph,使得这个hyper graph实际上是有多个repo的history构成的.

那么,这样的hyper graph有什么用的?

至少可以用来做一些简单统计吧.
比如公用了某个库或者文件的项目有哪些,或者某个repo的链入/热度/受欢迎程度如何.

实际一点的,可能是解决project的版本冲突问题.
比如,根据当前的版本,就可以"横向"地从其他repo里根据公有文件的version,cut出一个aspect来,使得所有文件都是处于同一个版本时间线上的.
而在即使这样都不能解决版本冲突的情况下,至少还能对冲突的部分做出具体的冲突比较,看是不是可以兼容的.

事实上,这就类似于page之间的link.
本质就是一些hyper graph.

至于要用来rank还是拿来干其他什么.

剩下的就是想象力的问题了.

概率性的有效数据

之前有过一个想法,就是把低维的数据往高维变换,然后再投影回另外一个较低维的空间.

这个想法的目的在于,在通常情况下,对于一组数据,只能猜出有限的几个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行数据的时候,差地离谱.

原因嘛,跟之前差不多.
而且,即使系统是线性的,但是解并一定唯一,所以错很正常.

加上实际上,这个数据集的各列的取值范围还是有约束的,这个根本就没反映进去.
于是数据合理才是不正常的.

不过从这个角度来说,除非是自己"设计"出来的数据.
不然,应该没什么办法衡量什么才是正确/有效的数据吧.

因为谁也不知道真正的运算式是什么.

所谓概率性的有效数据.