机器学习基石笔记 感知机 损失函数 给定一个数据集 $T ={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$ , 其中 $x = R^n , , y={+1,-1}$ 若存在超平面S $w\cdot x + b = 0$ 能将所有的正负实例点分到两侧，则称数据集是线性可分的，否则称线性不可分。 任意一点$x_0$到超平面的距离为 $$\frac{1}{||w||}|w\cdot x_0 + b|$$ 对于误分类数据$(x_i,y_i)$来说， $-y_i(w\cdot x_i + b) > 0$ 有误分类点到超平面距离 $$-\frac{1}{||w||}y_i|w\cdot x_0 + b|$$ 则所有误分类点到超平面距离为 $$-\frac{1}{||w||}\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$ 所以感知机$sign(w\cdot x + b)$学习损失函数为 $$L(w,b) = -\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$ 学习算法 选取初值$w_0,b_0$ 在训练集中选取数据$(x_i,y_i)$ 如果$y_i(w\cdot xi+ b) \leq 0$（分类错误） $$w \leftarrow w + x_iy_i$$

最大值栈和最大值队列(Tsinghua OJ,PA2) 最大值栈 要求 以O(1)的时间查询栈中的最大值. 思路 维护一个最大值栈，在原栈中数据发生改变时最大值栈也跟着改变。 每次输入一个数据，若最大值栈为空，则比较最大值栈栈顶和当前元素，如果当前元素较大或相等，就把当前元素推入栈中，反之出栈时，如果出栈元素和当前元素相等，则把最大值栈中元素也推出栈。 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 template <typename T> class MaxStack { private: Stack <T> max_stack; Stack <T> _data; public: T max(){ return max_stack.top(); } void push(T ele){ _data.push(ele); if(max_stack.empty() || ele >= max_stack.top()){ max_stack.push(ele); } } T pop(){ T tmp = _data.top(); if(_data.

逆序对计算的思考(Tsinghua OJ,PA1) 题目出自清华DSA的Programming Assignment作业灯塔(LightHouse)． 描述 海上有许多灯塔，为过路船只照明。 如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。 若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。 现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。 输入 共n+1行。 第1行为1个整数n，表示灯塔的总数。 第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。 输出 1个整数，表示可照亮彼此的灯塔对的数量。 样例 Input: 1 2 3 4 3 2 2 4 3 5 1 Output: 1 1 限制 对于90%的测例：1 ≤ n ≤ 3×10^5 对于95%的测例：1 ≤ n ≤ 10^6 全部测例：1 ≤ n ≤ 4×10^6 灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异 1 ≤ x, y ≤ 10^8 时间：2 sec 内存：256 MB 提示 注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 - 1]，不一定足够容纳本题的输出。 思考 我们把灯塔坐标抽象为坐标结构体 1 typedef struct pos{ long x,y; }Pos; 照亮的情况为一个灯塔在另一个灯塔的一四象限，即$tower1.

DP解决钢条切割问题 （原题见算法导论·动态规划） 对长度为n的钢条进行切割，对应的切割长度和价格对应如下： int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; 比如1对应价值1,10对应价值30。即相应的下标和值的对应。现求切割所得最大效益mx。 递归算法 1 2 3 4 5 6 7 8 9 int cut_rod(int *cost,int n) { if(n == 0) return 0; int limit = MIN(n,10); //分割第一条的上限 int mx = -1; for(int i = 1;i <= limit; ++i) mx = maxnum(mx,cost[i]+cut_rod(cost,n-i)); //取当前值于递归值的最大值 return mx; } 由于对相同子问题的重复求解，T(n) = 2^n 递归标记数组算法（自顶而下）（DFS） 1 2 3 4 5 6 7 8 9 10 11 12 int mem_cut_rod(int *cost,int n,int *mem) //mem数组长度为n,所有元素须在其他函数中初始化为-1 { int mx; if (mem[n] >= 0) return mem[n]; //对于求过的问题，直接返回存储的值 if (n == 0) mx = 0; else mx = -1; int limit = MIN(n,10); for(int i = 1;i <= limit; ++i) mx = maxnum(mx,cost[i]+mem_cut_rod(cost,n-i,mem)); //后面的内容和递归型是一样的 mem[n] = mx; //储存计算出的新值 return mx; } 逆拓扑序DP（自底向上） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int bottom_cut_rod(int *cost,int n) { int mem[MEM_LEN+1]; //MEM_LEN = n，设置标记数组 mem[0] = 0; //i,j将从1开始，这里收益是0 for(int i = 1; i <= n; ++i) //从第一个问题开始求解 { int mx = -1; int limit = MIN(i,10); for(int j = 1;j <= limit; ++j) mx = maxnum(mx,cost[j] + mem[i-j]); //求解最小的问题 mem[i] = mx; } return mem[n]; } 我们可以看到，2,3 的解法复杂度均为O(n^2)。