typography 0.0.3
Adaptive High Throughput Sampler
License: Apache 2.0 Licence

# Typography [泰否]

<div align="center">
<img src=./docs/imgs/typography_02.png width=30% />
</div>

#### 介绍
这是一个基于Jax与Numpy的自适应高通量采样器，充分利用和协调各种算力资源，自适应的分配采样资源与评分资源，
最终通过采样的方案来求解各种工业领域的实际问题，如QUBO模型的求解等。关于Ising模型或者QUBO模型的建模，
可以参考这篇 [文章](https://arxiv.org/pdf/1302.5843.pdf) 的内容。

虽然项目本身是一个采样器，但是其中比较核心的均匀采样功能直接通过Jax或者Numpy可以实现，
本项目重点在于自适应的适配各种不同的硬件系统，实现高通量的随机采样求解方案，直接对接各种实际生产问题。

#### 软件架构
Typography的核心路径在typography目录下，其中采样模块直接通过__init__.py来集成，
其他模块可以再单独在typography下创建目录。
```bash
typography
├── __init__.py
├── backends
├── models
└── tests
```

#### 安装教程
推荐在虚拟环境下使用pip进行安装：
```bash
pip install typography --upgrade
```
对于新特性有所要求的童鞋也可以下载master分支源代码到本地执行安装：
```bash
python3 setup.py install
```
安装完成后可以执行如下指令以确定是否安装成功：
```bash
python3 -c "import typography as typy"
```
或者使用如下指令查看安装的版本：
```bash
pip show typography
```

#### 使用说明
最简单的案例就是从一个给定的概率分布矢量进行采样：
```python
import typography as typy
import numpy as np

distribution = np.array([1,0,1])
print (typy.sampleArray(distribution, nums=20))

# [2 0 0 0 2 0 0 0 2 2 0 2 0 0 2 2 0 2 2 0]
```
关于`Typography`在具体问题场景中的应用，可以参考这个[背包问题](http://localhost:8890/notebooks/examples/knaspack_simple.ipynb)
的示例，其中部分问题描述与测试结果如下：
##### 了解背包问题
其实背包问题非常的好理解：有一个容量为$c$的背包，需要从$j$个物品中挑选若干个装进背包中，使得最终装在背包里的物品总价值最高。
如果用数学公式来表达就是：
$$
max_{\theta}\sum_jv_j\theta_j
$$

$$
s.t.\ \sum_j\omega_j\theta_j<=c
$$
其中$\omega_j$表示第$j$个物品的重量，$v_j$表示第$j$个物品的价值，而$\theta_j\in\{0,1\}$表示是否选取第$j$个物品装入背包。
##### 背包问题实例
假设我们一共有6个物品，编号分别为[0,1,2,3,4,5]，重量分别为[1,3,5,7,9,11]，价值分别为[2,4,7,8,9,11]，背包总容量为20，最终的目标是找到在背包承重范围内收益最高的配置。有了这些参数之后，原本的硬性约束可以写成如下的形式：
$$
max(2\theta_0+4\theta_1+7\theta_2+8\theta_3+9\theta_4+11\theta_5)\\
$$

$$
s.t.\ \theta_0+3\theta_1+5\theta_2+7\theta_3+9\theta_4+11\theta_5<=20
$$
##### 示例代码
```python
import numpy as np
from jax import numpy as jnp
from jax import vmap
from itertools import product
import typography as typy
from tabulate import tabulate

np.random.seed(0)

nodes = 6
c = 20
theta = jnp.array(list(product([0,1],repeat=nodes)))
x = jnp.array(np.ones((2**nodes,1)))
v = jnp.array([2,4,7,8,9,11])
w = jnp.array([1,3,5,7,9,11])

def get_res(samples, theta, w, v, c):
    return jnp.sum(theta[samples]*w,axis=1)<=c, jnp.sum(theta[samples]*v,axis=1)

opt_x = normalization(res.x)
nums = 16
samples = typy.sampleArray(x, nums=nums)
satisfy, value = get_res(samples, theta, w, v, c)

header=['index']+list(range(nums))
sap = ('samples',)+tuple(samples)
sat = ('satisfy',)+tuple(satisfy)
val = ('value',)+tuple(value)
table=[sap,sat,val]

print(tabulate(table,headers=header))
```
##### 背包问题采样结果
如下表格就是基于`Typography`的采样结果，虽然我们并没有得到最优的策略结果，
但是也在较少的采样次数下得到了较高优化率的可行解:
```bash
index      0    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15
-------  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ----  ----  ----  ----  ----  ----
samples   34   62   39   55   40   13   47   54   13   20    47    50    23     8     3    38
satisfy    1    0    0    0    1    0    0    1    0    1     0     1     0     1     1     1
value     11   30   30   34    9   26   37   23   26   12    37    15    32     7    20    19
```
我们这次采样的结果中，采到的最优结果的总收益是23，采样得到的序号是54，也就是说，将重量分别为1,3,7,9的两个物品放到背包中。虽然我们知道这个解不是最优解，只是一个可行解。这个问题本身的最优解应该是将重量分别为：1,3,5,11的这四个物品放进背包中，最优总收益是24，那么我们所得到的解的优化率约为95.83%。单纯就这个案例来说，我们用25%的采样率就采到了优化率为95.83%的解，这就是基于采样的方法求解组合优化问题的框架。而在这个框架中还有众多的优化点，比如建模的优化，优化概率分布过程的算法设计，以及最终的采样方法，以及我们typography采样的性能，都有较大的优化空间。

#### 参与贡献

1.  Fork 本仓库
2.  新建 Feat_xxx 分支
3.  使用 flake8 和 pytest 检查代码后提交代码
4.  新建 Pull Request 到 develop 分支


#### 公开博客
1. [开源合作招募公告-2021.12.09](https://www.toutiao.com/i7039612619002774046/)
2. [开源第一阶段开发进展-2021.12.11](https://www.toutiao.com/i7040426019408527910/)
3. [关于GPU和CPU上随机采样的简单方法-2021.12.09](https://www.toutiao.com/i7039522596978868773/)