Categories
不学无术

LeetCode 368. Largest Divisible Subset

思路:
想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…
时间复杂度应该是O(n^2)

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty())
            return nums;
        sort(nums.begin(), nums.end());
        int bestIndex = 0;
        vector<vector<int>> results(nums.size());
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<i; j++){
                //nums[j] < nums[i]
                if(nums[i]%nums[j]==0 &&
                    results[i].size() < results[j].size())
                    results[i] = results[j];
            }
            results[i].push_back(nums[i]);
            if(results[bestIndex].size() < results[i].size())
                bestIndex = i;
        }
        return results[bestIndex];
    }
};

 

Categories
不学无术

LeetCode 424. Longest Repeating Character Replacement

思路很重要。
给定一个长度n的字符串s和限制k,将s中的部分字符替换(替换次数<=k)后,能得到连续字符(如AAAA)的长度最大为多少?
使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值(可以看做分布情况)以及当前窗口的起始点,窗口内最多字符的计数best。我们知道,最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话,就得把窗口缩小(起始点后挪)。窗口缩小时记得把窗口计数更新一下。
这里有一个tricky的地方,best值本来在滑动窗口的时候是要更新的,因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值,所以这个情况并不需要考虑对best进行更新,反正它也成不了最优。

代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        //sliding window solution
        int charCount[26] = {0};
        int w_start = 0, best = 0;
        for(int w_end = 0; w_end < s.size(); w_end++){
            charCount[s[w_end]-'A']++;
            best = max(best, charCount[s[w_end]-'A']);
            if(best+k <= w_end-w_start){
                //replace k chars in current window,
                // if we still can't have the optimal
                // we will shrink the left border of window
                charCount[s[w_start]-'A']--;
                w_start++;
            }
        }
        return s.size()-w_start;
    }
};

 

Categories
不学无术

LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流,判断当前整个数组的中位数值。由于数据流是可以不断增加的,因此采用两个堆(最大堆*1+最小堆*1)来实现。
这东西思路网上都有,每次新进一个数,维护堆就行了。维护一次的复杂度是O(logN),对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西,在<algorithm>库里面就有三个与堆有关的函数,利用vector存储堆元素就可以调用这些函数来建立、更新堆。
make_heap(first, last, comp)是建立堆的函数,输入的first, last对应begin()和end()的iterator,comp函数可选,与库中sort()用到的方法相同,自定义的时候比较两个元素x, y的偏序关系,返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>(),直接用来比较<和>关系的。
push_heap(first, last, comp)使用时,将新元素放在数组末尾(代表堆的末叶节点),然后调用这个函数更新堆,是一个sift-up的过程。
pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop,同时调整更新堆。

代码

class MedianFinder {
private:
    vector<int> maxHeap; // store values less than median
    vector<int> minHeap; // store values greater than median
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        int minSize = minHeap.size();
        int maxSize = maxHeap.size();
        if(maxSize == 0){
            maxHeap.push_back(num);
            return;
        }
        if(num < maxHeap[0]){
            maxHeap.push_back(num);
            push_heap(maxHeap.begin(), maxHeap.end());
            if(maxSize > minSize) {
                pop_heap(maxHeap.begin(), maxHeap.end());
                int popVal = maxHeap[maxHeap.size()-1];
                maxHeap.pop_back();
                minHeap.push_back(popVal);
                push_heap(minHeap.begin(), minHeap.end(), greater<int>());
            }
        } else {
            minHeap.push_back(num);
            push_heap(minHeap.begin(), minHeap.end(), greater<int>());
            if(minSize >= maxSize) {
                pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
                int popVal = minHeap[minHeap.size()-1];
                minHeap.pop_back();
                maxHeap.push_back(popVal);
                push_heap(maxHeap.begin(), maxHeap.end());
            }
        }
    }
    // Returns the median of current data stream
    double findMedian() {
        if((maxHeap.size() + minHeap.size())%2 == 0){
            //even num.
            if(maxHeap.empty() && minHeap.empty())
                return 0.0;
            double sum = maxHeap[0] + minHeap[0];
            return sum/2.0;
        } else {
            if(maxHeap.empty())
                return 0.0;
            return (double)maxHeap[0];
        }
    }
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

 

Categories
不学无术

LeetCode 51. N-Queens

八皇后问题的延伸版,回溯实现。

class Solution {
public:
bool checkQueen(int** mat, int N, int r, int c) {
	for (int row = 0; row < N; row++) {
		if (row == r)
			continue;
		if (mat[row][c] == 1)
			return false;
	}
	//
	int row = r-1, col = c-1;
	while (row >= 0 && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row--; col--;
	}
	row = r + 1, col = c + 1;
	while (row < N && col < N) {
		if (mat[row][col] == 1)
			return false;
		row++; col++;
	}
	//
	//
	row = r - 1, col = c + 1;
	while (row >= 0 && col < N) {
		if (mat[row][col] == 1)
			return false;
		row--; col++;
	}
	row = r + 1, col = c - 1;
	while (row < N && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row++; col--;
	}
	//
	return true;
}
void nQueensSub(int** mat, int N, int row, int col, vector<vector<string>>& results) {
	if (row == N) {
		//print
		vector<string> result;
		for (int i = 0; i < N; i++) {
			string row;
			for (int j = 0; j < N; j++) {
				if (mat[i][j] == 0)
					row += '.';
				else
					row += 'Q';
			}
			result.push_back(row);
		}
		results.push_back(result);
	}
	else {
		if (checkQueen(mat, N, row, col)) {
			//put queen here
			mat[row][col] = 1;
			//try next row
			nQueensSub(mat, N, row + 1, 0, results);
			mat[row][col] = 0;
		}
		//try next col
		if (col+1 < N) {
			nQueensSub(mat, N, row, col + 1, results);
		}
	}
}
    vector<vector<string>> solveNQueens(int n) {
	    int** mat = new int*[n];
	    for (int i = 0; i < n; i++) {
	    	mat[i] = new int[n];
	    	for (int j = 0; j < n; j++) {
	    		mat[i][j] = 0;
    		}
    	}
    	vector<vector<string>> results;
    	nQueensSub(mat, n, 0, 0, results);
    	for (int i = 0; i < n; i++) {
    		delete[]mat[i];
    	}
    	delete[] mat;
    	return results;
    }
};

 

Categories
不学无术

基于单词的统计翻译模型 IBM Model1

统计翻译模型的基本思想是对大量平行(parallel)语料进行统计分析。之前实习的时候有幸接触到一些简单的模型,而事实上这种简单的模型在大量数据训练的基础上,发挥还是挺不错的。
IBM的统计翻译模型从简单到繁琐,一共有Model1-Model5五个模型,全都是基于词的统计模型。
本文只对Model1作简单介绍,方便起见,文中以将法文(French)翻译为英文(English)为例。

噪声信道模型。机器翻译=翻译模型+语言模型

模型假定源语言中的(法语)句子是由目标语言(英语)经过含有噪声的信道编码后得到的。寻找最佳的英文翻译结果等同于寻找[latex]\arg\max_{e}p(e|f)[/latex]。
根据贝叶斯公式,容易得到[latex]\arg\max_{e}p(e|f)=\arg\max_{e}\frac{p(f|e)p(e)}{p(f)}[/latex],由于对于同一个法语单词来说,[latex]p(f)[/latex]是一定的,因此上式等同于[latex]\arg\max_{e}p(f|e)p(e)[/latex],其中

  • [latex]p(f|e)[/latex]称为翻译模型,即给定信号源,观察到信号的概率;
  • [latex]p(e)[/latex]称为语言模型,即信号源发生的概率;

机器翻译的任务就被拆解成这两个模型的任务了。本文只负责翻译模型:)

词对齐(Alignment)

Word Alignment
我们假设要翻译的法语句子包含m个单词,即[latex]F=f_1, f_2, …, f_m[/latex],翻译出来的英语句子包含l个单词,即[latex]E=e_1, e_2, …, e_l[/latex],那么之前提到的翻译概率[latex]p(F|E)=p(f_1,f_2,…,f_m|e_1,e_2,…,e_l, m)[/latex]其中包含了对句子长度服从这么个条件分布[latex]p(m|l)[/latex]的假设。
然而这个概率是很难直接建模的,于是一帮聪明的人想出来一个方案:引入词对齐(word alignment):[latex]p(F|E)=p(F,A|E)=p(f_1,f_2,…,f_m,a_1,a_2,…,a_m|e_1,e_2,…,e_l, m)[/latex],其中这个a就是词对齐,它是个隐变量,表示源语言(法语)中的某个单词是用目标语言(英语)翻译而来的。
具体可以看这个例子:

e = And the program has been implemented
     1   2     3     4   5       6
f = Le programme a ete mis en application
     1   2       3  4   5   6      7

这个例子中,[latex]l=6, m=7[/latex],一个理想的对齐方式如下:

Le => the
Programme => program
a => has
ate => been
mis => implemented
en => implemented
application => implemented

它对应的alignment标记可以表示为[latex]a_1,a_2,…,a_7=<2,3,4,5,6,6,6>[/latex]
此外在英文中还有加入个特殊的NULL单词,它表示法语中那些对于英语翻译“无用”的词。

IBM Model 1:翻译模型=对齐+词-词翻译

根据之前单词对齐的假设,我们可以把翻译任务进一步拆分成两部分:对齐和词到词的翻译,边际化参数A
[latex]p(F|E)=\sum_{A}p(F,A|E)=\sum_{A}p(A|E)p(F|E,A)[/latex]
第一部分是对齐,在Model 1中做了一个最简单的假设:每个对齐都是等概率发生的。所以[latex]p(a|e)=\prod_{i=1}^{m}\frac{1}{l+1}[/latex]。
第二部分是词-词翻译,也是整个模型的核心部分,这里当然不能再精简了,否则就没有了…
[latex]P(F|E,A)=\prod_{j=1}^{m}tr(f_j|e_{A_{j}})[/latex]
这里头的[latex]tr(.|.)[/latex]就是单词到单词的翻译概率,也就是模型要学习的东西。

模型训练:期望最大化(EM)

很显然,要学习到词-词翻译概率,就必须知道单词对齐;要学习单词对齐,就得知道翻译概率,这种鸡生蛋的问题就需要用EM来解。
定义一个参数[latex]\delta(k,i,j)[/latex]表示第k组平行预料(训练集中法文-英文句子)里的第i个法文词,第j个英文词。如果是上帝模式,那[latex]\delta(k,i,j)=1/0[/latex]分别表示这两个词之间应当/不应当对齐。然而目前无人能观测到这个隐变量,所以采用最大似然估计来估计这个东西,意思就是说翻译概率的大小决定了单词对齐的概率,即
[latex]\delta(k,i,j)=\frac{q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}=\frac{tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})}[/latex]
注意上面这个式子是根据Model 1“句子中的对齐都是等概率”假定推导来的:[latex]q(j|i,l_k,m_k)=\frac{1}{l^{(k)}+1}[/latex]

算法

输入:训练集[latex](f^{(k)}, e^{(k)})[/latex]其中[latex]k=1,…,n[/latex],其中[latex]f^{(k)}=f_1^{(k)}…f_m^{(k)}, e^{(k)}=e_1^{(k)}…e_l^{(k)}[/latex]
初始化:初始化所有词-词翻译概率[latex]t(f|e)[/latex]
步骤:关键部分我用绿色的字注释了

  • for t=1…T
    • Set all counts [latex]c=0[/latex]
    • for [latex]k=1…N[/latex]
      • for [latex]i=1…m_k[/latex]
        • for [latex]j=1…l_k[/latex]
          • // word(i,j) in parallel corpus line k
          • [latex]\delta(k,i,j)=\frac{tr(f_i^{(k)}|e_j^{(k)}}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})}[/latex] //estimate alignment
          • [latex]c(e_j^{(k)},f_i^{(k)})+=\delta(k,i,j)[/latex] //update co-occurence count for word-word pair
          • [latex]c(e_j^{(k)})+=\delta(k,i,j)[/latex]
    • [latex]tr(f|e)=\frac{c(e,f)}{c(e)}[/latex] //update word-word pair translation probabilities

输出:[latex]tr(f|e)[/latex]
 

参考文献

  1. http://www.cs.columbia.edu/~mcollins/courses/nlp2011/notes/ibm12.pdf
  2. http://cpmarkchang.logdown.com/posts/245418-mt-ibm-model-1
  3. https://zh.wikipedia.org/wiki/%E7%BB%9F%E8%AE%A1%E6%9C%BA%E5%99%A8%E7%BF%BB%E8%AF%91
Categories
不学无术

Information Cell Mixture Models 语义细胞混合模型

语义细胞混合模型是用于表示模糊概念的一种模型,我个人的理解嘛,是一种介于k-means与GMM之间的一个模型。具体论文可以看

Tang, Yongchuan, and Jonathan Lawry. “Information cells and information cell mixture models for concept modelling.” Annals of Operations Research195.1 (2012): 311-323.

下面做一些简要介绍。

基本概念及假设

一个语义细胞混合模型(Information Cell Mixture Model, ICMM)是由一组语义细胞[latex]L_i[/latex]构成的,每个语义细胞使用三元组[latex]<P_i, d_i, \delta_i>[/latex]表示,这三个符号分别表示原型,距离函数以及密度函数。其中原型的概念类似于k-means中的聚类中心,而距离、密度刻画了这个聚类中心的“势力范围”。下图就是一个例子,这个ICMM里面有两个语义细胞。
%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8810-48-58

ICMM的概率密度

假设一个ICMM由[latex]n[/latex]个语义细胞构成,则可以根据每个语义细胞自身的概率密度函数及这个细胞的权重来界定整个ICMM的密度函数如下
[latex]\delta_{ICMM}(X)=\sum_{i=1}^{n} \delta_i (X) Pr(L_i)[/latex]
而每个语义细胞自身的密度函数,由一个指定的距离函数(文中用欧氏距离)和一个概率密度函数(文中用高斯密度函数)一起界定,即
[latex]\delta_{L_i}(X) = \delta_{i}(d_i(X,P_i)) [/latex]表示到X与原型的”距离”密度,而[latex]\delta[/latex]是一个高斯密度函数[latex]\delta(\epsilon|c_i, \sigma_i)[/latex].
上面这堆都是密度函数,最后算出来是个距离(也可以称之为相似度)的密度,那如果要求真正点X到ICMM的“距离”,就需要求密度函数在[latex][d(X, P_i), +\infty)[/latex]范围的积分了。

目标函数

跟其他的生成模型类似,就是最大似然估计,目标函数也就变成了整个(对数)期望最大化了。
[latex]maximize J(ICMM) = ln \delta_{ICMM}(DB)=\sum_{k=1}^{N}(ln \delta_{ICMM}(X_k))[/latex]
[latex]= \sum_{k=1}^{N} ln (\sum_{i=1}^{n}(\delta(\epsilon_{ik}|c_i, \sigma_i)Pr(L_i))[/latex]
其中DB表示数据集,k是训练集的样本,i是第i个语义细胞。
但是上面这个对数似然函数很难优化,因此引入一个隐含变量[latex]z_{ik}\in {0,1} [/latex]并且有[latex]\sum_{i=1}^{n} z_{ik} = 1[/latex],它表示由某一个语义细胞“生成”了整个ICMM。

参数更新

语义细胞的概率分布更新

引入了隐变量,很容易想到用EM来更新参数… EM就是两个步骤:1.利用现有的参数去更新隐变量;2.利用隐变量来更新参数
在我们的问题中,用隐变量[latex]z_{ik}[/latex]的最大似然估计来更新,即[latex]q_{ik}=E(z_{ik}|ICMM) = \frac{\delta(\epsilon_{ik}|c_i, \sigma_i)Pr(L_i)}{\sum_{i=1}^{n}\delta(\epsilon_{ik}|c_i, \sigma_i)Pr(L_i)}[/latex]
这里的参数c, sigma, Pr, L全都是有hat的hypothesis值,鄙人不熟悉latex,没有加上。
然后,之前的那个目标函数就转变为了
[latex]Q(.)=\sum_{k=1}^{N}\sum_{i=1}^{n}q_{ik}ln(\delta(\epsilon_{ik}|c_i, \sigma_i)Pr(L_i))[/latex]
这是一个带有约束条件(Pr权重加起来=1)最优化目标函数,所以引入Lagrange乘子[latex]\lambda[/latex]来进行变换。变换后的目标函数求最值的问题,就可以转化为偏导数=0的问题了。

更新语义细胞的概率密度

没错,又是“退而求其次”。上面写的那个目标Q,展开来是有一个高斯分布函数项的(见原文公式9),这样对Q最优化又有难度了。作者退了一步,,因为高斯分布是个[0,1]的值,它的ln是负数,因此把这一项[latex]-ln(…)[/latex]去掉,相当于加上了一个负数值的[latex]-ln(…)[/latex].
假设这个精简版的优化目标函数叫U,显然就有[latex]U<=Q[/latex],相当于U就是个lower-bound
那如果能不断提高U的话,原有的目标函数也能得到优化。还是类似,求最值=偏导数为0,在本文中就是[latex]\frac{\partial U}{\partial c_i} = 0[/latex]以及[latex]\frac{\partial U}{\partial \sigma_i} = 0[/latex]
解出来是这么两坨:
%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-48-39

参数更新算法

终于..可以更新参数了,具体算法如下

  1. 利用k-means算法找出k个语义细胞的原型,初始化每个语义细胞的权重[latex]Pr(L_i)=1/n[/latex];
  2. 计算训练集到当前原型的距离[latex]\epsilon_{ik}=d(X_k, P_i)[/latex],这里用的是欧氏距离;
  3. 初始化距离密度函数的参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-52-42
  4. 计算第一轮的隐变量%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-53-24
  5. 迭代更新(EM),直到目标函数J收敛
    1. 更新权重参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-55-40
    2. 更新密度函数的两个参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-56-24
    3. 利用更新后的参数,重新计算隐变量(的MLE)%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-57-57
    4. 计算目标函数J

GMM与ICMM

GMM与ICMM长得比较像,我觉得ICMM算是GMM的一个简化版本。GMM求的是每个样例做高斯分布的参数,而ICMM事先就假定好了有k个“原型”,先做了一轮k-means固定下了原型,再来做密度函数的参数更新。假设有N个sample,GMM就相当于是k=N的ICMM。因此从计算复杂度上来说,ICMM比GMM简单,当然了ICMM能表示的模型复杂度还需要调参(k)才能进一步优化。

Categories
不学无术

TensorFlow学习: 训练个ReLu神经网络(单隐层、双隐层)

其实是UdaCity上的深度学习公开课,感觉这个讲的最简洁明了。
下面的代码训练的是一个单隐层全连通的小小神经网络,隐层节点数量设定为1024,输入的图片是28*28的,label有’A’-‘J’共10个,所以最后用了softmax。数据使用nonMNIST的。参数更新用的mini-batch的SGD.
ReLu nonMNIST single hidden layer
下面是关键部分代码,这个课程的一个好处是用Docker+jupyter做的,给答案很方便,以前从未体验过这么流畅的哈哈哈。

batch_size = 128
num_relu_units = 1024
graph = tf.Graph()
with graph.as_default():
  # Input data. For the training data, we use a placeholder that will be fed
  # at run time with a training minibatch.
  tf_train_dataset = tf.placeholder(tf.float32,
                                    shape=(batch_size, image_size * image_size))
  tf_train_labels = tf.placeholder(tf.float32, shape=(batch_size, num_labels))
  tf_valid_dataset = tf.constant(valid_dataset)
  tf_test_dataset = tf.constant(test_dataset)
  # Variables.
  weights = tf.Variable(
    tf.truncated_normal([image_size * image_size, num_relu_units]))
  biases = tf.Variable(tf.zeros([num_relu_units]))
  wt_hidden = tf.Variable(tf.truncated_normal([num_relu_units, num_labels]))
  b_hidden = tf.Variable(tf.zeros([num_labels]))
  # Training computation.
  l1 = tf.matmul(tf_train_dataset, weights) + biases
  l1 = tf.nn.relu(l1)
  l2 = tf.matmul(l1, wt_hidden) + b_hidden
  loss = tf.reduce_mean(
    tf.nn.softmax_cross_entropy_with_logits(l2, tf_train_labels))
  # Optimizer.
  optimizer = tf.train.GradientDescentOptimizer(0.5).minimize(loss)
  # Predictions for the training, validation, and test data.
  train_prediction = tf.nn.softmax(l2)
  valid_prediction = tf.nn.softmax(
    tf.matmul(tf.nn.relu(tf.matmul(tf_valid_dataset, weights) + biases), wt_hidden) + b_hidden)
  test_prediction = tf.nn.softmax(tf.matmul(tf.nn.relu(tf.matmul(tf_test_dataset, weights) + biases), wt_hidden) + b_hidden)
num_steps = 3001
with tf.Session(graph=graph) as session:
  tf.initialize_all_variables().run()
  print("Initialized")
  for step in range(num_steps):
    # Pick an offset within the training data, which has been randomized.
    # Note: we could use better randomization across epochs.
    offset = (step * batch_size) % (train_labels.shape[0] - batch_size)
    # Generate a minibatch.
    batch_data = train_dataset[offset:(offset + batch_size), :]  # mini-batch
    batch_labels = train_labels[offset:(offset + batch_size), :]
    # Prepare a dictionary telling the session where to feed the minibatch.
    # The key of the dictionary is the placeholder node of the graph to be fed,
    # and the value is the numpy array to feed to it.
    feed_dict = {tf_train_dataset : batch_data, tf_train_labels : batch_labels}
    _, l, predictions = session.run(
      [optimizer, loss, train_prediction], feed_dict=feed_dict)
    if (step % 500 == 0):
      print("Minibatch loss at step %d: %f" % (step, l))
      print("Minibatch accuracy: %.1f%%" % accuracy(predictions, batch_labels))
      print("Validation accuracy: %.1f%%" % accuracy(
        valid_prediction.eval(), valid_labels))
  print("Test accuracy: %.1f%%" % accuracy(test_prediction.eval(), test_labels))

输出如下:

Initialized
Minibatch loss at step 0: 319.099121
Minibatch accuracy: 8.6%
Validation accuracy: 26.0%
Minibatch loss at step 500: 8.215627
Minibatch accuracy: 83.6%
Validation accuracy: 81.8%
Minibatch loss at step 1000: 11.695193
Minibatch accuracy: 78.1%
Validation accuracy: 80.8%
Minibatch loss at step 1500: 7.294090
Minibatch accuracy: 83.6%
Validation accuracy: 79.1%
Minibatch loss at step 2000: 8.128178
Minibatch accuracy: 77.3%
Validation accuracy: 81.5%
Minibatch loss at step 2500: 3.724820
Minibatch accuracy: 84.4%
Validation accuracy: 82.1%
Minibatch loss at step 3000: 3.041273
Minibatch accuracy: 86.7%
Validation accuracy: 81.0%
Test accuracy: 88.1%

随后又试了一下有两个隐层的ReLuNet,隐层节点数分别是1024,512,使用AdamOptimizer训练,似乎准确度又能提高一点点
迭代次数=5000,miniBatch的大小没有变

def getPrediction(dataSet, wt0, wt1, wt2, b0, b1, b2):
    l1 = tf.nn.relu(tf.matmul(dataSet, wt0) + b0)
    l2 = tf.nn.relu(tf.matmul(l1, wt1) + b1)
    l3 = tf.matmul(l2, wt2) + b2
    return tf.nn.softmax(l3)
batch_size = 128
num_relu_units = 1024
num_relu_units_l3 = 512
dropout_keep_prob = 0.75
graph = tf.Graph()
with graph.as_default():
  # Input data. For the training data, we use a placeholder that will be fed
  # at run time with a training minibatch.
  tf_train_dataset = tf.placeholder(tf.float32,
                                    shape=(batch_size, image_size * image_size))
  tf_train_labels = tf.placeholder(tf.float32, shape=(batch_size, num_labels))
  tf_valid_dataset = tf.constant(valid_dataset)
  tf_test_dataset = tf.constant(test_dataset)
  # Variables.
  weights = tf.Variable(
    tf.truncated_normal([image_size * image_size, num_relu_units]))
  biases = tf.Variable(tf.zeros([num_relu_units]))
  wt_hidden = tf.Variable(tf.truncated_normal([num_relu_units, num_relu_units_l3]))
  b_hidden = tf.Variable(tf.zeros([num_relu_units_l3]))
  wt_h_l3 = tf.Variable(tf.truncated_normal([num_relu_units_l3, num_labels]))
  b_h_l3 = tf.Variable(tf.zeros([num_labels]))
  # Training computation.
  l1 = tf.matmul(tf_train_dataset, weights) + biases
  l1 = tf.nn.relu(l1)
  #l1 = tf.nn.dropout(l1, dropout_keep_prob)
  l2 = tf.matmul(l1, wt_hidden) + b_hidden
  l2 = tf.nn.relu(l2)
  #l2 = tf.nn.dropout(l2, dropout_keep_prob)
  l3 = tf.matmul(l2, wt_h_l3) + b_h_l3
  loss = tf.reduce_mean(
    tf.nn.softmax_cross_entropy_with_logits(l3, tf_train_labels))
  # Optimizer.
  optimizer = tf.train.AdamOptimizer().minimize(loss)
  # Predictions for the training, validation, and test data.
  train_prediction = tf.nn.softmax(l3)
  valid_prediction = getPrediction(tf_valid_dataset, weights, wt_hidden, wt_h_l3,
                                  biases, b_hidden, b_h_l3) #tf.nn.softmax(
    #tf.matmul(tf.nn.relu(tf.matmul(tf_valid_dataset, weights) + biases), wt_hidden) + b_hidden)
  test_prediction = getPrediction(tf_test_dataset, weights, wt_hidden, wt_h_l3,
                                  biases, b_hidden, b_h_l3)
    #tf.nn.softmax(tf.matmul(tf.nn.relu(tf.matmul(tf_test_dataset, weights) + biases), wt_hidden) + b_hidden)
num_steps = 5000
with tf.Session(graph=graph) as session:
  tf.initialize_all_variables().run()
  print("Initialized")
  for step in range(num_steps):
    # Pick an offset within the training data, which has been randomized.
    # Note: we could use better randomization across epochs.
    offset = (step * batch_size) % (train_labels.shape[0] - batch_size)
    # Generate a minibatch.
    batch_data = train_dataset[offset:(offset + batch_size), :]  # mini-batch
    batch_labels = train_labels[offset:(offset + batch_size), :]
    # Prepare a dictionary telling the session where to feed the minibatch.
    # The key of the dictionary is the placeholder node of the graph to be fed,
    # and the value is the numpy array to feed to it.
    feed_dict = {tf_train_dataset : batch_data, tf_train_labels : batch_labels}
    _, l, predictions = session.run(
      [optimizer, loss, train_prediction], feed_dict=feed_dict)
    if (step % 500 == 0):
      print("Minibatch loss at step %d: %f" % (step, l))
      print("Minibatch accuracy: %.1f%%" % accuracy(predictions, batch_labels))
      print("Validation accuracy: %.1f%%" % accuracy(
        valid_prediction.eval(), valid_labels))
  print("Test accuracy: %.1f%%" % accuracy(test_prediction.eval(), test_labels))
Initialized
Minibatch loss at step 0: 3763.713867
Minibatch accuracy: 10.2%
Validation accuracy: 11.6%
Minibatch loss at step 500: 218.475220
Minibatch accuracy: 78.9%
Validation accuracy: 79.3%
Minibatch loss at step 1000: 289.750031
Minibatch accuracy: 78.1%
Validation accuracy: 80.2%
Minibatch loss at step 1500: 171.686737
Minibatch accuracy: 84.4%
Validation accuracy: 81.1%
Minibatch loss at step 2000: 123.215240
Minibatch accuracy: 85.2%
Validation accuracy: 82.1%
Minibatch loss at step 2500: 57.080734
Minibatch accuracy: 89.8%
Validation accuracy: 82.4%
Minibatch loss at step 3000: 63.220982
Minibatch accuracy: 85.9%
Validation accuracy: 83.0%
Minibatch loss at step 3500: 95.992943
Minibatch accuracy: 82.0%
Validation accuracy: 83.1%
Minibatch loss at step 4000: 69.324394
Minibatch accuracy: 86.7%
Validation accuracy: 83.2%
Minibatch loss at step 4500: 75.464554
Minibatch accuracy: 82.0%
Validation accuracy: 83.7%
Test accuracy: 90.4%
Categories
不学无术

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是,假设当前运行到nums[i]的位置,则需要往前看k个数,并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题(问题就转变为:找到第一个>=nums[i]-t的数,判断他是否<=nums[i]+t)。整个算法的时间复杂度是O(N * logk),N为数组长度。
下面代码中用set实现,set是用红黑树实现的。

代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty() || k<1 || t<0)
            return false;
        k++;
        set<int> kNumSet;
        for (int i=0; i<nums.size(); i++){
            if(i >= k){
                int oldVal = nums[i-k];
                kNumSet.erase(oldVal);
            }
            auto l_bound = kNumSet.lower_bound(nums[i] - t);
            if(l_bound != kNumSet.end()){
                if(*l_bound - t <= nums[i])
                    return true;
            }
            kNumSet.insert(nums[i]);
        }
        return false;
    }
};

 

Categories
不学无术

LeetCode 223. Rectangle Area

题目

题目大意是给定两个长方形的坐标,计算他们一起覆盖的面积。
总的思路很简单,Area_A + Area_B – Overlap,具体求重合的面积则需要计算重合区域的两个坐标点。
那么就要分情况讨论,以重合区左下角点的横坐标为例,需要判断点E与横坐标AC的位置关系,即三种:E<A; A<E<C; C<E。

代码

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int pt_M[2], pt_N[2];
        int area_A_or_B = (C-A)*(D-B) + (G-E)*(H-F);
        //pt_M[0]
        if(E<A)
            pt_M[0] = A;
        else if(E<=C)
            pt_M[0] = E;
        else
            return area_A_or_B;
        //pt_N[0]
        if(G<=A)
            return area_A_or_B;
        else if(G<=C)
            pt_N[0] = G;
        else
            pt_N[0] = C;
        //pt_M[1]
        if(F<B)
            pt_M[1] = B;
        else if(F <= D)
            pt_M[1] = F;
        else
            return area_A_or_B;
        //pt_N[1]
        if(H<=B)
            return area_A_or_B;
        else if(H<=D)
            pt_N[1] = H;
        else
            pt_N[1] = D;
        return area_A_or_B - (pt_N[0]-pt_M[0]) * (pt_N[1]-pt_M[1]);
    }
};

 
 

Categories
不学无术

LeetCode 40. Combination Sum II

思路

递归?呵呵
需要判断两个解是否相等,目前没有什么好办法,从boost库里抄了个hash函数过来。

代码

class Solution {
private:
	vector<vector<int>> results;
	size_t hashOfIntVec(const vector<int>& vec) const {
		size_t seed = vec.size();
		for (auto& i : vec) {
			seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		}
		return seed;
	}
public:
	void subCombSum(vector<int>& candidates, int start, int target, vector<int>& path) {
		for (int i = start; i<candidates.size(); i++) {
			if (target - candidates[i] == 0) {
				//bingo!
				path.push_back(candidates[i]);
				vector<int> pathCopy(path);
				sort(pathCopy.begin(), pathCopy.end());
				size_t hashVal = hashOfIntVec(pathCopy);
				bool hasSame = false;
				for (int j = 0; j < results.size(); j++) {
					if (hashVal == hashOfIntVec(results[j])) {
						hasSame = true;
						break;
					}
				}
				if(!hasSame)
					results.push_back(pathCopy);
				path.erase(path.end() - 1);
			}
			else if (target - candidates[i] > 0) {
				path.push_back(candidates[i]);
				subCombSum(candidates, i + 1, target - candidates[i], path);
				path.erase(path.end() - 1);
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	    vector<int> path;
		subCombSum(candidates, 0, target, path);
		return results;
	}
};