CS224n Assignment1

Pre Import

# All Import Statements Defined Here
# Note: Do not add to this list.
# All the dependencies you need, can be installed by running .
# ----------------
import sys
assert sys.version_info[0]==3
assert sys.version_info[1] >= 5
from gensim.models import KeyedVectors
from gensim.test.utils import datapath
import pprint
import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [10, 5]
import nltk
nltk.download('reuters')
from nltk.corpus import reuters
import numpy as np
import random
import scipy as sp
from sklearn.decomposition import TruncatedSVD
from sklearn.decomposition import PCA
START_TOKEN = '<START>'
END_TOKEN = '<END>'
np.random.seed(0)
random.seed(0)
# ----------------

Part1:Count-Based Word Vectors (10 points)(基于计数的词向量 (10分))

读取google 词向量预训练数据的函数

def read_corpus(category="crude"):
    """ Read files from the specified Reuter's category.
        Params:
            category (string): category name
        Return:
            list of lists, with words from each of the processed files
    """
    files = reuters.fileids(category)
    return [[START_TOKEN] + [w.lower() for w in list(reuters.words(f))] + [END_TOKEN] for f in files]

Question 1:Implement distinct_words [code] (2 points)

Write a method to work out the distinct words (word types) that occur in the corpus. You can do this with for loops, but it’s more efficient to do it with Python list comprehensions. In particular, this may be useful to flatten a list of lists. If you’re not familiar with Python list comprehensions in general, here’s more information.

You may find it useful to use Python sets to remove duplicate words.

就是完成 distinct_words函数,找出一个语料库内不重复的词的集合。可以利用python集合类型完成

Read more »

Computer Network——Review From Keywords

https://sakuyui.github.io/2019/04/21/Computer Network——Review From Keywords/ (持续更新)

[TOC]

Keyword

Internet(因特网)

Internet is a global network of all computers that communicative with each other in public languages.It’s a logical network formed by many small subnet.
因特网是由所有使用公用语言相互通信的计算机组成的全球网络,是由许多小的子网组成的逻辑网络。

[extend]
Q1:因特网概念的实质是什么?
全球信息资源的总汇
Q2:计算机设备可以有多个IP地址吗?为什么?什么设备在internet上一定有多个IP地址
可以,插多个网卡爱有几个有几个。路由器
Q3:一个网段可否赋予不止一个 IP 地址?一个接口可否赋予多个 IP 地址?
可以

hosts/end system(主机\终端系统)

hosts is same to end system.It refer to all the devices like computer、cell phone、Web cams which being connected to the internet
主机和终端系统概念相同,是指所有像计算机、手机、网络摄像头之类的连接到互联网的设备

ISP(Internet Service Provider:因特网服务提供商)

Read more »

Computer Networking

[TOC]

Chapter 1 Computer Networks and the Internet

1.1 What Is the Internet

1.1.1 A Nuts-and-Bolts Description

hosts or end systems
Alt text
ISP: Internet Services Provider
transmission rate measured in bits/second(b/s)
Packet switching(包交换/分组交换) is a method of grouping data that is transmitted over a digital network into packets. Packets are made of a header and a payload. Data in the header are used by networking hardware to direct the packet to its destination where the payload is extracted and used by application software.
Packet switches include routers(路由) and link-layer switches(数据链路层的交换机)
TCP(Transmission Control Protocol )
IP(Internet Protocol)

1.1.3 What Is a Protocol?

A protocol defines the format and the order of messages exchanged between two or more communicating entities, as well as the actions taken on the transmission and/or receipt of a message or other event.(协议定义了信息在两个网络实体间交换信息的格式以及一系列操作)

1.2 The Network Edge(网络边缘)

也就是hosts.靠近用户端那部分.也叫端系统

Read more »

Beta分布与最大后验估计(MAP)

Beta分布

  • 二次分布:抛n次硬币出现k次正面的概率
  • 几何分布:抛第t次时,该次为第一次出现正面的概率
  • 帕斯卡分布:抛第t次时,第k次出现正面

可以发现以上可以用一个统一分布来描述

a,b为形状参数
B为归一化函数

理解1

首先抛开B。看看简单的变体$f(x|\alpha,\beta)=x^\alpha(1-x)^\beta$
对于贝叶斯主义者,不应该使用频率主义,要把概率当做随机变量。
如抛出7次正面,3次反面。概率分布是关于X的函数.

$f(x|7,3)=x^7(1-x)^3$
该函数在0.7处取得最大值,说明极有可能正面概率是0.7

几种特殊分布
1.a=b=1时为均匀分布,a=b时

用于贝叶斯推断
在推断中,我们往往在意模型的参数,对于贝叶斯主义来说,这些参数不是一个确定的值,而是服从某个分布。记参数为[随机变量]$\theta$

Read more »

【统计学习】*逐步回归(Step Regression and) 和 分段回归(Stagewise regression)

Enter:所有X一次性全部进入
Forward:X一个一个进,每次进入P-value最小的X,直到未进入的X都不significant
Backward:所有的X先一次性进入,然后一个一个剔除,每次剔除P-value最大的X,直到保留的X全都significant
Stepwise:X一个一个进,但是进入新的X以后,会重新审查所有已进入X的P-value,如果进入新的X导致原来的X的P-value从significant变成不significant,则把原来的X剔除。

QR分解

在ols(最小二乘)中要计算$(X^TX)^{−1}$,可以通过矩阵分解简化计算,将X分解成QR乘积的形式,其中Q是一个$N∗(p+1)$的正交矩阵,也就是X的列空间的一组正交基,R是一个上三角矩阵,于是,$\hatβ=(X^TX)^{−1}X^Ty=R^{−1}Qy,\hat y=QQ^Ty$


子集选择

有两个原因导致我们对最小二乘法(ols)的估计不满意:
1.第一个原因是预测精度(accuracy),最小二乘法估计通常具有低偏差(bias)和高方差(var),我们想要通过使某些系数收缩或者设置为零,牺牲一些偏差来换取方差的减小,这样一来可以提升预测的精度。
2.第二个原因是解释(interpretation),当有大量的自变量的时候,我们希望确定一个表现出最强影响的较小子集。

以下是三种子集选择的方法

最优子集选择(best-subset selection)

最优子集选择,顾名思义,就是便利所有可能的预测子的集合然后在训练集上进行ols确定参数,最后选取在测试集上表现最好的集合作为最优子集。

Read more »

【信息论】Entropy、Relative Entropy,K-L distance

Entropy(熵)

熵表现了信息量的多少,概率越小的样本信息量越大。其是概率对数的期望
log底数为

  • 2:比特 bit
  • e:奈特 nat

为确定X的值所需的二元问题数的最小期望介于H(X)与H(X)+1之间

条件熵(Conditional Entropy)联合熵(Joint Entropy)按照概率论方式算即可
不过因为这里是对数
所以概率中联合分布和条件分布的式子要改一改

KL散度

KL散度也叫互信息或者鉴别信息。是描述两个随机分布之间的距离的度量

其是两个随机变量相除的对数的期望

互信息

Read more »

【信息论】AEP(渐进均分性)&随机过程熵率&数据压缩

AEP

证明很简单。就是X_i与X_j是相互独立的,然后就可以把联合分布展开出来,就变成均值公式了,依概率后就是期望了

典型集

是序列$(x_1,x_2,…,x_n)\in \mathscr{X}$的集合

典型集的概率近似为1

典型集的大小为$2^{n(H+\epsilon)}$
于是典型序列需要${n(H+\epsilon)}+2\approx nH$bit来描述(每个变量都约需要H来描述,个数为n的序列就是nH)
加2是因为
1.为了防止非整数长度,加了个1
2.为了表示是典型集,加一个标志位

最小概率集

最小概率集

随机过程熵率

Read more »

【统计学习】Shrinkage Method

岭回归(Ridge Regression)

岭回归(英文名:ridge regression, Tikhonov regularization)是一种专用于共线性数据分析的有偏估计回归方法,实质上是一种改良的最小二乘估计法,通过放弃最小二乘法的无偏性,以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法,对病态数据的拟合要强于最小二乘法。

理论

岭回归在最小二乘法的基础上加上了一个L2惩罚项(正则化项。也就是使用了L2正则化)(关于L2正则化可以看另一篇文章)
Loss Function:

Read more »

【统计学习】SVM(支持向量机)

1 简介

支持向量积是通过在二维空间确定一条直线,或者在三维空间确定一个平面或者在高维空间确定一个超平面,使确定的直线\平面\超平面到两类数据的距离最大的分类方式。其只适用于二分类。

Alt text
可以这么理解。旁边的2类数据点是两个村庄。现在我们要在中间修一条路,把两个村庄隔开。这条路越宽越好。

支持向量积在处理分类问题时有3种解决方案。

  • 线性可分——使用硬间隔
  • 近似线性科峰——使用软间隔
  • 线性不可分——使用核技巧

2 线性可分——使用硬间隔

Alt text

我们希望确定一条直线将两类区分开来。
首先我们需要有个直线的表达式

这个表达式既可以表示直线也可以表示平面也可以表示超平面 之后,想之前说的。我们希望直线离两类的间隔尽可能大。 直线到两类的距离是相等的,于是我们可以 $$ \begin{cases} W^Tx+b<-1 ,& \text{负类}\\ w^tx+b>1,& \text{正类} \end{cases}\tag{2.1.2} $$ 至于为什么是-1和1.只是为了方便。如果是2和-2也可以。不过两边同除2就变成 $0.5W^Tx+0.5b=±1$,又变成1了.对后面优化的优化没有影响。所以为了方便。直接取1. 下面。需要求个间隔,这个间隔很好求,根据平行直线的距离公式即可 $$margin=\rho=\frac{2}{||W||} \tag{2.1.3}$$ $||W||$相当于$\sqrt{w_1^2+w_2^2+...}$ 于是现在我们得到一个优化问题 $$\max_{W,b} \rho=\max_{W,b} \rho^2=\min_{W,b}\frac{1}{2}||W||^2\tag{2.1.4}$$ 也就是在求1/2||W||最小下W,b的值 然后还有个约束条件 $$ \begin{cases} W^Tx_i+b\le -1 ,& \text{y_i=-1}\\ W^Tx_i+b\ge 1,& \text{y_i=+1} \end{cases}\tag{2.1.5} $$ 这个约束表示,对于所有输入数据$x_i$都是能分类的(y=±1),也就是我们现在要修一条最宽的路把两个地区分开,输入一个点,不能让他在这路上。 当然这个约束条件还可以再简洁点,观察可以很容易发现可以写成 $$y_i(W^Tx_u+b)\ge 1 \tag{2.1.6}$$ 现在我们已经得到了一个带约束的优化问题,经过优化后就可以得到$\hat W和\hat b$ 具体如何优化。见第2.1
Read more »

【统计学习】Principle Component Regression(主成分回归)&Partial Least Squares Regression(偏最小二乘回归)

1.简介&PCA

除了对全部特征进行筛选和压缩——这些都是针对原特征本身,那么是否可以把多个特征组合成少数的几个新特征,使模型更加简洁?特别是多个特征之间往往还存在多重共线性关系。两种方法都将新的预测变量(称为组件(Components))构建为原始预测变量的线性组合,但它们以不同的方式构造这些组件。

PCA(主成分分析)的核心是降维,把高维空间上的多个特征组合成少数几个无关的主成分.

举个例子,在二维平面中,如果大部分的点都在一条直线附近,那么可以直接用这条直线当作一维坐标轴来反映原始数据?
在三维空间中,如果大部分的点都在一个平面附近,就可以直接用这个平面当作二维平面来反映原始数据

第一主成分是高维空间上的一个向量,所有的点沿着这条线波动最大,或者说所有的点到直线的距离的平方和最小。如下图所示,所有的点沿着绿色直线的波动最大,它就代表着第一主成分向量。Alt text

有了第一主成分,还可以依次往后选择主成分,各主成分之间是相互正交的向量。如下左图所示,右图是左图的旋转,以第一主成分作为x轴,第二主成分作为y轴与之垂直。
Alt text

我们定义主成分是原特征的线性组合,即:

找到一组Φ(其平方和为1),使Z1的方差最大,它的优化问题变成:
Alt text
第一主成分确定之后,如果是二维空间那么第二主成分就可以通过正交关系直接确定;对于高维空间,一个向量的正交向量可以有无数个,则在其正交向量中继续优化上式至最大值;之后的主成分依次类推。

Principle Components Analysis(PCA)

Read more »