# Natural Language Processing Lecture02

## 图搜索算法

### Depth-first search (DFS)

• Time Complexity
• Some left prefix of the tree
• If m is finite, takes time O(bm)
• Space Complexity
• Only has siblings on path to root, so O(bm)
• Completion
• No, can be infinite
• Optimal
• It finds the "leftmost" solution, regardless of depth of cost
• BFS outperform BFS
• The tree is deep and the answer is deep and frequent
• It has advantages according to computing complexity

• Time Complexity
• Processes all nodes above shallowest solution
• Let depth of shallowest solution be s
• Search takes time O(bs)
• Space Complexity
• Has roughly the last tier, so O(bs)
• Completion
• Yes
• Optimal
• Yes

• BFS outperform DFS
• The branch factor is relatively small
• The depth of the optimal solution is relatively shallow
• The required optimal condition of BFS
• all costs between two nodes are positive or zero
• sort the list used to maintain the searching history in every iteration

Similar to BFS under the optimal conditions.

Differences :

• It sorts the list by the sum of the cost for initial node to current node and the estimated cost from current node to the goal.

$total = cost(s,c) + estimated_cost(c,g)$

• In every iteration, it check all path and prune some paths that will never be the optimal results.

## 机器学习

### 介绍

Tom Mitchell, 1996: Machine learning is the study of how to make programs improve their performance on certain tasks from (own) experience.

• performance = speed, accuracy
• experience = earlier observation = data

Conclusion: use data to learn a model that has good performance on unseen data.

### 最优化（梯度下降）

1. 定义目标函数为：

$y = k*rm + b$

2. 均方差为：

$loss = \frac{1}{n} \sum{(y_i - \hat{y_i})}^2$

$loss = \frac{1}{n} \sum{(y_i - (kx_i + b_i))}^2$

3. 偏微分为：

$\frac{\partial{loss}}{\partial{k}} = -\frac{2}{n}\sum(y_i - \hat{y_i})x_i$

$\frac{\partial{loss}}{\partial{b}} = -\frac{2}{n}\sum(y_i - \hat{y_i})$

# NLP