Dimension Reduction 降维: 随机投影与JL 变换

关于维度爆炸的问题,历来探讨的都很广泛。存在于很多真实的问题中,比如 nearest neighbor,最近邻问题,这里总结一种简单的技术,叫做随机投影(random projection)

最近邻问题的简单描述如下:

给定 $k$ 维空间 $R^k$ 中的 $n$ 个点 $x_1,x_2,\dots ,x_n$,找到每个点的最近邻居 $NN_i = …

阅读全文

Support Vector Machine

简单总结一下SVM,以帮助ML相关面试

SVM 是一种上古时代(90s) 的东西,其实我也不清楚他在工业界的用处到底几何。只是感觉算法特别慢,还意义不太大。

intuition

首先SVM的动机其实很简单。我们都知道对于分类问题(这里以二分类为例),就是要找一个超平面将正例和负例分开,而SVM找的这个超平面相对比较特殊,他希望找到一个超平面,s.t …

阅读全文

Kickstart 2019 Round E

A. Cherries Mesh

easy

code : github

B. Code-Eat Switcher

这题结束后想通了,可以贪心,将 $(c_i,e_i)$ 按照 $c_i / e_i$ 排序,然后贪心.

codegithub

C. Street Checkers

这题还是很容易的,

首先翻译一下题意,对于一个数 $X$, 如果它 …

阅读全文

Kickstart 2019 RoundD

整体来说这次的题不是很难,我都能自己想出来,并写完,但是这次马力有点大,C题写了2hrs…

A.X or What?

这题比较简单,重点在一个 xor的性质,与位的异或次序无关即两数$A,B$ 共 $K$ 位

$$ \bigwedge_i A_i \wedge B_i = (\bigwedge_i A_i)\wedge …

阅读全文

Kickstart 2019 RoundC 题解

A. Wiggle Walk

难度 模拟,编码,hashtable

这个题比较简单,可以直接模拟,用一个 hashtable 维护 dp[x][y][dir] [注意这里不是开数组], 因为只有 $N \le 5e4$ 个点所以用hashtable维护就好,复杂度 $O(n)$

code : github

B. Circuit Board …

阅读全文

KM Algorithm--二分图最大权匹配

很久以前打ACM的时候学过这个算法,但到用的时候还是忘了,起因是来源于这样一个问题:

给定任意一个矩阵 $nXn$, 选取其中 $n$ 个点,$s.t.$ 任意两个点 不在同一行,同一列,求这 $n$ 个点的和的最大值.

这个问题可以很简单的转化为 最大流,或者最大权匹配问题来求解。

可是难受的是这两个算法都忘了,不会敲,所以又重新拿起遗忘的知识, …

阅读全文