CUHK CSCI5030

instructor: XU Lei

来自 交大 的大佬教授。

大佬就是大佬，直接用中文。

四年来第一次上中问的专业课，感觉exciting。

Preface

Probability distributions

• Uniform
• Poisson
  • Discrete
  • Parameter: $\lambda$
  • $P(X = k) = \frac {e^{-\lambda}\lambda^k}{k!}$
• Normal
• t-dis???
• Chi-square 卡方分布
  • k个独立的标准正态分布变量的平方和
  • parameter:k
• Cauchy

Benford’s Law

$P(d) = log_{10}(d+1)-log_{10}(d)$, where d is the case that the first digit of the data is d

Ch 1

Sample space: $S$

event:

• subset of $S$
• measurable, (can assign a probability)
• subset is NOT event

Conditional Probability:

$P(A|B) = \frac{P(A\cap B)}{P(B)}$

Bayes theorem

$P(A) = \sum{P(A\cap B_i)}$

Now: We want to know: if A happened, what are the p of different B?

$P(B_j|A) = \frac{P(A\cap B_j)}{P(A)}$

$P(A\cap B_j) = P(A|B_j)P(B_j)$

Bayes theorem definition:

Consider a partition $B_j$ of $S$ and event $A$:

$P(B_j|A) = \frac{P(A\cap B_j)}{P(A)}= \frac{P(A|B_j)P(B_j)}{\sum{P(A|B_i)P(B_i)}}​$

Monty Hall Problem

$B_j = C_2|X_1, A = H_3|X_1$

Ch 2 Discrete Random Variables

Mean is the quantity a that minimizes $min_aE(X-a)^2$

Variance $(x-E(x))^2$

Moment generating function = mgf = summary of the overall random behavior

median $min_b |x-b|$

新的一年

惟愿此心无怨尤。

Tensor to numpy array

In Tensorflow, kernel (tf.Variable) can be easily accessed by slim.get_model_variables() (return a list of tf.Variable)if using slim package. Also, if we want to access corresponding

• name: simply by .name
• value: sess.run

1
2
3
4
5
6
7

   weights = slim.get_model_variables()
   #sturcture: list of variable name
structure = []
   for i in range(len(weights)):
       structure.append(weights[i].name)
   #weights: list of variable value(numpy array)
   weights = self.sess.run(weights,feed_dict={})

Numpy array to file

BAD TRY: numpy.savetxt

Extracted numpy array is usually multi-dimentional, therefore numpy.savetxt is not applicable, because it requires a 1-d or 2-d array.

BAD TRY: numpy.save

pretty easy to use, but only applicable when we only need to load the file using Python, but we need to implement a C code in our project

SUCCESSFUL: scipy.io.loadmat

numpy to .mat file, need a dic to generate the file, therefore we need the name of tf.variable above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import numpy as np
import scipy.io
class extractor:
    def __init__(self,filepath):
        self.filepath = filepath
    def tensor_to_file(self,tensor_list,structure):
        mat_dict = {}
        for i in range(len(tensor_list)):
            mat_dict.update({structure[i]:tensor_list[i]})
        scipy.io.savemat(self.filepath,mdict=mat_dict)
        print '.mat file has been saved.'
    def file_to_tensor(self):
        tensor_dic = scipy.io.loadmat(self.filepath)
        print '.mat file has been loaded.'
        return tensor_dic

• speed up trainning:
  • gradient computation -> 0 or 1
  • computation of ReLU is also easy, 0 or original
• vanishing gradient problem
• sparse output, reduce overfitting, (like L1 reg)

1. Introduction

We need to consider more about transformation rather than information.
eg. Expect top3, but 8th.
除去多余石头，变成大卫

Two keys to be extraordinary successful
1.Believe in yourself.
2.Keep asking questions.Not satisfied with an offer.

2. Why positive psychology

Most papers, researchers focus on negative such as depression,
few is working on what works, such as positive feelings.

Why deeper? not fatter?

• Analogy: Using multiple layers of neurons (logic gates) to represent some functions are much simpler

• deeper layer ->Modularization (More kinds of module with less training data)

  low layer = basic module = enough training data

Bad training results?

• choosing proper loss

  softmax output layer -> cross entropy

  And its partial derivation by W is:

  $\begin{eqnarray} \frac{\partial C}{\partial w_j} & = & \frac{1}{n} \sum_x \frac{\sigma’(z) x_j}{\sigma(z) (1-\sigma(z))} (\sigma(z)-y). \tag{60}\end{eqnarray}$

  Because the final activation function is usually softmax, therefore,

  $\begin{eqnarray} \frac{\partial C}{\partial w_j} = \frac{1}{n} \sum_x x_j(\sigma(z)-y). \tag{61}\end{eqnarray}$

• mini-batch

  • for each batch(n=1000), update parameters by picking mini-batches. ( the total loss is not the whole batch loss, but a mini-part).
  • If there are 20 batches, update 20 times in one epoch. ( Shuffle the training examples for each epoch)

• Vanishing Gradient Problem

  lower layer = smaller gradients = slow learning = almost random

  deeper layer = larger gradients = fast learning = already converge

  • ReLU

    1. Fast to computer
    2. Biological reason
    3. Infinite sigmoid with different biases
    4. Vanishing gradient problem

    $\dfrac{\partial{C}}{\partial{b_{1}}}=\sigma^{\prime}(z_{1})\omega_{2}\sigma^{\prime}(z_{2})\omega_{3}\sigma^{\prime}(z_{3})\omega_{4}\sigma^{\prime}(z_{4})\dfrac{\partial{C}}{\partial{a_{4}}}$

    where $\sigma^{\prime}(z)$ is the activation function respectively. Therefore, ReLU = 1

• Adaptive Learning Rate

  If learning rate is too large, Total loss may not decrease after each update

  If learning rate is too small, Training would be too slow

  Reduce the learning rate by some factor every few epochs:

  • Adagrad

    Learning rate is smaller and smaller for all parameters

    Smaller derivatives, larger learning rate, and vice versa

• Momentum

Bad test result? overfittting?

• Early Stopping

• L2 regu

  我们拿 L2正则化来探讨一下, 机器学习的过程是一个 通过修改参数 theta 来减小误差的过程, 可是在减小误差的时候非线性越强的参数, 比如在 x^3 旁边的 theta 4 就会被修改得越多, 因为如果使用非线性强的参数就能使方程更加曲折, 也就能更好的拟合上那些分布的数据点. Theta 4 说, 瞧我本事多大, 就让我来改变模型, 来拟合所有的数据吧, 可是它这种态度招到了误差方程的强烈反击, 误差方程就说: no no no no, 我们是一个团队, 虽然你厉害, 但也不能仅仅靠你一个人, 万一你错了, 我们整个团队的效率就突然降低了, 我得 hold 住那些在 team 里独出风头的人. 这就是整套正规化算法的核心思想. 那 L1, L2 正则化又有什么不同呢?

  l1:

  尽量稀疏 和dropout 类似

• Weight Decay

  $w = 0.99 w - learning~rate * gradient$

• Dropout

  • Each time before updating the parameters: Each neuron has p% to dropout

  • The structure of the network is changed

  • Using the new network for training

  • For each mini-batch, we resample the dropout neurons

  • If the dropout rate at training is p%, all the weights when testing times (1-p)%

  • Reason

    • When teams up, if everyone expect the partner will do the work, nothing will be done finally

      However, if you know your partner will dropout, you will do better.

      When testing, no one dropout actually, so obtaining good results eventually.

    • Dropout is a kind of ensemble

      Train a bunch of networks with different structures

• $\Delta$ : \Delta
• $\leftrightarrow$ : \leftrightarrow
• $\Rightarrow$: \Rightarrow
• $\neg$: \neg
• $\wedge$: \wedge
• $\vee$: \bee
• $\sum_{n = 0}^{\infty}$: \sum_{n = 0}^{\infty}
• $\lambda$: \lambda

CSCI3230 HW3 Li Wei 1155062148

test!

1. Information Theory and Logic

a.

define $P_{front}$ and $P_{back}$ as the possibilities of front and back respectively. And we have:

$P_{front}+P_{back} = 1$

$I(V) = 0$: The coin flipping result must be front/ back, which means its possibility is 1. $P_{front} \ or \ P_{back} =1$ so that $I(V) = - 0\times log_2 0 - 1\times log_21 = 0$

$I(V) = log_2n$: The possibility of front and back are same, which is 0.5 respectively. $P_{front} =P_{back} =0.5$ so that $I(V) = - 0.5\times log_2 0.5 - 0.5\times log_20.5 = log_22=1$

b.

R1:

$Pass(x,computer) \wedge Win(x,prize)\rightarrow Happy(x)\Rightarrow $

$\neg(Pass(x,computer) \wedge Win(x,prize)) \vee Happy(x) \Rightarrow$

$\neg Pass(x,computer) \vee \neg Win(x,prize) \vee Happy(x) $

R2:

$Study(y) \vee Lucky(y) \rightarrow Pass(y,z) \Rightarrow$

$\neg(Study(y) \vee Lucky(y)) \vee Pass(y,z) \Rightarrow$

$(\neg Study(y) \wedge \neg Lucky(y)) \vee Pass(y,z) \Rightarrow$

$(\neg Study(y) \vee Pass(y,z)) \wedge(\neg Lucky(y)\vee Pass(y,z))$

R3:

$Lucky(w) \rightarrow Win(w,prize) \Rightarrow$

$\neg Lucky(w) \vee Win(w,prize) $

2. Neural Network

a.

$O = f(\sum_{j=1}^{n} (w_jI_j)+ w_o)$

b.

$h_{i,k} = f(\sum_{j = 1}^{H_{i-1}}(w_{i-1,j,k}h_{i-1,j}))$

$O_m =f(\sum_{j = 1}^{H_{K}}(w_{K,j,m}h_{K,j})) $

c.

$f’(z) = (\frac{1}{1+e^{-z}})’ = \frac{e^{-z}}{(1+e^{-z})^2} = \frac{1}{1+e^{-z}}\times \frac{e^{-z}}{1+e^{-z}}= f(z)(1-f(z))$

d.

Learning rate represents the impact of the correction applied following a training step. The bigger the learning rate, the more drastic the changes at each step. And if we set learning rate as 1, which means no learning rate, we’ll mostly likely start diverging away from the minimum. Therefore, we need a learning rate to control the changing velocity of weights and it is better to use a smaller learning rate.

e.

1. $\frac{\delta E}{\delta w_{K,j,k}} = \frac{\delta E}{\delta O_k}\cdot \frac{\delta O_k}{\delta w_{K,j,k}}= (O_k - T_k)\cdot O_k\cdot(1-O_k)\cdot h_{K,j}​$ (because $E = 0.5\sum_{m=1}^{H_{K+1}}(O_m - T_m)^2 \ and\ O_ k=f(\sum_{j = 1}^{H_{K}}(w_{K,j,k}h_{K,j}) ) ​$)

2. considering $E=F(h_{i+2,1}+ …+ h_{i+2,H_{i-2}})$ and $h_{i+2,j} = G(h_{i+1,k})$, according to the multivariate chain rule:

   $\frac{\delta E}{\delta h_{i+1,k}} = \sum_{j=1}^{H_{i+2}}(\frac{\delta E}{\delta h_{i+2,j}} \cdot \frac{\delta h_{i+2,j}}{\delta h_{i+1},k})$

   $=\sum_{j=1}^{H_{i+2}}(\frac{\delta E}{\delta h_{i+2,j}}\cdot h_{i+2,k}\cdot (1-h_{i+2,k})\cdot w_{i+1,k,j}) = \sum_{j=1}^{H_{i+2}}\Delta_{i+2,j} \cdot w_{i+1,k,j}$

3. According to chain rule, we have

   $\frac{\delta E}{\delta w_{i,j,k}} = \frac{\delta E}{\delta h_{i+1},k} \cdot \frac{\delta h_{i+1},k}{w_{i,j,k}}$

   And $\frac{\delta h_{i+1,k}}{w_{i,j,k}} = f’(\sum_{j = 1}^{H_{i}}(w_{i,j,k}h_{i,j}))\cdot h_{i,j}= h_{i+1,k}\cdot (1-h_{i+1,k})\cdot h_{i,j}​$

   Therefore, the result is:

   $\frac{\delta E}{\delta w_{i,j,k}} = (\sum_{j=1}^{H_{i+2}}\Delta_{i+2,j} \cdot w_{i+1,k,j})\cdot h_{i+1,k}\cdot (1-h_{i+1,k})\cdot h_{i,j} $

   ---

4. def BP(network,examples,a) return a modified network:
   INPUTS:
   network, a multilayer network
   examples, a set of data/label pairs
   a, learning rate

   Repeat:

   for each e in examples:
   $O \leftarrow Run(Network, e)$
   for each neuron in network:

    $\Delta_{K+1,k} \leftarrow (O_k - T_k)\cdot O_k\cdot(1-O_k)\cdot h_{K,j}$
   

   ​ for each weight connected to corresponding neuron:

   ​ $W_{K,j,k} \leftarrow W_{K,j,k} - a\cdot \Delta_{K+1,k} \cdot h_{K,j}$

   for each sub-layer except the first layer:

   ​ **for each ** neuron in sub layer:

   ​ $\Delta_{i,k}= (\sum_{j=1}^{H_{i+1}}\Delta_{i+1,j} \cdot w_{i,k,j})\cdot h_{i,k}\cdot (1-h_{i,k})\cdot $

   ​ for each weight connected to corresponding neuron in current sublayer:

   ​ $W_{i,j,k} \leftarrow W_{i,j,k} - a\cdot \Delta_{i+1,k} \cdot h_{i,j}$

   Until network has converged

   return network

   ---

ESTR 3108 Review

Agents

Agents include humans,robots, softbots, thermostats, etc.

The agent function maps from percept histories(sequences) to actions $P->A$

agent program runs on the physical architecture to produce f. (prescode)

• Percepts :sensor reading
• Actions : output
• Goals : performance measure ( to achieve the goal )
• Environment : external world

Rational agent: For each possible percept sequence, a rational agent should choose an action
that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge (environment) (capabilities(actions)) it has

Basic types of agents in order of increasing generality:

Simple reflex agents

Agents with condition-action rules

Model based Reflex agents with state

Simple agents that maintain some sort of internal state(arg: state,action,percept,model) of the world (and a model) in order to choose an action.

Model-based, Goal-based agents

Knowing about the current state of the environment is not always enough to decide what to do.The agent need a GOAL describing the desirable situations.

Model-based, Utility-based agents

Goals alone are not really enough to generate high-quality behavior. (eg: quicker? safer? cheaper?) }We
can only achieve some utilities, or have a compromise action.

Learning Agents

The learning element responsible for making improvements to the performance element.

The performance element = previously entire agent: it takes in percepts and decides on actions.

The critic tells the learning element how well the agent is doing w.r.t. a fixed standard of performance. Necessary because the percepts themselves provide no indication of agent’s success.

The problem generator - responsible for suggesting problems & actions for new and informative experiences.

Problem-solving agents

1. Goal Formation
2. Problem formulation: to decide what actions and states to consider
3. Search
4. Execution

4 problem types

single-state problems

deterministic, fully observable: consider a single state at a time

Multiple state problems

non-observable: reason about sets of states that it might get to.

Contingency（偶然性） problems

nondeterministic and/or partially observable: calculates a whole tree of actions rather than a single action sequence

Exploration problems

unknown state space: agent must experiment, discovering the actions and states.

state space : The set of all states reachable from the initial state by any sequence of actions

Tree Search alg

Basic idea:

Current state - generate a new set of states (expanding the state) - choose one (expanding state) by a search strategy to expand - search tree with search nodes

Evaluation methods

• completeness. Always find a solution if exists?
• time complexity: number of nodes
• space complexity: maximum number of nodes in memory
• optimality: always find a least-cost solution?

BFS

• FIFO queue
• complete
• time and space: O($b^{d+1}$) b: branching factor, d:depth of optimal solution
• optimal(if cost = 1 per step)

Uniform cost search

• expand the lowerst-cost node rather than lowest-depth node.
• complete
• time: number of nodes with g <= cost of optimal solution. g: path cost
• space: number of nodes with g <= cost of optimal solution
• optimal

DFS

• LIFO queue
• not complete, fail in infinite depth spaces
• O($b^m$) m: max depth of search tree, b: branching factor
• space: O(bm)
• optimal if cost same per step

Depth limited search

depth first search with depth limit L

Iterative deepening search

iterate limit L from 0 to infinite

• complete
• time: O($b^d$)
• space: O(bd)
• optimal if cost same per step

Best first search

Nodes are ordered so that the best evaluation is expanded first.

Greedy search

• Evaluation function = estimation of cost from node n to the closest goal, h(n)
• h can be any function as long as h(n) = 0 when n = goal such as 直线距离
• greedy search: best first search that uses h to select the next node to expand
• not complete(stuck in loop)
• time, space: O($b^m$), m: max depth of search tree ( keep all node in memory )
• not optimal

A search

• evaluation function f = g(n) + h(n) g:cost so far to reach n
• 0<=h(n)<= true cost from n to goal
• complete, unless inifinity nodes with f<= f(Goal)
• time, exponential in [error in h * length of solution]
• space. keep all nodes
• optimal
• no other optimal alg is is guaranteed to expand fewer nodes than A (没expand all f 小于goal的 node， 就有可能miss optimal solution)

Dominance

if h2 > h1 for all n, then h2 dominates h1 and is better

$N = 1 + b^1 + b^2 + … + b^d $

N:total number of expanded nodes, b: effective branching factor d: solution depth. use b to determine the h’s overall usefulness.

Recursive Best First Search RBFS

			1.Deterministic2.Stochastic

Single point Hill-climbing Simulator A

Multiple poi Multi-start GA

Mul: Send whole class to search

Hill climbing

如果邻居最大值 < current -> return

else current = 邻居最大值

problem: stuck on local max

Simulated annealing

• escape local max by allowing some “ bad “ moves ( next = randomly selected) but gradually decrease their size and frequency
• if next = better, always excuted
• $p = e^{\Delta E/T}$

Genetic algorithms

选择初始生命种群(initial population)

​ 评价种群中的个体适应度(fitness function)

​ 以比例原则（分数高的挑中机率也较高）选择产生下一个种群。不仅仅挑分数最高的的原因是这么做可能收敛到局部的最佳点，而非整体的。

​ 改变该种群（交叉和变异）(crossover mutation)

直到停止循环的条件满足

Game play

Minimax

• complete if tree is finite
• optimal if opponent is optimal
• time ：$O(b^m)$
• space: O(bm) depth first

Resource limits: cutoff test: depth limit ; evaluation function:= estimated desirability of position

Evaluation function

• agree with the utility function on terminal states
• not too long
• accurately reflect the actual chances of winning

Qui’escence search

Expand non-quiescent(静) positions until quiescent positions are reached.

Alpha-Beta pruning

compute the correct minimax decision without looking at every node in the search tree.

perfect order: time = $O(b^{m/2})$

Logic

Syntax defines the sentences in the language

Semantics define the meaning of sentences

m is a model of a sentence s if s in true in m

M(s) = set of all models of s

KB entails s iff M(KB) belongs to M(s)

• Soundness: i is sound if whenever KB entails(i) s, then KB entails s
• Completeness: i is complete if whenever KB entails s, then Kb entails(i) s. Derivations can produce all entailed sentences

Valid: true in all models

Satisfiable: true in some models

Unsatisfiable: true in no models

Horn Form

conjunction of Horn clauses

Horn clauses

proposition symbol || conjucton of symbols -> symbol

Backward chaining

1.check if q is known already

2.prove by BC all premises of some rules concluding q

• Forward chaining
  • data-driven
  • may do lots of works that is irrelevant to the goal
• Backward chaining
  • goal-driven
  • complexity of BC can be much less than linear in size of KB

Resolution

CNF-universal

conjunction of “disjunctions of literals”

• $ a\leftrightarrow b\Rightarrow(a\rightarrow b) \wedge(b\rightarrow a)$
• $a\rightarrow b\Rightarrow \neg a \vee b$
• $ \neg( a \vee b)\Rightarrow \neg a \wedge \neg b$
• $(a \wedge b) \vee c \Rightarrow (a \vee c) \wedge ( b \vee c)$

Resolution inference rule

sound and complete

To proof Kb entails a , by contradiction, show that Kb and not a unsatisfiable

First Order Logic

• Terms: Function(Term,…) | constant | variable
• atomic sentences: a predicate symbol followed by a parenthesized list of terms.(also an equality)
• complex sentences: logical connectives (and or)
• Quantifier, for all, exist one

well formed formula/wff: for sentences that have all their variables properly introduced.

FOL: one can quantify over objects but not over relations or functions on these object

Higher order logic : quantify over relations and functions

$(\lambda x,y\ x^2-y^2)(25,24) = 25^2 - 24^2 = 49$

E! = unique

Universal instantiation / Existential instantiation

UI can be applied several times to add new sentences, the new KB is logically equivalent

to the old

EI can be applied once to replace the existential sentence, the new KB is not equivalent to the old.

Unification

UNIFY(p,q) = theta where SUBST(theta,p) = SUBST(theta, q)

Backward channing and FC

• BWC
  • space is linear in size of proof
  • incomplete due to infinite loops(checking current goal against every goal on stack)
  • inefficient due to repeated sub goals ( caching previous results)
• FWC
  • sound and complete
  • may not terminate in general if alpha is not entailed
  • entailment with definite clauses is semi-decidable

Learning From Examples

Decision Tree not a good way to represent the function because the truth table is exponentially large in the number of attributes

• If there are no examples left, it means that no such example has been observed, and we return the majority classification of the node’s parent.
• If there are no attributes left, but both +ve and -ve examples, which means that these examples have exactly the same description, but different classifications. This happens when
  • noise
  • not fully describe
  • the domain is non-deterministic

**Ockham’s razor.**The most likely hypothesis is the simplest one that is consistent with all observations.

Information content I

$I(P(v_1),…,P(v_n)) = \sum-P(v_i)log_2P(v_i)$

P is smaller, then -log P is bigger

$Gain(A) = I(p/(p+n), n/(n+p)) - Reminder(A)$

$Reminder(A) = \sum\frac{p_i+n_i}{p+n}I(p_i/{p_i+n_i},n_i/p_i+n_i)$

We select features with largest Gain.

• Fasle negative: the hypothesis must generalization: C2(x) implies C1(x). C2 is to be generalized
• Dropping conditions || add OR conditions
• False positive: specialization. special = contradiction

Sample Size: $m >= 1/e ( ln 1/o + ln|H|)$

e = max error o = error’s probablity H= number of possible hypothesis