鸡尾酒会问题—语音分离

在斯坦福大学的Coursera的Andrew Ng的机器学习介绍性讲座中,他给出了以下一行Octave解决方案的鸡尾酒会问题,因为音频源由两个空间分离的麦克风记录:

[W,s,v]=svd((repmat(sum(x.*x,1),size(x,1),1).*x)*x’);

  • 传统方法

独立成分分析ICA

独立分量分析(Independent Component Analysis,ICA)是将信号之间的独立性作为分离变量判据的方法。由Comon于1994年首次提出。Comon指出ICA方法可以通过某个对比函数(Contrast Function)的目标函数达到极大值来消除观察信号中的高阶统计关联,实现盲源分离。盲源分离被描述成在不知道传输通道特性的情况下,从传感器或传感器阵列中分离或估计原始源波形的问题。然而,对于某些模型,不能保证估计或提取的信号与源信号具有完全相同的波形,因此有时要求放宽到提取的波形是源信号的失真或滤波版本。

独立成分分析(Independent Component Analysis),最早应用于盲源信号分离(Blind Source Separation,BBS)。起源于“鸡尾酒会问题”,描述如下:在嘈杂的鸡尾酒会上,许多人在同时交谈,可能还有背景音乐,但人耳却能准确而清晰的听到对方的话语。这种可以从混合声音中选择自己感兴趣的声音而忽略其他声音的现象称为“鸡尾酒会效应”。
  独立成分分析是从盲源分离技术发展而来的一种数据驱动的信号处理方法, 是基于高阶统计特性的分析方法。它利用统计原理进行计算,通过线性变换把数据或信号分离成统计独立的非高斯的信号源的线性组合。
  主成分分析(PCA)是一种数据降维的方法,它与主成分分析有一些区别.

ICA的python实现

应用Python机器学习库SKlearn中的FastICA来演示信号分离并与PCA进行对比。

#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
from scipy import signal
from sklearn.decomposition import FastICA, PCA
# 生成观测模拟数据
np.random.seed(0)
n_samples = 2000
time = np.linspace(0, 8, n_samples)
s1 = np.sin(2 * time)  # 信号源 1 : 正弦信号
s2 = np.sign(np.sin(3 * time))  # 信号源 2 : 方形信号
s3 = signal.sawtooth(2 * np.pi * time)  # 信号源 3: 锯齿波信号
S = np.c_[s1, s2, s3]
S += 0.2 * np.random.normal(size=S.shape)  # 增加噪音数据
S /= S.std(axis=0)  # 标准化

# 混合数据
A = np.array([[1, 1, 1], [0.5, 2, 1.0], [1.5, 1.0, 2.0]])  # 混合矩阵
X = np.dot(S, A.T)  # 生成观测信号源

# ICA模型
ica = FastICA(n_components=3)
S_ = ica.fit_transform(X)  # 重构信号
A_ = ica.mixing_  # 获得估计混合后的矩阵

# PCA模型
pca = PCA(n_components=3)
H = pca.fit_transform(X)  # 基于PCA的成分正交重构信号源

# 图形展示
plt.figure()
models = [X, S, S_, H]
names = ['Observations (mixed signal)',
         'True Sources',
         'ICA recovered signals',
         'PCA recovered signals']
colors = ['red', 'steelblue', 'orange']
for ii, (model, name) in enumerate(zip(models, names), 1):
    plt.subplot(4, 1, ii)
    plt.title(name)
    for sig, color in zip(model.T, colors):
        plt.plot(sig, color=color)
plt.subplots_adjust(0, 0.1, 1.2, 1.5, 0.26, 0.46)
plt.show()

from sklearn.decomposition import FastICA
ica = FastICA(n_components=None, algorithm=’parallel’, whiten=True, fun=’logcosh’, fun_args=None, max_iter=200, w_init=None)

以上是 FastICA 模型通常所含的参数及其对应的默认值。 n_components: 指定使用元素的数目。 algorithm: {‘parallel’,’deflational’},指定 FastICA 使用哪种算法。 writen: True/False,是否进行白化处理。 fun: {‘logcosh’,’exp’,’cube’,..},选择一种近似于计算负熵的目标函数,可自己定义函数。 fun_args: 指定目标函数所要用的参数。 max_iter: 指定拟合过程中最大的迭代次数。 w_init: 指定初始的混合矩阵。

​ 1. 主成分分析假设源信号间彼此非相关,独立成分分析假设源信号间彼此独立。

​ 2. 主成分分析认为主元之间彼此正交,样本呈高斯分布;独立成分分析则不要求样本呈高斯分布。

稀疏主成分分析Spars PCA

稀疏主成分分析即是为了解决这个问题而引进的一个算法。它会把主成分系数(构成主成分时每个变量前面的系数)变的稀疏,也即是把大多数系数都变成零,通过这样一种方式,我们就可以把主成分的主要的部分凸现出来,这样主成分就会变得较为容易解释。

实现主成分分析稀疏化,最终会转化为优化问题, 也即对本来的主成分分析(PCA)中的问题增加一个惩罚函数。 这个惩罚函数包含有稀疏度的信息。当然,最终得到的问题是NP-困难问题,为了解决它,我们就需要采用一些方法逼近这个问题的解。这也是不同稀疏主成分分析算法不同的由来。

非负矩阵分解NMF

NMF的基本思想可以简单描述为:对于任意给定的一个非负矩阵V,NMF算法能够寻找到一个非负矩阵W和一个非负矩阵H,使得满足 ,从而将一个非负的矩阵分解为左右两个非负矩阵的乘积。如下图所示,其中要求分解后的矩阵H和W都必须是非负矩阵。

参考:

https://zhuanlan.zhihu.com/p/142143151

https://github.com/jake-g/dsp-fpga-labs/blob/c0c84ed08c02da11fb4161599cafe8ddcabeaca4/Labs/sound_split_demo/seperate.m

https://www.cxymm.net/article/weixin_30446557/115847250

https://leoncuhk.gitbooks.io/feature-engineering/content/feature-extracting04.html

ICA独立成分分析

ICA的数学推导

ICA算法的思路比较简单,但是推导过程比较复杂,本文只是梳理了推理路线。

假设我们有n个混合信号源\(X\subset{R^{n}}\)和n个独立信号\(S\subset{R^{n}}\),且每个混合信号可以由n个独立信号的线性组合产生,即:\(X=\left[ \begin{matrix} x_1&\\ x_2&\\ …&\\ x_n& \end{matrix} \right]S=\left[ \begin{matrix} s_1&\\ s_2&\\ …&\\ s_n& \end{matrix} \right]X=AS => S=WX,W=A^{-1}\)

假设我们现在对于每个混合信号,可以取得m个样本,则有如下n*m的样本矩阵:\(D=\left[ \begin{matrix} d_{11}&d_{12}&…&d_{1m}&\\ …&\\ d_{n1}&d_{n2}&…&d_{nm}\\ \end{matrix} \right]\)

由于S中的n个独立信号是相互独立的,则它们的联合概率密度为:$$p_S(s)=\Pi_{i=1}^{n}p_{s_i}(s_i)$$

由于\(s=Wx\),因此我们可以得出:\(p_X(x)=F^{‘}_{X}(x)=|\frac{\partial{s}}{\partial{x}}|*p_S(s(x))=|W|*\Pi_{i=1}^{n}p_{s_i}(w_ix)\)

考虑目前有m个样本,则可以得到所有样本的似然函数:\(L=\Pi_{i=1}^{m}(|W|*\Pi_{j=1}^{n}p_{s_j}(w_{j\cdot}d_{\cdot{i}}))\)

取对数之后,得到:\(lnL=\Sigma_{i=1}^{m}\Sigma_{j=1}^{n}lnp_{s_j}(w_{j\cdot}d_{\cdot{i}})+mln|W|\)

之后只要通过梯度下降法对lnL求出最大值即可,即求使得该样本出现概率最大的参数W。
此时假设我们上面的各个独立信号的概率分布函数sigmoid函数,但是不确定这里的g函数和下面fastICA中的g函数是否有关联):\(F_{s_i}(s_i)=\frac{1}{1+e^{-s_i}}\)

最终,我们求得:\(\frac{\partial{lnL}}{\partial{W}}=Z^TD+\frac{m}{|W|}(W^*)^T\)

其中:$$Z=g(K)=\left[ \begin{matrix} g(k_{11})&g(k_{12})&…&g(k_{1m})&\\ …&\\ g(k_{n1})&g(k_{n2})&…&g(k_{nm})\\ \end{matrix} \right]g(x)=\frac{1-e^x}{1+e^x}K=WDD=\left[ \begin{matrix} d_{11}&d_{12}&…&d_{1m}&\\ …&\\ d_{n1}&d_{n2}&…&d_{nm}\\ \end{matrix} \right]$$

由于伴随矩阵具有以下性质:$$WW^*=|W|I$$

因此我们可以求出:\(\frac{\partial{lnL}}{\partial{W}}=Z^TD+m(W^{-1})^T\)

因此可以得到梯度下降更新公式:$$W=W+\alpha(Z^TD+m(W^{-1})^T)$$

至此,ICA的基本推理就此结束。下面我们来看一下fastICA的算法过程(没有数学推理)。

fastICA的算法步骤

观测信号构成一个混合矩阵,通过数学算法进行对混合矩阵A的逆进行近似求解分为三个步骤:

  • 去均值。去均值也就是中心化,实质是使信号X均值是零。
  • 白化。白化就是去相关性。
  • 构建正交系统。

在常用的ICA算法基础上已经有了一些改进,形成了fastICA算法。fastICA实际上是一种寻找\(w^Tz(Y=w^Tz)\)的非高斯最大的不动点迭代方案。具体步骤如下:

  1. 观测数据的中心化(去均值)
  2. 数据白化(去相关),得到z
  3. 选择需要顾及的独立源的个数n
  4. 随机选择初始权重W(非奇异矩阵)
  5. 选择非线性函数g
  6. 迭代更新:
    • \(w_i \leftarrow E\{zg(w_i^Tz)\}-E\{g^{‘}(w_i^Tz)\}w\)
    • \(W \leftarrow (WW^T)^{-1/2}W\)
  7. 判断收敛,是下一步,否则返回步骤6
  8. 返回近似混合矩阵的逆矩阵

代码实现
基于python2.7,matplotlib,numpy实现ICA,主要参考sklean的FastICA实现。

import math
import random
import matplotlib.pyplot as plt
from numpy import *

n_components = 2

def f1(x, period = 4):
return 0.5(x-math.floor(x/period)period)

def create_data():
#data number
n = 500
#data time
T = [0.1*xi for xi in range(0, n)]
#source
S = array([[sin(xi) for xi in T], [f1(xi) for xi in T]], float32)
#mix matrix
A = array([[0.8, 0.2], [-0.3, -0.7]], float32)
return T, S, dot(A, S)

def whiten(X):
#zero mean
X_mean = X.mean(axis=-1)
X -= X_mean[:, newaxis]
#whiten
A = dot(X, X.transpose())
D , E = linalg.eig(A)
D2 = linalg.inv(array([[D[0], 0.0], [0.0, D[1]]], float32))
D2[0,0] = sqrt(D2[0,0]); D2[1,1] = sqrt(D2[1,1])
V = dot(D2, E.transpose())
return dot(V, X), V

def _logcosh(x, fun_args=None, alpha = 1):
gx = tanh(alpha * x, x); g_x = gx ** 2; g_x -= 1.; g_x *= -alpha
return gx, g_x.mean(axis=-1)

def do_decorrelation(W):
#black magic
s, u = linalg.eigh(dot(W, W.T))
return dot(dot(u * (1. / sqrt(s)), u.T), W)

def do_fastica(X):
n, m = X.shape; p = float(m); g = _logcosh
#black magic
X *= sqrt(X.shape[1])
#create w
W = ones((n,n), float32)
for i in range(n):
for j in range(i):
W[i,j] = random.random()

#compute W
maxIter = 200
for ii in range(maxIter):
    gwtx, g_wtx = g(dot(W, X))
    W1 = do_decorrelation(dot(gwtx, X.T) / p - g_wtx[:, newaxis] * W)
    lim = max( abs(abs(diag(dot(W1, W.T))) - 1) )
    W = W1
    if lim < 0.0001:
        break
return W

def show_data(T, S):
plt.plot(T, [S[0,i] for i in range(S.shape[1])], marker=”*”)
plt.plot(T, [S[1,i] for i in range(S.shape[1])], marker=”o”)
plt.show()

def main():
T, S, D = create_data()
Dwhiten, K = whiten(D)
W = do_fastica(Dwhiten)
#Sr: reconstructed source
Sr = dot(dot(W, K), D)
show_data(T, D)
show_data(T, S)
show_data(T, Sr)

if name == “main“:
main()

参考:

http://skyhigh233.com/blog/2017/04/01/ica-math/

PCA

降维——PCA

降维就是一种对高维度特征数据预处理方法。降维是将高维度的数据保留下最重要的一些特征,去除噪声和不重要的特征,从而实现提升数据处理速度的目的。在实际的生产和应用中,降维在一定的信息损失范围内,可以为我们节省大量的时间和成本。降维也成为应用非常广泛的数据预处理方法。

降维具有如下一些优点:

  • 使得数据集更易使用。
  • 降低算法的计算开销。
  • 去除噪声。
  • 使得结果容易理解。

降维的算法有很多,比如奇异值分解(SVD)、主成分分析(PCA)、因子分析(FA)、独立成分分析(ICA)。

PCA(Principal Component Analysis),即主成分分析方法,是一种使用最广泛的数据降维算法。PCA的主要思想是将n维特征映射到k维上,这k维是全新的正交特征也被称为主成分,是在原有n维特征的基础上重新构造出来的k维特征。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴,新的坐标轴的选择与数据本身是密切相关的。其中,第一个新坐标轴选择是原始数据中方差最大的方向,第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的,第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推,可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴,我们发现,大部分方差都包含在前面k个坐标轴中,后面的坐标轴所含的方差几乎为0。于是,我们可以忽略余下的坐标轴,只保留前面k个含有绝大部分方差的坐标轴。事实上,这相当于只保留包含绝大部分方差的维度特征,而忽略包含方差几乎为0的特征维度,实现对数据特征的降维处理。

我们如何得到这些包含最大差异性的主成分方向呢?

事实上,通过计算数据矩阵的协方差矩阵,然后得到协方差矩阵的特征值特征向量,选择特征值最大(即方差最大)的k个特征所对应的特征向量组成的矩阵。这样就可以将数据矩阵转换到新的空间当中,实现数据特征的降维。

基于特征值分解协方差矩阵实现PCA算法

输入:数据集 [公式] ,需要降到k维。

1) 去平均值(即去中心化),即每一位特征减去各自的平均值。

2) 计算协方差矩阵 [公式],注:这里除或不除样本数量n或n-1,其实对求出的特征向量没有影响。

3) 用特征值分解方法求协方差矩阵[公式] 的特征值与特征向量。

4) 对特征值从大到小排序,选择其中最大的k个。然后将其对应的k个特征向量分别作为行向量组成特征向量矩阵P。

5) 将数据转换到k个特征向量构建的新空间中,即Y=PX。

 PCA实例

(1)PCA的Python实现:

##Python实现PCA
import numpy as np
def pca(X,k):#k is the components you want
  #mean of each feature
  n_samples, n_features = X.shape
  mean=np.array([np.mean(X[:,i]) for i in range(n_features)])
  #normalization
  norm_X=X-mean
  #scatter matrix
  scatter_matrix=np.dot(np.transpose(norm_X),norm_X)
  #Calculate the eigenvectors and eigenvalues
  eig_val, eig_vec = np.linalg.eig(scatter_matrix)
  eig_pairs = [(np.abs(eig_val[i]), eig_vec[:,i]) for i in range(n_features)]
  # sort eig_vec based on eig_val from highest to lowest
  eig_pairs.sort(reverse=True)
  # select the top k eig_vec
  feature=np.array([ele[1] for ele in eig_pairs[:k]])
  #get new data
  data=np.dot(norm_X,np.transpose(feature))
  return data

X = np.array([[-1, 1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

print(pca(X,1))

用sklearn的PCA与我们的PCA做个比较:

##用sklearn的PCA
from sklearn.decomposition import PCA
import numpy as np
X = np.array([[-1, 1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca=PCA(n_components=1)
pca.fit(X)
print(pca.transform(X))