Posts Tagged ‘Algorithm’

深度残差网络的个人理解

June 21st, 2017

上篇对于三大RCNN算法进行了阐述,算法首要都必须提取整幅图的特征向量,目前性能比较好的神经网络是ResNet。ResNet使用了深度残差网络(Deep Residual Network),这种网络的发明的背景在于网络的层数在不断增加的情况下出现识别率降低的问题。

Deep Residual Network采用在层与层之间添加shortcut,即每层的输出不是传统神经网络当中输入的映射,而是映射和输入的叠加。

网上很多观点都倾向于梯度消失,即对网络做BP推导的话,

本来每个子项就特别小,再乘以更小的子项导致梯度趋近于0,而Deep Residual Network采用添加路径的方式将X1和XL连接起来,导致偏导置于一个比较大的数,在BP过程中,梯度不容易消失。

学术界对于出现这种问题的根源有不同的看法,我倾向这种增加路径的方式非常类似于Dropout,一个是增加路径,一个是随机减少路径,实际上效果来自于训练层数的减少,实际每次训练网络结构层数少于网络最大层数。

目前在我算法里,我使用的是ResNet50,50就是包含50层Conv卷积,ResNet50在网上有现成的model和weights,不过这里为了加深理解提供部分基于Keras的模型代码和模型结构图示。

    x = ZeroPadding2D((3, 3))(img_input)

    x = Convolution2D(64, (7, 7), strides=(2, 2), name='conv1', trainable = trainable)(x)
    x = FixedBatchNormalization(axis=bn_axis, name='bn_conv1')(x)
    x = Activation('relu')(x)
    x = MaxPooling2D((3, 3), strides=(2, 2))(x)

    x = conv_block(x, 3, [64, 64, 256], stage=2, block='a', strides=(1, 1), trainable = trainable)
    x = identity_block(x, 3, [64, 64, 256], stage=2, block='b', trainable = trainable)
    x = identity_block(x, 3, [64, 64, 256], stage=2, block='c', trainable = trainable)

    x = conv_block(x, 3, [128, 128, 512], stage=3, block='a', trainable = trainable)
    x = identity_block(x, 3, [128, 128, 512], stage=3, block='b', trainable = trainable)
    x = identity_block(x, 3, [128, 128, 512], stage=3, block='c', trainable = trainable)
    x = identity_block(x, 3, [128, 128, 512], stage=3, block='d', trainable = trainable)

    x = conv_block(x, 3, [256, 256, 1024], stage=4, block='a', trainable = trainable)
    x = identity_block(x, 3, [256, 256, 1024], stage=4, block='b', trainable = trainable)
    x = identity_block(x, 3, [256, 256, 1024], stage=4, block='c', trainable = trainable)
    x = identity_block(x, 3, [256, 256, 1024], stage=4, block='d', trainable = trainable)
    x = identity_block(x, 3, [256, 256, 1024], stage=4, block='e', trainable = trainable)
    x = identity_block(x, 3, [256, 256, 1024], stage=4, block='f', trainable = trainable)

上图只是针对其中一个conv_block,conv_block分出两个分支,一个分支卷积一次,一个分支卷积3次,然后在res2a处将两个分支Add。identity_block则是直接将输入和三次卷积结果Add。

 

http://blog.csdn.net/superCally/article/details/55671064

https://my.oschina.net/yilian/blog/667900

https://arxiv.org/pdf/1605.06431.pdf

 

字符串切割问题求解

June 30th, 2015

我在做Leetecode的一道题时,遇到了一道切割字符串求解回文字符串的题目,题目大意如下:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

这个时候我们需要使用DFS算法,进行深搜,但是这个里我们需要注意的一个问题是,每个字符只能用一次,而且不能使用拼接的方式,需要直接从string s中截取子字符串,所以我们使用s.substr(start,count)的方式。这个不同于之前的combinationSum的题目,需要有一个中间target保存。我们只需要传入下面几个参数即可,使用step来标示当前指向s的开头index,i为结束index。

void DFS(string &s,vector<vector<string>> &result,vector<string> &path,int step){
		if(step>=s.size()){
			result.push_back(path);
			return;
		}
		for(auto i = step;i<s.size();i++){
			if(is_palindrome(s,step,i)){
				path.push_back(s.substr(step,i-step+1));
				DFS(s,result,path,i+1);
				path.pop_back();
			}
		}
	}

	bool is_palindrome(string &s,int start,int end){
		while(start < end){
			if(s[start]!=s[end])
				return false;
			start++;
			end--;
		}
		return true;
	}
};

一个长度为n 的字符串,有n-1 个地方可以砍断,每个地方可断可不断,因此复杂度为O(2^(n-1))

 

https://leetcode.com/problems/palindrome-partitioning/

Combination Sum 思路

June 1st, 2015

最新刷leetcode的题目,发现了Combination Sum题目,这个题目分为I、II、III。难度层层递进,题目就是遍历vector容器,选择出符合target number的sum组合,这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板,首先要构造dfs函数。

一般情况下,我们需要五个参数:结果,原始数据集,中间结果,当前指向的数据,满足target number的值:

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集,深搜这个数据集的各种可能性,将达成target的path中间结果加入result,按照通用模版

void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

第一步:收敛也就是target==0
第二步:使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步:如果通过第二部,也就意味着这个current合格,可以将这个加入到path中,然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的,可以多次使用。如果只使用一次的话,也就意味着我们需要sort(),然后需要将上个满足条件的值跳过,也就是II中的nums[i]==nums[i-1]比较Combination Sum II

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

 

 

题目:

 

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

DFS通用解法

May 8th, 2015

最近在刷一些算法题,发现DFS在单链表,二叉树,图,集合的解题比较多,具有一定的通用规律,现在讲通用方法记录下。拿二叉树举例,比如我们需要从根走到叶子节点才能得到一个解,这种类型非常适合是用DFS,再以二维数组举例,我们可以将二维数组当成一个图,进行搜索,在搜索的同事满足一定的匹配等。

一般情况下Wide-FS只要求有一个解,而且需要将整个中间状态存储到内存中,而DFS只存储一条路径,非常时候解决一些问题。

在DFS中我们需要一个收敛条件,也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜,我们可以剪枝,常用方式使用状态数组表示,提前return,可以大大加快递归速度。

通用dfs模板:

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径,也是中间结果,可以是一维数组
* @param[out] result 存放最终结果,二维数组
* @param[inout] cur or gap 标记当前位置或距离目标的距离,或者可以
* 是start end等标记
* @return 路径长度,如果是求路径本身,则不需要返回长度
* 可以返回bool等,依照题目要求来实现。
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

这里我举一个例子:列举所有set可能的子集合,比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题,需要首先按照上面的这种模板构建,首先是这个dfs的input 也就是这个S,中间路径path与S类型相同。结果应该是一个二维数组,也就是vector< vector > result,最后我们需要一个step作为收敛条件。

void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) {
     if (step == S.size()) {//到达S.size()收敛
           result.push_back(path);
           return;
     }
     //这里没有剪枝
     // 不选S[step]
     subsets(S, path, step + 1, result);
     // 选S[step]
     path.push_back(S[step]);
     subsets(S, path, step + 1, result);
     path.pop_back();
}
 void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result,
                     vector<int>::iterator start){
 
     result.push_back(path);
 
     for(auto i = start;i<nums.end();i++)
     {
          path.push_back(*i);
          dfs(nums,path,result,i+1);
          path.pop_back(); 
     }
 }

深度搜索比较难以理解,层层递归会让我迷失,不过进行断点认真跟踪是可行的。最后跟踪断点结果是:

[]
3
2
2,3
1,
1,3
1,2
1,2,3

还有很多场景,比如二维数组寻路,都会用到上下左右的移动,还要使用flag来标示,具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/

CFS 调度算法

February 2nd, 2015

之前说过CFS是Kernel中的一种调度policy,这个调度算法的核心,所有task都应该公平分配处理器,为了达成这个目标,CFS调度使用vruntime来衡量某一个进程是否值得调度。

上篇博文初步对CFS的实现有了一个说明,但是没有阐述vruntime的计算。

上篇 http://www.lizhaozhong.info/archives/1206

vruntime 是CFS算法模拟出来的一个变量,他淡化了优先级在调度中的作用,而是以vruntime的值使用struct sched_entity组织成为一棵red-black tree。

根据red-black tree的特点,值小的在tree的左边,值大的在右边,随着进程的运行,系统在timer 中断发生时会调用policy中的task_tick()方法,这个函数可以更新vruntime的值。以供CFS调度时使用。

为了维护这个red-black tree最左边的节点vruntime值最小,我们必须使得这个值单调递增,所以要比较delta_exec 与 curr->statistics.exec_max值的,并取最大值。schedstat_set(curr->statistics.exec_max,max(delta_exec, curr->statistics.exec_max));update_min_vruntime(cfs_rq);

通过这两个函数,只有最靠左的节点超过min_vruntime才会更新。

有一种情况,如果进程睡眠,则他的vruntime不变,而min_vruntime变大,则,这个进程会更加靠左!

调用路径是:

void scheduler_tick(void)
{... curr->sched_class->task_tick(rq, curr, 0); ...}
->通过函数指针,调用具体policy的函数,在CFS中是task_tick_fair,这个函数可以调用entity_tick()更新
当前调度实体sched_entity所在的cfs_rq中当前运行task的sche_entity中vruntime的值
->
3097 static void
3098 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
3099 {
3100         /*
3101          * Update run-time statistics of the 'current'.
3102          */
3103         update_curr(cfs_rq);
3104
......
3131 }
->static void update_curr(struct cfs_rq *cfs_rq)

从entity_tick()中的update_curr()调cfs中真正更新vruntime值的函数:

694 static void update_curr(struct cfs_rq *cfs_rq)
695 {
....
697         u64 now = rq_clock_task(rq_of(cfs_rq));
....
703         delta_exec = now - curr->exec_start;
704         if (unlikely((s64)delta_exec <= 0))
705                 return;
706
707         curr->exec_start = now;
708
709         schedstat_set(curr->statistics.exec_max,
710                       max(delta_exec, curr->statistics.exec_max));
711
712         curr->sum_exec_runtime += delta_exec;
713         schedstat_add(cfs_rq, exec_clock, delta_exec);
714
715         curr->vruntime += calc_delta_fair(delta_exec, curr);
716         update_min_vruntime(cfs_rq);
717
718         if (entity_is_task(curr)) {
719                 struct task_struct *curtask = task_of(curr);
720
721                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
722                 cpuacct_charge(curtask, delta_exec);
723                 account_group_exec_runtime(curtask, delta_exec);
724         }
725
726         account_cfs_rq_runtime(cfs_rq, delta_exec);
727 }

首先获取当前rq的时间,使用delta_exec获取当前进程运行的实际时间,然后将exec_start再次更新为now以便下一次使用。

并将该值加到sum_exec_runtime中时间中,对于vruntime 时间则需要calc_delta_fair(delta_exec, curr);进行处理。

通过下表我们可以看出当nice值为0,weight值为1024。另外我们需要明确nice值【-20,+19】映射到整个系统中是100~139,也就是说nice值每增加一个nice值,获得cpu时间减少10%,反之增加10%!而0~99则属于实时进程专用!nice值越高权值越小!

1046 static const int prio_to_weight[40] = {
1047  /* -20 */     88761,     71755,     56483,     46273,     36291,
1048  /* -15 */     29154,     23254,     18705,     14949,     11916,
1049  /* -10 */      9548,      7620,      6100,      4904,      3906,
1050  /*  -5 */      3121,      2501,      1991,      1586,      1277,
1051  /*   0 */      1024,       820,       655,       526,       423,
1052  /*   5 */       335,       272,       215,       172,       137,
1053  /*  10 */       110,        87,        70,        56,        45,
1054  /*  15 */        36,        29,        23,        18,        15,
1055 };

在calc_delta_fair()函数中会比较当前权重与nice值为0的权重(NICE_0_LOAD),如果等于则直接返回加权后的vruntime,如果不同则需要对该权值加权。
struct sched_entity *se 存在着当前进程的权重,就是上面那个array里面数字!

601 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
602 {
603         if (unlikely(se->load.weight != NICE_0_LOAD))
604                 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
605
606         return delta;
607 }

如果当前进程的nice值不等于nice 0 ,进入下面的函数:

214 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
215 {
216         u64 fact = scale_load_down(weight);
217         int shift = WMULT_SHIFT;
218
219         __update_inv_weight(lw);
220
221         if (unlikely(fact >> 32)) {
222                 while (fact >> 32) {
223                         fact >>= 1;
224                         shift--;
225                 }
226         }
227
228         /* hint to use a 32x32->64 mul */
229         fact = (u64)(u32)fact * lw->inv_weight;
230
231         while (fact >> 32) {
232                 fact >>= 1;
233                 shift--;
234         }
235
236         return mul_u64_u32_shr(delta_exec, fact, shift);
237 }

这个函数有些复杂,我现在理解这个加权公式就是delta_exec = delta_exec * (weight / lw.weight)

我们可以绘制出不同nice下,加权后vruntime与真实的delta_exec值的关系。我们可以对照上面那个数组发现nice值越高,权值越小,在这里我们比较的是1024/lw.weight的值,权值越小的,商越大,vruntime越大!在CFS中,vruntime值越小,越容易调度!
105514854

 

mul_u64_u32_shr()函数应该是32位与64位转换的,具体没研究清楚,改天再来。
具体这个的解释:
/*
203  * delta_exec * weight / lw.weight
204  *   OR
205  * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
206  *
207  * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
208  * we're guaranteed shift stays positive because inv_weight is guaranteed to
209  * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
210  *
211  * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
212  * weight/lw.weight <= 1, and therefore our shift will also be positive.
213  */

CFS总结:

1)不再区分进程类型,不使用nice值判断优先级,而是使用vruntime衡量一个进程的重要性。

2)对于IO类型的进程,随着睡眠时间正常,仍然可以得到公平的时间片

3)对于优先级高的进程,可以获得更多的CPU时间。

参考:
http://lxr.free-electrons.com/source/kernel/sched/fair.c#L214
http://lxr.free-electrons.com/source/kernel/sched/sched.h#L1046