Linear models

matrix multiplication: fast with GPU
numerically stable
cannot cocatenate linear units → equivalent to one big matrix...

⇒ add non-linear units in between

rectified linear units (RELU)

chain rule: efficient computationally

back propagation

easy to compute the gradient as long as the function Y(X) is made of simple blocks ...

这是udacity上deeplearning的笔记, 做得非常粗糙, 而且这门课也只是介绍性质的... https://www.udacity.com/course/deep-learning--ud730

Softmax function

socres yi ⇒ probabilities pi

property: smaller scores ⇒ less certain about result

Onehot encoding

Cross entropy

measure how well the probability vector S corresponds to the label vector L. ⇒ cross entropy D(S,L)( D>=0, the smaller the better ...

1. Introduction to Intractability

recall model of computation: DFA
a univeral model of computation: turing machine
→ no more powerful model of computation.
Turing machine can compute any function that can be computed by a physically harnessable process of the natural world.

bottom line: turing machine is a simple and universal ...

simplex algo: top 10 algo of the 20th century (ever?).

what is linear programming:
a general problem-solving model that works for:
shortest-path, maxflow, MST, matching, assignment, ...

1. Brewer-'s Problem

toy example: choose products to maximize profit.
...
feasible region: a convex polygon.

⇒ optimum solution appears at an extreme point.

standard ...

http://www.imooc.com/learn/317

模块和包

包: 文件夹 (可以有多级), 且包含__init__.py文件(每层都要有) 模块: py文件

代码分开放在多个py文件(模块名=文件名). 同名变量互不影响.

模块名冲突: 把同名模块放在不同包中.

导入模块

from math import log
from logging import log as logger

引用时: 使用完整的路径(包+模块名). ex. p1.util.f()

动态导入模块

try:
    from cStringIO import ...

Goal: classify problems according to computational requirements.
bad new: for huge number of pbs we don't know...

1. Introduction to Reductions

shifing gears:

• from individual problems to problem-solving models.
• from linear/quard to polynomial/exponential pbs
• from implementation details to conceptual framwork

suppose we could (not) solve pb X ...

http://www.imooc.com/learn/317

函数式编程: 更抽象, 更脱离指令(计算机), 更贴近计算(数学).

• 不需要变量 (python允许有变量, 所以python非纯函数式)
• 高阶函数
• 闭包: 返回函数
• 匿名函数

高阶函数

• 变量可以指向函数 f=abs; f(-10)
• 函数名: 就是指向函数的变量 abs=len

• 高阶函数: 接收函数作为参数的函数

  def add(x,y,f):
  return f(x)+f(y)
  add(-5, 9, abs)

map()

map()是 Python 内置的高阶函数 ...

1. Introduction to Data Compression

pb: reduce the size of a file, to save space/time for storing/transmitting.
applications: generic file compression(gzip), multimedia (mp3), communication(skype).

From binary data B, ⇒ generate a compressed representation C(B).

lossless compression: get exactly B from C(B)
compression ratio: |C(B ...

1. Regular Expressions

pb: pattern matching.

regular expression

Is a notation to specify a set of strings.
basic operations:

• concatenation
• or
• closure: "0 or more appearances of chars"
• parentheses

additional operations (added for convinence):

ex. [A-C]+ is equivalent to (A|B|C)(A|B|C)*.

吐槽名句:

2. REs and NFAs ...

1. Introduction to substring search

"most ingenious algorithm we've seen so far"
pb. having two strings, pattern and text, len(pattern)=M << len(text)=N, try to find pattern in text.

ex. indexOf method of String in java.

2. Brute-Force Substring Search

function signature:
public static int search(String ...