C++11 Lambda: Capturing Member Variables

发表于 2019-04-17

C++11 Lambda : Capturing Member Variables

本文将介绍如下从外部域捕获成员变量，假设有一个OddCounter类，在其成员函数中使用lambda函数，并需要捕获成员变量：

class OddCounter
{
	// tracks the count of odd numbers encountered
	int mCounter = 0;
public:
	int getCount()
	{
		return mCounter;
	}
	void update(std::vector<int> & vec)
	{
		// Capturing member variable by value will not work
                // Will result in Compile Error
		std::for_each(vec.begin(), vec.end(), [mCounter](int element){
			if(element % 2)
				mCounter++; // Accessing member variable from outer scope
		});
	}
};

这种做法无论是将成员变量传值还是传引用都会出现编译错误。

Capturing Member variables inside Lambda Function

理想的做法是传递this指针的值，这样就可以访问外部成员变量了。

1
2
3

std::for_each(vec.begin(), vec.end(), [this](int element){
//....
}

C++11 Lambda : Capturing local variables

发表于 2019-04-16

C++11 Lambda : How to capture local variables inside Lambda ?

本文将介绍如何在lambda中从外部域捕获变量，同样的，我们可以以值传递或引用传递的方式捕获变量，以下是语法：

1	[Captured variables](paameters) { function code }

Capturing Local Variables by value inside Lambda Function

以下是以值传递捕获变量的方式：

// Local Variables
std::string msg = "Hello";
int counter = 10;
 
// Defining Lambda function and
// Capturing Local variables by Value
auto func = [msg, counter] () {
                          //...
                          };

msg和counter都是const变量，只读不改。要想修改，可以加入关键字mutable：

1	auto func = [msg, counter] () mutable { };

Capturing Local Variables by Reference inside Lambda

要实现引用传递，只需要加上前缀&即可。

// Local Variables
std::string msg = "Hello";
int counter = 10;
 
// Defining Lambda function and
// Capturing Local variables by Reference
auto func = [&msg, &counter] () {
                       //...
                       };

这样在lambda中就可以通过修改该引用从而修改外部值。

Capture All Local Variables from outer scope by Value

正如前面的文章提到过的，我们也可以把外部变量全部捕获，或值传递或引用传递，甚至可以混合使用：

// Capturing all Local variables by Value
auto func = [=] () {
                   //...
                   };

// Capturing all Local variables by Reference
auto func = [&] () {
                   //...
                   };

// Capturing all Local variables by Reference and Value
auto func = [=, &counter] () mutable {};

Be-aware of capturing local variables by Reference in Lambda

如果在lambda中我们通过引用捕获局部变量，那么我们需要确保在访问或调用lambda函数时，所有引用捕获的局部变量仍然在作用域内。

如果该变量已经被回收或者从stack中移除，会导致undefined behavior。

C++11 Lambda Function

发表于 2019-04-15

C++11 Lambda Function

What is a Lambda Function?

lambda函数是C++中的一种匿名函数，通常用作回调使用，像普通的函数那样，也需要传递参数和返回结果。但区别就是，lambda函数没有名字，因此主要用来创建那些短小的函数。

Need of Lambda functions

假设以下使用std::for_each算法的函数：

#include <iostream>
#include <algorithm>
 
void display(int a)
{
    std::cout<<a<<" ";
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
 
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), &display);
 
    std::cout << std::endl;
 
}

在上面的例子中，我们创建了一个单独函数，但使用lambda函数，我们可以避免这种开销。

Rise of Lambda functions

lambda函数是一种匿名函数，它没有任何名称，但您可以传递参数并从中返回结果。如下：

1
2
3

[](int x) {
        std::cout<<x<<" ";
    }

[]用来传递外部域的元素；
(int x)则是传递进来的参数；

利用lambda函数改写：

#include <iostream>
#include <algorithm>
 
int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
 
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), [](int x) {
            std::cout<<x<<" ";
        });
 
    std::cout << std::endl;
 
}

How to pass outer scope elements inside lambda functions

case 1: 使用[=]

1
2
3

[=](int &x) {
    // All outer scope elements has been passed by value
}

case 1: 使用[&]

1
2
3

[&](int &x) {
    // All outer scope elements has been passed by reference
}

Variadic Templates

发表于 2019-04-14

C++11 – Variadic Template Function

Variadic模版允许函数采用任意类型的可变数量参数，考虑这样的一个例子，假设我们创建一个函数log()，它接受任意类型的可变数量参数，并在控制台上打印。

log(1,4.3, "Hello");
 
log('a', "test", 78L, 5);
 
class Student;
Student obj;
 
log(3, obj);

对于可变类型的参数，我们一般考虑的是创建模版函数，如：

template<typename T>
void log(T obj)
{
    std::cout<<obj;
}

但以上做法只能接受一个参数。

Vardiac Template Function: Creating function that accepts variable number of arguments of ant type

使用vardiac template，我们可以定义这样的一个函数，接收不定数量的参数：

1 2	template<typename T, typename ... Args> void log(T first, Args ... args);

上述函数可以接收多个参数，**Args…代表了模版参数的可变数目。

声明一个vardiac template函数是容易的，但其内部具体定义会有点tricky。由于我们无法直接访问到被传递进去的可变数目的参数。我们需要使用c++的类型推导机制和递归来实现。

template<typename T, typename ... Args>
void log(T first, Args ... args) {
 
	// Print the First Element
	std::cout<<first<<" , ";
 
	// Forward the remaining arguments
	log(args ...);
}

现在假设我们通过这种方式调用log函数：

1	log(2, 3.4, "aaa");

居于模版的类型推导，编译器回创建这样的函数：

void log(int first, double b, const char * c)
{
  std::cout<<first<<" , ";
  log(b, c);
}

void log(double first, const char * c)
{
  std::cout<<first<<" , ";
  log(c);
}

void log(const char * first)
{
  std::cout<<first<<" , ";
  log();
}

为了log函数能够在无参数的状态下返回，我们另外定义一个函数：

// Function that accepts no parameter
// It is to break the recursion chain of vardiac template function
void log()
{
}

auto specifier

发表于 2019-04-12

auto specifier

auto这个关键字是由c++11引进的，使用auto，我们可以声明变量而无需指定其类型，其类型由初始化的数据进行推断。

// type int
auto var_1 = 5;
 
// type char
auto var_2 = 'C';
 
std::cout<<var_1<<std::endl;
std::cout<<var_2<<std::endl;

我们也可以记录一些其他的类型，例如函数或者迭代器，以下就是将一个lambda函数存放在auto：

auto fun_sum = [](int a , int b){
					return a+b;
				};
 
std::cout<<fun_sum(4,5)<<std::endl;

auto的最大优点就是，我们不需要书写很长的变量类型：

std::map<std::string, std::string> mapOfStrs;
 
// Insert data in Map
mapOfStrs.insert(std::pair<std::string, std::string>("first", "1") );
mapOfStrs.insert(std::pair<std::string, std::string>("sec", "2") );
mapOfStrs.insert(std::pair<std::string, std::string>("thirs", "3") );

//std::map<std::string, std::string>::iterator it = mapOfStrs.begin();
auto it = mapOfStrs.begin();
while(it != mapOfStrs.end())
{
	std::cout<<it->first<<"::"<<it->second<<std::endl;
	it++;
}

Important points about auto variable in C++11

初始化auto变量后，您可以更改值，但不能更改类型
不能只声明而不进行初始化

Returning an auto from a function

要从函数返回auto变量，我们可以以特殊方式声明它

auto sum(int x, int y) -> int
{
	return x + y;
}

auto value = sum(3, 5);

std::bind

发表于 2019-04-11

std::bind

std::bind是一个标准的函数对象，它就像一个功能适配器，接受一个函数作为输入，并返回一个新函数对象作为输出。另外还附带若干个传递进函数的参数。

假设存在这样一个函数：

int add(int first, int second)
{
	return first + second;
}

bind函数的第一个参数就是函数指针，后面的参数则是该函数的参数：

1	auto add_func = std::bind(&add, _1, _2);

这里add_func是一个函数对象，我们可以这样调用：

1	add_func(4,5);

它将在内部调用add()函数，并在_1的位置传递第一个参数，在_2的位置传递第二个参数。

现在假设我们想在一个特殊场景中使用这个add函数，我们应该将第一个参数始终固定为12，并让第二个参数由用户传递，即：

auto new_add_func = std::bind(&add, 12, _1);

int x = new_add_func(5);
// Will return 17

我们也可以使用std :: bind()重新排列参数，即_1和_2等决定要传递的参数的位：

1
2
3

auto mod_add_func = std::bind(&add, _2, _1);

// mod_add_func(12,15) === add(15, 12).

Use of std::bind in STL algorithms

由于std :: bind充当功能适配器并提供新的函数对象，因此它对于许多STL算法非常有用。

例如，我们有一个数字列表，我们想要计算5的倍数。要实现这一点，我们有一个现有的函数，即:

bool divisible(int num , int den)
{
    if(num % den == 0)
        return true;
    return false;
 
}

一般的算法是遍历判断，但我们可以使用std :: count_if这一个STL算法，即：

count_if (InputIterator firstValue, InputIterator lastValue, UnaryPredicate predFunctionObject);

通过bind函数，我们就可以将divisible转换为一元参数：

int approach_2()
{
    int arr[10] = {1,20,13,4,5,6,10,28,19,15};
    return std::count_if(arr, arr + sizeof(arr)/sizeof(int) , std::bind(&divisible, _1, 5));
 
}

What std::bind returns ?

除了auto，我们也可以使用std:;function Function对象存储它们，即

1	std::function<int (int) > mod_add_funcObj = std::bind(&add, 20, _1);

C++11 ‘delete’ keyword and deleted functions

发表于 2019-04-10

C++11 / C++14 : ‘delete’ keyword and deleted functions

本文将介绍C++11的一个新特性——delete，通过将delete应用到函数来限制其调用：

1	void someFunction() = delete ;

它通常用在以下的地方：

delete编译器生成的函数，如拷贝构造函数、赋值运算符、移动拷贝函数、移动赋值运算符和默认构造函数；
delete成员函数，以避免数据丢失；
delete类的new运算符，以限制堆的对象创建；
delete特定的模版特化；

Deleting Copy Constructor and Assignment Operator

假设存在这样的一个类，拷贝构造函数和赋值运算符都被delete了：

class User
{
 
	int id;
	std::string name;
public:
	User(int userId, std::string userName) : id(userId), name(userName)
	{}
 
	// Copy Constructor is deleted
	User(const User & obj) = delete;
	// Assignment operator is deleted
	User & operator = (const User & obj) = delete;
 
	void display()
	{
		std::cout<<id << " ::: "<<name<<std::endl;
	}
 
};

如果调用这赋值运算符：

1	User obj = userObj;

编译时报错：

delete.cpp:30:10: error: call to deleted constructor of 'User'
    User obj = userObj;
         ^     ~~~~~~~
delete.cpp:15:2: note: 'User' has been explicitly marked deleted here
        User(const User & obj) = delete;
        ^
1 error generated.

Deleting member functions to prevent data loss conversions

由于类型的隐式转换，有可能会在调用函数时传递了错误的参数，例如：

User(int userId, std::string userName) : id(userId), name(userName){}


// 这样调用会被cast
User obj4(5.5, "Riti");
 
User obj5('a', "Riti");

通过利用delete来避免类型转换：

// Deleting a constructor that accepts a double as ID to prevent narrowing conversion
User(double userId, std::string userName) = delete ;
 
// Deleting a constructor that accepts a double as ID to prevent invalid type conversion
User(char userId, std::string userName) = delete ;

报错如下：

elete.cpp:32:10: error: call to deleted constructor of 'User'
    User userObj1(5.5, "John");
         ^        ~~~~~~~~~~~
delete.cpp:14:5: note: 'User' has been explicitly marked deleted here
    User(double userId, std::string userName) = delete ;
    ^
delete.cpp:33:10: error: call to deleted constructor of 'User'
    User userObj2('a', "John");
         ^        ~~~~~~~~~~~
delete.cpp:15:5: note: 'User' has been explicitly marked deleted here
    User(char userId, std::string userName) = delete ;
    ^
2 errors generated.

Restrict Object creation on Heap by deleting new operator for class

我们也可以限制new运算符的使用：

void * operator new (size_t) = delete;

// 调用
User * ptr = new User(1, "Riti");

报错如下：

delete.cpp:34:17: error: call to deleted function 'operator new'
    User *ptr = new User(1, "Rziti");
                ^
delete.cpp:17:12: note: candidate function has been explicitly deleted
    void * operator new (size_t) = delete;
           ^
1 error generated.

Delete specific template specialisation

使用delete关键字，我们可以限制模板类或函数的某些模板特化。

template <typename T>
class ComplexNumber
{
	T x;
	T y;
public:
	ComplexNumber(T a, T b) : x(a) , y(b)
	{}
	void display()
	{
		std::cout<<x << " + i"<<y<<std::endl;
	}
        // Deleted template specialisation 
	ComplexNumber(char a, char b) = delete;
        // Deleted template specialisation  
	ComplexNumber(double a, double b) = delete;
};

原来该模版类可以接收char参数和double参数，通过delete，我们可以限制其特化。

Different between deleted function and private functions

相比private成员函数，delete有两个优点：

避免被其它成员函数调用；
delete函数在name lookup中，如果函数delete了，那么它就不会根据该类型去查找其它匹配函数；

In Search of an Understandable Consensus Algorithm<二>——MIT6.824

发表于 2019-04-08

In Search of an Understandable Consensus Algorithm<二>

Cluster membership changes

上一篇博文中，我们都假设集群配置是固定的。但在实践中往往需要更改配置，可能需要更换服务器或者更改备份配置。为了使配置变更机制更加安全，在过渡期间不存在任意一个时间点会存在两个leader，但任何从旧配置切换到新配置的方法都是不够安全的，在切换期间可能会存在分裂成两个集群，如图：

为了确保安全，配置更改可以使用两阶段的方法。在raft中，集群首先切换到过渡配置，即为joint consensus。一旦commit了joint consensus，系统就会切换到新配置。

日志会被复制到两种配置中的所有服务器；
两种配置中的任何服务器就可以成为leader；
选举等协议需要新旧两种配置的大多数票；

我们使用复制的日志中特殊条目来存储和传送集群配置，下图就是配置更改过程：

当leader收到请求，从Cold配置更改为Cnew时，它会将联合共识即\(C_{old, new}\)存储为日志。如果leader crash了，新的leader会在\(C_{old}\)和\(C_{old, new}\)中选择。

更改配置后还有三个问题需要解决；

新服务器可能一开始不会存储任何日志；raft的解决方法是在更改配置之前引入一个额外的阶段，在该阶段新的服务器以非投票成员的身份加入集群，leader会将日志复制到它们，但不参与投票；
集群leader可能并不属于新配置；在这种情况下，leader在提交了日志\(C_{new}\)之后就会返回到follower阶段；
删除的服务器可能会破坏集群；这些服务器不再接受心跳，因此会超时用新的term发送RequestVote RPC请求选举，并且重复这个过程。为了避免这个问题，服务器会在当前leader存在时，忽略掉RequestVote RPC，不会更新term或者授予票数；

Log compaction

日志会在服务器运行期间无限增长，如果我们不及时丢弃过期的日志，那么对着日志的增长，它会占据更多的内存空间并需要更多时间来重新执行日志。

snapshot是最简单的压缩方法，下图就是raft的快照方式：

每个服务器独立获取快照，快照内容仅仅覆盖了已提交的条目。快照除了包括状态集信息之外，还包含了少量的元数据信息，如上图就包含了最近索引和term。包含了这些信息，可以帮助支持快照后第一个日志条目的AppendEntries一致性检查。

虽然服务器独立生成快照，但一般情况下，如果有一个落后非常多的follower或者新的服务器加入集群，leader会通过InstallSnapshot RPC往其它服务器发送快照。

如果snapshot中包含了follower未包含的日志新内容，该follower会丢弃整个日志，并用snapshot替代。如果接收者收到的snapshot是当前日志的前缀部分，则该快照后面的条目保留，其余删除。

如果是由leader生成snapshot再转发到各个follower，这种做法会浪费网络带宽并降低生成快照的速度。另外还有两个问题会影响性能：

服务器必须决定何时进行快照。一个简单的策略是在日志达到固定大小（以字节为单位）时拍摄快照，此大小设置为远大于快照的预期大小，则用于快照的磁盘带宽开销将很小
写快照可能需要很长时间，我们不希望这会延迟正常操作。解决方案是写时拷贝

Client interaction

本节主要描述raft客户端与raft的交互。

raft将所有的客户端请求发送到leader，如果客户端联系的不是leader，那么服务器会拒绝这一请求，并提供最新的leader地址。

我们对Raft的目标是实现可线性化的语义（即每个操作似乎在其调用和响应之间的某个时刻只执行一次）。但如果leader在提交日志条目之后但在响应客户端之前发生了冲突，则客户端将使用新的leader重试该命令，从而变成了二次执行。解决方案是客户端为每个命令分配唯一的序列号，如果它收到一个序列号已经执行的命令，它会立即响应而不重新执行请求。

只读操作可能会因为leader的重新选举而返回过时的数据，raft需要在不使用日志的情况下确保自己不返回过期的数据，这里采取两个措施：

首先，leader必须拥有关于提交的日志的最新信息。虽然leader拥有所有提交了的日志，但leader不知道这是什么，Raft通过让每个leader在其任期开始时将空白的无操作日志条目输入到日志中来处理此问题。
其次，leader必须在处理只读请求之前检查它是否已被废除；这个可以通过与大多数集群交换心跳来解决；

特征选择与稀疏学习

发表于 2019-04-06

特征选择与稀疏学习

子集搜索与评价

对一个学习任务来说，有些属性很关键，而从给定的特征集合中选择出相关特征子集的过程，就叫"特征选择"(feature selection)。

除了无用特征，还有一类冗余特征，它的信息是从其它特征推断出来的。大部分时候这些特征是不起作用，但有时也会起到中间特征的作用，使得学习更加方便。

提取特征的一个可行做法是先产生一个候选子集，评估好坏，再根据评估结果去产生下一个候选子集，依次迭代。

子集搜索

这第一个环节就是"子集搜索"，给定特征集合\({a_1, a_2, …, a_d}\)。对于前向搜索，对这个d个特征子集进行评价，假设\(\{a_2\}\)最优，接着从剩下的d-1个特征选一个特征，假设此时两特征集合\(\{a_2, a_4\}\)最优，并且由于\(\{a_2\}\)效果更好，则选择\(\{a_2, a_4\}\)。依次进行，直到最优的候选子集不如上一轮选定集合，则停止生成候选子集。而对于后向搜索，则是每次减去一个无关特征。

这种贪心的策略可能会遇到这样一种情况，第三轮选了\(\{a_2,a_4,a_5\}\)，而第四轮却可能是\(\{a_2,a_4,a_6,a_8\}\)更好。这是不可避免的。

子集评价

给定数据集D，假设D中第i类样本所占的比例为\(p_i(i=1,2,..,|y|)\)，另外对于属性子集A，假定根据其取值将D划分为V个子集:\(\{D^1, D^2, ,,., D^V\}\)，每个子集中的样本在属性A上取值相同，则计算属性子集A的信息增益： \[ Gain(A) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v) \\ Ent(D) = - \sum_{k=1}^{|y|} p_k log_2p_k \] Gain(A)越大，意味着特征子集A对数据集D的划分与样本标记信息对于D的真实划分，差异越小，则越有助于分类。

常见的特征选择方法有：过滤式、包裹式、嵌入式

过滤式选择

过滤式方法先对数据集进行特征选择——"过滤"，然后再训练学习器。Relief是一种过滤式特征选择方法，其设计了一个"相关统计量"来度量特征的重要性，该统计量是一个向量，每个分量对应一个初始特征，特征子集的重要性由子集中每个特征所对应的相关统计量分量之和所决定。

Relief的关键是如何确定相关统计量。假设样本为\(\{(x_1,y_1), (x_2, y_2),…, (x_m,y_m)\}\)。对于每个样本\(x_i\)，该算法先在\(x_i\)的同类样本中寻找最近邻\(x_{i,nh}\)，再从异样样本中寻找其最近邻\(x_{i,nm}\)。相关统计量对应属性j的分量为： \[ \delta^j = \sum_i -diff(x_i^j, x_{i,nh}^j)^2 + \sum_{l\neq k}(x_i^j, x_{i,nm}^j)^2 \] 如果属性j为离散型，则\(diff(x_a^j, x_b^j)^2\)的值域为[0, 1]。若是连续型，则是\(|x_a^j-x_b^j|\)。

由上式可以看出，若\(x_i\)与同类样本更近，则属性j对于区分同类与异类的样本是有益的。

上述Relief算法是为二分类问题准备的，其扩展变形Relief-F则能够处理多分类问题： \[ \delta^j = \sum_i -diff(x_i^j, x_{i,nh}^j)^2 + \sum_{l\neq k}(p_l \times (x_i^j, x_{i,nm}^j)^2) \] 其中\(p_l\)为第l类样本在数据集D中所占的比例。

包裹式选择

包裹式特征选择直接把最终将要使用的学习器性能最为特征子集的最终评价标准，因为是为了目的学习器选择特征子集，因此往往比过滤式选择性能更好。

LVW是其中的代表，算法描述为：

输入： 数据集D
			特征集A
			学习算法O
			停止条件控制参数T
过程：
1. E = inf
2. d = |A|
3. A* = A
4. t = O
5. while t < T do
		随机生成特征子集A'
		d' = |A'|
		E' = CrossValidation(O(D^A'))
		if (E'<E) or ((E'=E)and(d'<d)) then
			t = 0
			E = E'
			d = d'
			A* = A'
		else
			t = t+1
		endif
	endwhile
输出A'

由于特征搜索时使用了随机策略，因此每次特征子集评价都需要训练学习器，因此开销很大，我们设置停止条件控制参数。

嵌入式选择与L1正则化

嵌入式特征选择是将特征选择与学习器训练过程融合为一体，给定数据集\(D = \{(x_1,y_1),(x_2, y_2),…,(x_m,y_m)\}\)，考虑简单的线性回归模型，以平方差为损失函数： \[ min_w \sum_{i=1}^m(y_i-w^Tx_i)^2 \] 为了避免过拟合，加入范数正则化： \[ min_w \sum_{i=1}^m(y_i-w^Tx_i)^2 + \lambda||w||^2_2----L_2范数 \\ min_w \sum_{i=1}^m(y_i-w^Tx_i)^2 + \lambda||w||_1----L_1范数 \] L1范数相对于L2范数更容易带来稀疏解，即它求得的w具有更少的非零分量。假设x只有两个属性，同理解w也只有两个分量，因此我们画出等值线：

可以看到的是，由于上面w的解必须要在误差项与正则化项之间折中，因此即有图中的误差项等值线与正则化项等值线相交，采用L1范数时，相交点一般在坐标轴上，则w1或者w2为0。这意味着采用L1范数正则化的结果是得到了对应w的非零分量的特征。

其特征选择过程与学习器训练融为一体，同时完成。

稀疏表示与字典学习

假设数据集D是一个矩阵，行对应每个样本，列则对应特征，特征选择考虑的是如何使得矩阵变得稀疏，即某些特征与学习任务无关，我们可以去掉这些咧从而提高学习速度。

但考虑另一种稀疏性，即D对应的矩阵中存在很多零元素。但样本具有这样的稀疏表达形式时，学习任务会得到许多好处，例如线性支持向量机能使大多数问题变得线性可分，同时也不会带来存储上的负担。

若提供的数据集是稠密的，我们需要学习出一个"字典"，从而使得稠密数据转化为"恰当稀疏"的数据。

给定数据集\({x_1,x_2,…,x_m}\)，字典学习的最简单形式为： \[ min_{B,\alpha_i} || x_i-B\alpha_i ||^2_2 + \lambda \sum_{i=1}^m || \alpha_i ||_1 \] 其中B为字典矩阵，\(\alpha_i\)则是样本\(x_i\)的稀疏表示。该式的第一项是希望\(\alpha_i\)能够尽可能重构样本，而第二项则是希望\(\alpha_i\)尽可能稀疏。

压缩感知

在现实任务中，我们常希望能够通过部分信息来恢复全部信息，假定有长度为m的离散信号x，采样后得到长度为n的信号y，其中n<<m： \[ y = \phi x \] 其中\(\phi \in R^{n \times m}\)表示对信号x的测量矩阵，而由于n<<m，因此上式是一个欠定方程。

现在假设存在某个线性变换\(\psi \in R^{n \times m}\)，使得y表示为： \[ y = \phi \psi s = As \] 若能恢复出s，我们也可以最后恢复出x。虽然这个问题仍然是欠定的，但如果s具有稀疏性，我们就可以解决这个问题了。这里A的作用则类似于字典，能够将信号转换为稀疏表示。

压缩感知分为"感知测量"和"重构恢复"两个阶段，前者关注如何对原始信号进行处理以获得稀疏样本表示，后者则是基于稀疏性从少量观察中恢复原信号。

对于大小为nXm的矩阵A，若存在常数\(\delta_k \in (0, 1)\)使得对任意常量s和A的所有子矩阵\(A_k \in R^{n\times k}\)有： \[ (1-\delta_k)||s||_2^2 \leq || A_ks ||_2^2 \leq (1+\delta_k)||s||_2^2 \] 则称A满足k限定等距性，此时可通过下面的优化问题从y中恢复出稀疏信号s： \[ min_s || s ||_0 \\ s.t. \ \ y = As \] 但该式涉及到L0范数最小化，这是一个NP难的问题，但由于L1范数最小化在一定条件下与L0范数最小化问题同解，因此有： \[ min_s || s ||_1 \\ s.t. \ \ y = As \]

降纬与度量学习

发表于 2019-03-30

降纬与度量学习

k近邻学习

k近邻学习是一种常见的监督学习方法，给定测试样本，然后基于某种距离度量找出训练样本中与测试样本距离最近的k个样本。在预测结果时，既可以通过投票法选择k个样本中出现最多的类标记，也可以在回归任务中使用平均法计算输出标记的平均值，还可以基于距离远近进行加权平均或者加权投票。

给定测试样本x，若其最近邻样本为z，则该分类器的出错概率就是x与z类标记不同的概率： \[ P(err) = 1 - \sum_{c \in y} P(c|x)P(c|z) \]

低维嵌入

假设测试样本x附近任意小的\(\sigma\)距离范围内总能找到一个训练样本，即需要实现足够大的密度采样。然而这种情况在现实生活中却不容易实现，以\(\sigma=0.001\)为例，单个属性就需要1000个样本点平均分布在归一化后的属性取值范围内。但假如属性维度数目达到了20，样本就指数增长到(10³⁾20，这就是出现了所谓的维数灾难(curse of dimensionality)。

缓解这个问题的一个重要途径是实现降维，之所能降维，是因为往往与学习任务相关的属性仅仅是某个低维分布。若要求原始空间样本中样本之间的距离在低维空间得以保持，则要实现"多维缩放"(MDS——Multiple Dimensional Scaling)。

假设m个样本在原始空间的距离矩阵为\(D\in R^{m X m}\)，其第i行h列的元素\(dist_{ij}\)为样本\(x_i\)到\(x_j\)的距离。而我们的目标是获得样本在\(d'\)维空间的表示\(Z\in R^{d'Xm}\)，d'比d小，且任意两个样本在d'维空间中的欧式距离应该与原始空间相等或者近似于。

令\(B=Z^TZ \in R^{mXm}\)，且\(b_{ij}=z_i^Tz_j\)，则有： \[ dist_{ij}^2 = b_{ii} + b_{jj} - 2b_{ij} \] 令降维后的样本Z被中心化，即\(\sum_{i=1}^mz_i=0\)，矩阵B的行与列之和为0，则有： \[ \sum_{i=1}^m dist_{ij}^2 = tr(B) + mb_{jj} \\ \sum_{j=1}^m dist_{ij}^2 = tr(B) + mb_{ii} \\ \sum_{i=1}^m\sum_{j=1}^m dist_{ij}^2 = 2m \ tr(B) \] 其中，tr为矩阵的trace，\(tr(B) = \sum_{i=1}^m || z_i ||^2\)： \[ dist_{i.}^2 = \frac{1}{m}\sum_{j=1}^m dist_{ij}^2 \\ dist_{.j}^2 = \frac{1}{m}\sum_{i=1}^m dist_{ij}^2 \\ dist_{..}^2 = \frac{1}{m^2}\sum_{i=1}^m\sum_{j=1}^m dist_{ij}^2 \] 根据上式，可得： \[ b_{ij} = -\frac{1}{2}(dist_{ij}^2-dist_{i.}^2-dist_{.j}^2+dist_{..}^2) \] 由此可见，我们可以通过降维前后保持不变的距离矩阵D求取内积矩阵B。对矩阵B做特征值分解，取A为d‘个最大特征值所构成的对角矩阵，V为相应的特征向量矩阵。 \[ Z = A^{1/2}V^T \in R^{d'Xm} \] 一般来说，想要获得低维子空间，最简单是对原始高维空间进行线性变换，这就是线性降维方法。

主成分分析

主成分分析(Principal Component Analysis，简称PCA)是最常用的一种降维方法。简单来说，就是用一个超平面来对所有样本进行适当的表达，这个超平面应该具有的性质：

样本点到这个超平面的距离都足够近；
样本点在这个超平面的投影尽可能分开；

假设样本进行了中心化，即\(\sum_ix_i=0\)，再假定投影变换后的新坐标系为\({w_1,w_2,…,w_d}\)，其中\(w_i\)是标准正交基。假设降维之后样本点\(x_i\)在低维空间下的投影是\(z_i = {z_{i1},z_{i2},…,z_{id'}}\)。其中，\(z_{ij}=w_j^Tx_i\)，重构回来的投影带点为\(x_i=\sum_{j=1}^{d'}z_{ij}w_j\)。

考虑整个数据集，原样本点与重构后的投影点之间的距离： \[ \sum_{i=1}^m||\sum_{j=1}^{d'}z_{ij}w_j - x_i||^2_2 = \sum_{i=1}^mz_i^Tz_i-2\sum_{i=1}^mz_i^TW^Tx_i+const \varpropto - tr(W^T(\sum_{i=1}^mx_ix_i^T)W) \] 根据上面的属性要求，我们需要最小化上式： \[ min \ -tr(W^TXX^TW) \] 而为了使得所有样本点的投影尽可能分散，则最大化投影后样本点的方差 \(\sum_i W^Tx_ix_iW\)： \[ max \ tr(W^TXX^TW) \] 可见，两个优化目标等价，对其使用拉格朗日乘子法，得： \[ XX^Tw_i = \lambda_iw_i \] 然后对协方差矩阵\(XX^T\)进行特征值分解，将求得的特征值进行排序，再取前n个特征值对应的特征向量构成\(W^*=(w_1,w_2,…,w_n)\)。

核化线性降维

在现实任务中，需要实现非线性映射才能找到恰当的低维嵌入。非线性将维的一种常用方法是基于核技巧对线性将维方法进行"核化"。

假设我们将在高维特征空间中把数据投影到\(W=(w_1,w_2,..,w_d)\)确定的超平面上，根据上面的式子有： \[ (\sum_{i=1}^mz_iz_i^T)w_j = \lambda_jw_j \] 其中\(z_i\)是样本点\(x_i\)在高维特征空间中的像，因此有: \[ w_j = \frac{1}{\lambda_j}(\sum_{i=1}^mz_iz_i^T)w_j = \sum_{i=1}^m z_i \frac{z_i^Tw_j}{\lambda_j} = \sum_{i=1}^m z_i \alpha_i^j \] 假定\(z_i = \phi(x_i)\)，即原始属性空间中的样本点通过映射\(\phi\)产生。

因此前面的式子可以变换为 \[ (\sum_{i=1}^m \phi(x_i)\phi(x_i)^T) w_j= \lambda_jw_j \\ w_j = \sum_{i=1}^m \phi(x_i) \alpha_i^j \] 由于我们不知道\(\phi\)的具体形式，因此引入核函数： \[ k(x_i, x_j) = \phi(x_i)\phi(x_i)^T \] 将上面的式子化简后，得到： \[ K \alpha^j = \lambda_j\alpha^j \] 这里又变成了特征值分解的问题，取K最大的d'个特征值对应的特征向量即可。

流形学习

"流形"是在局部与欧氏空间同胚的空间，它在局部具有欧氏空间的性质，能用欧式距离来进行距离计算。若低维流形嵌入到高维空间中，其局部仍然具有欧氏空间的性质，因此可以在局部建立降维映射关系，并设法将局部关系推广到全局。

等度量映射

等度量映射(Isomap)的一个出发点：低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，可能会丢失某些信息。以下图为例：

如果使用传统的欧氏距离来作为距离尺度，显然会抛弃“数据的内部特征”，即假设一只虫子从一点到另一点，如果它不能脱离图中的曲面行走，那么红色曲线才是距离最短的路径。

如上图，低维嵌入流形上两点间的距离是"测地线"距离，要求得这个距离，可以对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图。这样计算两点之间的测地线距离的问题，就变成了临接图上两点之间的最短路径问题。

构建近邻图也有两种做法：一种是指定近邻点个书，例如欧氏距离最近的k个点为近邻点；另一种则是指定距离阈值\(\epsilon\)，小于这个距离的点则认为是近邻点。

局部线性嵌入

与Isomap不同的是，局部线性嵌入LLE试图保持领域内样本之间的线性关系，如图：

假设样本点可以通过它的领域样本线性重构： \[ x_i = w_{ij}x_j+w_{ik}x_k+w_{il}x_; \] LLE希望上式的关系在低维空间中得以保持。

算法步骤；

LLE首先为每个样本找到其近邻下标集合\(Q_i\)，然后计算出样本点对\(x_i\)进行线性重构的系数\(w_i\)：

\[ min \sum_{i=1}^m || x_i - \sum_{j \in Q_i} w_{ij}x_j||^2_2 \\ \sum_{j \in Q_i} w_{ij} = 1 \]

令\(C_{jk} = (x_i-x_j)^T(x_i-x_j)\)，\(w_{ij}\)有闭式解： \[ w_{ij} = \frac{\sum_{k\in Q_i} C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}} \] LLE在低维空间中保持\(w_i\)不变，因此低维空间坐标\(z_i\)可通过以下求解： \[ min \sum_{i=1}^m || z_i - \sum_{j \in Q_i} w_{ij}z_j||^2_2 \\ M = (1-W)^T(1-W) \] 则上式可以重写为： \[ min \ tr(ZMZ^T) \\ ZZ^T = 1 \] 然后对改式通过特征值分解，M最小的k个特征值组成的矩阵即为\(Z^T\).

度量学习

在机器学习中，对高维数据进行降维的目的是找到一个合适的低维空间，而由于每个空间对应了在样本属性定义的一个距离度量。因此寻找合适的空间就是寻找一个合适的距离度量。

对两个d维的样本\(x_i, x_j\)，引入属性权重后的平方欧氏距离为： \[ dist_{wed}^2(x_i,x_j) = ||x_i-x_j||^2_2 = w_1\cdot dist_{ij,1}^2 + w_2\cdot dist_{ij,2}^2+...+w_d\cdot dist_{ij,d}^2 \\ =(x_i-x_j)^TW(x_i-x_j) \] 其中W=diag(w)是一个对角矩阵。

由于W的非对角矩阵为0，因此坐标轴是正交的，即属性之间无关，但现实生活中属性往往是相关的，因此可以将W替换为一个普通的半正定对称矩阵M。由此可得到马氏距离： \[ dist_{mat}^2(x_i,x_j) =(x_i-x_j)^TM(x_i-x_j)= ||x_i-x_j||^2_M \] 度量学习必须对M进行学习，而因为M是半正定对称矩阵，因此一定存在正交基P使得\(M=PP^T\)。

对M学习需要设置合适优化目标，不同度量学习方法针对不同的目标获得合适半正定对称距离度量矩阵M。