经验误差与过拟合

##错误率
错误率（error rate）：分类错误的样本数占样本总数的比例
精度（accuracy）：精度=1-错误率

如果在m个样本中有a个样本分类错误，
则错误率：
$$E=a/m$$
精度：
$$1-a/m$$

误差error：学习器的实际预测输出与样本的真实输出之间的差异；
训练误差/经验误差：学习器在训练集上的误差；
泛化误差：在新样本上的误差。

我们希望得到泛化误差小的学习器，即在新样本上能表现得很好的学习器。。

过拟合和欠拟合

Introduction

• Give a definition of “Computer Vision”.
• What type of information is extracted in each of the following applications.
• Vision is often described as an “ill-posed, inverse problem”. Briefly describe what is meant by the terms “ill-posed” and “inverse problem” and their opposites “well-posed” and “forward problems”.
• What is a “prior” and how does it help solve the ill-posed, inverse problem of vision? Give examples of priors.

Overview of image formation

• Light from a radiation source is reflected by surfaces in the world..
• Refleted light passes through some optics and is recorded by a sensor
• Images are formed when a sensor registers radiation that has interacted with physical objects

Introdution to Linear Programming

Definitions

• Objective function: linear function,$z$, we want to optimise
• Variables: $x_j$ amounts we seek to assign values to, in order to optimise the objective function.
• Constraints: linear (in)equalities that must be satisfied by an assignment of variables
  • Non-negativity constraints: constraints of the type $x_j≥0$
  • Resource constraints: the other constraints are often termed as resource constraints(or just constraints when it’s clear from the context).
• Optimal solution: feasible point(s) at which the objective value is the largest (in case of maximisation) or smallest(in case of minimisation) among all feasible points.
• Feasible point: point $x$ is feasible for a linear program if it satisfies all its constraints.
• Feasible region: set of all feasible points of the problem.

统计学习方法三要素

统计学习方法都是由模型、策略和算法构成的，即统计学习方法由三要素构成，可以简单地表示为：
$$方法=模型+策略+算法$$

写在前面

主要四道题目，1道easy，2道medium，1道hard
主要题目如下：

• Special Array With X Elements Greater Than or Equal X
• Even Odd Tree
• Find Valid Matrix Given Row and Column Sums
• Minimum One Bit Operations to Make Integers Zero

滑动窗口算法

该算法是通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低了循环的嵌套深度。

贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，做出的是某种意义上的局部最优解。

思想

• 建立数学模型来描述问题；
• 把求解的问题分成若干个子问题；
• 对每个子问题求解，得到子问题的局部最优解；
• 把子问题的解局部最优解合成原来解问题的一个解。

写在前面

一共四题，1题easy，2题medium，1题hard
第一道，简单的系统设计题，要清楚object function；
第二道，同样应用题，但是通过率不高；
第三道，给出制定行和&列和的矩阵；
第四道，

• Design Parking System
• Alert Using Same Key-Card Three or More Times in a One Hour Period
• Find Valid Matrix Given Row and Column Sums
• Find Servers That Handled Most Number of Requests

卡诺图 karnaugh map

卡诺图是由美国工程师karnaugh首先提出的一种用来描述逻辑函数的特殊方格图。
在这个方格图中，每个方格代表逻辑函数的一个最小项，而且几何相邻（在几何位置上，上下或左右相邻）的小方格具有逻辑相邻性，即两相邻小方格代表的最小项只有一个变量取值不同。

对于有n个变量的逻辑函数，其最小项有$2^n$个。
因此该逻辑函数的卡诺图又$2^n$个小方格构成，每个小方格都满足逻辑相邻项的要求。
可以运用于逻辑函数的化简。