科学空间|Scientific Spaces

今天给大家介绍一篇1962年的论文《Computer Multiplication and Division Using Binary Logarithms》，作者是John N. Mitchell，他在里边提出了一个相当有意思的算法：在二进制下，可以完全通过加法来近似完成两个数的相乘，最大误差不超过1/9。整个算法相当巧妙，更有意思的是它还有着非常简洁的编程实现，让人拍案叫绝。然而，笔者发现网上居然找不到介绍这个算法的网页，所以在此介绍一番。

你以为这只是过时的玩意？那你就错了，前不久才有人利用它发了一篇NeurIPS 2020呢！所以，确定不来了解一下吗？

点击阅读全文...

最近在用VAE处理一些文本问题的时候遇到了对离散形式的后验分布求期望的问题，于是沿着“离散分布 + 重参数”这个思路一直搜索下去，最后搜到了Gumbel Softmax，从对Gumbel Softmax的学习过程中，把重参数的相关内容都捋了一遍，还学到一些梯度估计的新知识，遂记录在此。

文章从连续情形出发开始介绍重参数，主要的例子是正态分布的重参数；然后引入离散分布的重参数，这就涉及到了Gumbel Softmax，包括Gumbel Softmax的一些证明和讨论；最后再讲讲重参数背后的一些故事，这主要跟梯度估计有关。

基本概念

重参数（Reparameterization）实际上是处理如下期望形式的目标函数的一种技巧：
\begin{equation}L_{\theta}=\mathbb{E}_{z\sim p_{\theta}(z)}[f(z)]\label{eq:base}\end{equation}
这样的目标在VAE中会出现，在文本GAN也会出现，在强化学习中也会出现（$f(z)$对应于奖励函数），所以深究下去，我们会经常碰到这样的目标函数。取决于$z$的连续性，它对应不同的形式：
\begin{equation}\int p_{\theta}(z) f(z)dz\,\,\,\text{(连续情形)}\qquad\qquad \sum_{z} p_{\theta}(z) f(z)\,\,\,\text{(离散情形)}\end{equation}
当然，离散情况下我们更喜欢将记号$z$换成$y$或者$c$。

点击阅读全文...

此文很水，高手略过...

Python以它的开发效率而闻名，优秀的开发效率自然意味着它能够用更少的代码实现更多的功能。那么，对于同一个问题，Python的代码能有多简洁？而我们怎么平衡开发效率和运行效率？笔者学了几个月Python，略懂一点，在此班门弄斧一翻。

在此，我们来编程计算
$$\sum_{n=0}^{10} n^2$$
这当然是一道非常简单的习题。按照一般思路，写出来的最自然的代码就是：

s=0
for i in range(11):
    s = s + i**2

print(s)

点击阅读全文...

写在前面：作为离散数学的实验作业，我选择了研究数独。经过测试发现，数独的自动推理还不算难，我把两种常规的推理思路转化为了计算机代码，并结合了随机性推导，得到了一个解题能力还不错的数独程序。事实上，本文的程序还可以进一步优化，以得到更高能力的数独程序（只需要整理一下代码，加上几个循环和判断即可），但是我实在太懒，没有动力继续弄下去了，就这样先和大家分享吧。最后，笔者认为本文的算法是更接近我们的思维的算法。

数独简介

历史

相传数独源起于拉丁方阵（Latin Square），1970年代在美国发展，改名为数字拼图（Number Place）、之后流传至日本并发扬光大，以数学智力游戏智力拼图游戏发表。在1984年一本游戏杂志《パズル通信ニコリ》正式把它命名为数独，意思是“在每一格只有一个数字”。后来一位前任香港高等法院的新西兰籍法官高乐德（Wayne Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。

台湾于2005年5月由“中国时报”首度引进, 且每日连载, 亦造成很大的回响。台湾数独发展协会(Taiwan Sudoku Association, 简称 TSA)亦为世界解谜联盟会员。香港是在2005年7月30日由AM730在创刊时引入数独。中国大陆是在2007年2月28日正式引入数独。北京晚报智力休闲数独俱乐部（数独联盟前身）在新闻大厦举行加入世界谜题联合会的颁证仪式，成为世界谜题联合会的39个成员之一。（引用自“中文维基百科”： http://zh.wikipedia.org/wiki/数独）

点击阅读全文...