神经网络与深度学习

· · 个人记录

标题很高大上其实内容很简单。就是很入门的东西。

给定一个字符串求值。这个是普及组内容。这里不过多阐述。不会也没关系可以拉到最后。

首先原始的图片噪点很多，给图片降噪。一种简单的降噪方法就是每个点周围 3\times 3 如果 0 更多就是 0 否则就是 1。

然后拉出连通块。这里只拉出宽度 \ge 8 的连通块。当然具体是多少不重要，只要保证拉出的是完整的数字而不是无意义的噪点就行了。

首先我们生成训练数据和测试数据。这部分用 C++ 实现。

首先我们写一个图片类。

#include<bits/stdc++.h>
#define chkmx(a,b) (a)=max((a),(b))
#define chkmn(a,b) (a)=min((a),(b))
#define pc putchar
using namespace std;
mt19937 myrnd(random_device{}());
float rnd(float a,float b){
    return uniform_real_distribution<float>(a,b)(myrnd);
}
const float pi=acos(-1);
template<class T>struct Image{
    int n,m;vector<vector<T>>a;
    Image<T>(int n,int m):n(n),m(m){a=vector<vector<T>>(n,vector<T>(m,0));}
};
Image<char> readfile(string name){
    ifstream file(name);
    int n,m;file>>m>>n;
    string tmp;Image<char>a(n,m);
    for(int i=0;i<n;i++){
        file>>tmp;
        for(int j=0;j<m;j++)
            a.a[i][j]=tmp[j]=='#';
    }
    return a;
}

模拟数字的变换

Image<char>trans(Image<char>img,float M,float Mx,float My,float theta,float Sx,float Sy){
    theta=theta/180*pi;
    int n=img.n,m=img.m;
    Image<char>nwimg(n+30,m+30);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(img.a[i][j]){
        float x=i-1.0*n/2,y=j-1.0*m/2;
        x*=M*Mx,y*=M*My;
        tie(x,y)=make_pair(x*cos(theta)+y*sin(theta),y*cos(theta)-x*sin(theta));
        tie(x,y)=make_pair(x+Sx*y,y+Sy*x);
        int xx=int(x+1.0*n/2+15.5),yy=int(y+1.0*m/2+15.5);
        assert(0<=xx&&xx<nwimg.n);
        assert(0<=yy&&yy<nwimg.m);
        nwimg.a[xx][yy]=1;
    }
    return nwimg;
}

拉出连通块：

Image<char>cut(Image<char>img){
    int n=img.n,m=img.m;
    Image<char>vis(n,m);
    int mnx,mxx,mny,mxy;
    function<void(int,int)>dfs1;
    function<void(int,int,Image<char>&)>dfs2;
    dfs1=[&](int x,int y){
        vis.a[x][y]=1;
        chkmx(mxx,x);chkmn(mnx,x);
        chkmx(mxy,y);chkmn(mny,y);
        for(int xx=max(0,x-1);xx<=x+1&&xx<n;xx++)
            for(int yy=max(0,y-1);yy<=y+1&&yy<m;yy++)
                if(!vis.a[xx][yy]&&img.a[xx][yy])
                    dfs1(xx,yy);
    };
    dfs2=[&](int x,int y,Image<char>&nowimg){
        nowimg.a[x-mnx][y-mny]=1;
        vis.a[x][y]=2;
        for(int xx=max(0,x-1);xx<=x+1&&xx<n;xx++)
            for(int yy=max(0,y-1);yy<=y+1&&yy<m;yy++)
                if(vis.a[xx][yy]==1&&img.a[xx][yy])
                    dfs2(xx,yy,nowimg);
    };
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(img.a[i][j]&&vis.a[i][j]==0){
        mnx=mny=1e9;mxx=mxy=-1e9;
        dfs1(i,j);
        Image<char>nowimg(mxx-mnx+1,mxy-mny+1);
        dfs2(i,j,nowimg);
        if(mxy-mny>=8)return nowimg;
    }
    assert(0);
}

降噪：

Image<char>dnoise(Image<char>img){
    int n=img.n,m=img.m;Image<char>nwimg(n,m);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        int cnt1=0;
        for(int x=i-1;x<=i+1;x++)for(int y=j-1;y<=j+1;y++)
            if(0<=x&&x<n&&0<=y&&y<m&&img.a[x][y])cnt1++;
        nwimg.a[i][j]=(cnt1>=5);
    }return nwimg;
}

为了减小神经网络参数数量，我们缩放到 9\times 9：

const int N=9;
Image<float>work(Image<char>img){
    int n=img.n,m=img.m;
    #define getx(i) (max(n,m)*(i)/N)
    #define gety(i) (m*(i)/N)
    Image<float>nwimg(N,N);
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        int aa=0,bb=0;
        for(int x=getx(i);x<getx(i+1);x++)for(int y=gety(j);y<gety(j+1);y++){
            if(0<=x&&x<n&&0<=y&&y<m&&img.a[x][y])aa++;
            bb++;
        }
        if(bb)nwimg.a[i][j]=1.*aa/bb;
    }return nwimg;
}

最后生成训练数据与测试数据：

signed main(){
    ofstream train_img("train_img"),train_label("train_label");
    for(int i=0;i<16;i++){
        cout<<i<<endl;
        Image<char>img=readfile("font/"+to_string(i)+".txt");
        for(int j=0;j<10000;j++){
            Image<float>res=work(cut(dnoise(trans(img,rnd(.9,1),rnd(.9,1),rnd(.9,1),rnd(-15,15),rnd(-.1,.1),rnd(-.1,.1)))));
            for(int x=0;x<9;x++)for(int y=0;y<9;y++)train_img<<res.a[x][y]<<' ';
            train_img<<endl;train_label<<i<<endl;
        }
    }
    train_img.close();train_label.close();

    ofstream test_img("test_img"),test_label("test_label");
    for(int i=0;i<16;i++){
        cout<<i<<endl;
        Image<char>img=readfile("font/"+to_string(i)+".txt");
        for(int j=0;j<1000;j++){
            Image<float>res=work(cut(dnoise(trans(img,rnd(.9,1),rnd(.9,1),rnd(.9,1),rnd(-15,15),rnd(-.1,.1),rnd(-.1,.1)))));
            for(int x=0;x<9;x++)for(int y=0;y<9;y++)test_img<<res.a[x][y]<<' ';
            test_img<<endl;test_label<<i<<endl;
        }
    }
    test_img.close();test_label.close();
}

接下来写神经网络。神经网络入门可以去看 tensorflow。这里采用最简单的模型，输入为 9\times 9=81 的张量，第一个 Dense 层有 32 个节点，激活函数为 relu，第二个层会返回一个长度为 16 的 logits 数组。我们可以写出如下的代码：

import tensorflow as tf
import numpy as np
print(tf.__version__)
model = tf.keras.Sequential([
    tf.keras.layers.Input(shape=(81)),
    tf.keras.layers.Dense(32, activation='relu'),
    tf.keras.layers.Dense(16)
])

使用 model.summary() 查看模型参数个数。

Model: "sequential"
_________________________________________________________________
Layer (type)                 Output Shape              Param #   
=================================================================
dense (Dense)                (None, 32)                2624      
_________________________________________________________________
dense_1 (Dense)              (None, 16)                528       
=================================================================
Total params: 3,152
Trainable params: 3,152
Non-trainable params: 0
_________________________________________________________________

可以看到有 3,152 个参数。所有参数保留 5 位是能够提交的。

然后确定 损失函数，优化器和指标；

model.compile(optimizer='adam',
              loss=tf.keras.losses.SparseCategoricalCrossentropy(from_logits=True),
              metrics=['accuracy'])

读取训练数据并随机打乱：

traindata = np.loadtxt('train_img')
trainlabel = np.loadtxt('train_label',dtype=np.uint8)
index = [i for i in range(len(traindata))]
np.random.shuffle(index)
traindata = traindata[index]
trainlabel = trainlabel[index]

在训练数据上训练：

model.fit(traindata, trainlabel, epochs=10)
Epoch 10/10
160000/160000 [==============================] - 11s 66us/sample - loss: 2.8253e-09 - accuracy: 1.0000

可以 10 个 epoch 后准确率达到了 100\%。读取测试数据并测试：

testdata = np.loadtxt('test_img')
testlabel = np.loadtxt('test_label',dtype=np.uint8)
print(model.evaluate(testdata,  testlabel, verbose=2))
16000/16000 - 1s - loss: 3.8296e-09 - accuracy: 1.0000

可以看到准确率也是 100\%。

最后输出参数

weights = model.trainable_variables
baoliu = 5
weights_str = ""
for i in range(81):
    for j in range(32):
        weights_str += str(round(float(weights[0][i][j]),baoliu))+' '
for i in range(32):
    weights_str += str(round(float(weights[1][i]),baoliu))+' '
for i in range(32):
    for j in range(16):
        weights_str+=str(round(float(weights[2][i][j]),baoliu))+' '
for i in range(16):
    weights_str+=str(round(float(weights[3][i]),baoliu))+' '
print(weights_str)

最后就是实现要提交的代码了。

计算表达式。最朴素的方法，有括号先算括号，否则先算乘除，再算加减。反正这部分不是瓶颈怎么写都可以。下面给出垃圾实现：

int calc(string str){
    int len=str.size();
    for(int i=0;i<len;i++)if(str[i]=='('){
        int now=1,j=i;while(now){j++;if(str[j]=='(')now++;if(str[j]==')')now--;}
        return calc(str.substr(0,i)+to_string(calc(str.substr(i+1,j-i-1)))+str.substr(j+1));
    }
    vector<int>nums;
    for(int i=0;i<len;){
        int now=0,j=i;int f=1;if(str[j]=='-')f=-1,j++;while(isdigit(str[j]))now=now*10+str[j]-'0',j++;
        i=j;nums.push_back(f*now);if(i<len)nums.push_back(str[i]),i++;
    }
    while(nums.size()>1u){
        bool flag=0;
        for(int i=1;i<(int)nums.size()&&!flag;i+=2)if(nums[i]=='*'||nums[i]=='/'){
            flag=1;vector<int>nw;for(int j=0;j<i-1;j++)nw.push_back(nums[j]);
            if(nums[i]=='*')nw.push_back(nums[i-1]*nums[i+1]);else nw.push_back(nums[i-1]/nums[i+1]);
            for(int j=i+2;j<(int)nums.size();j++)nw.push_back(nums[j]);
            nums=nw;break;
        }
        if(!flag){
            vector<int>nw;
            if(nums[1]=='+')nw.push_back(nums[0]+nums[2]);else nw.push_back(nums[0]-nums[2]);
            for(int i=3;i<nums.size();i++)nw.push_back(nums[i]);
            nums=nw;
        }
    }return nums[0];
}

预测是什么字符：

float weights0[81][32],weights1[32],weights2[32][16],weights3[16];
float dense0[81],dense1[32],dense2[16];
int mymodel(Image<float>input){
    for(int i=0;i<N;i++)for(int j=0;j<9;j++)
        dense0[i*N+j]=input.a[i][j];
    memset(dense1,0,sizeof dense1);memset(dense2,0,sizeof dense2);
    for(int i=0;i<81;i++)for(int j=0;j<32;j++)
        dense1[j]+=dense0[i]*weights0[i][j];
    for(int i=0;i<32;i++)dense1[i]=dense1[i]+weights1[i];
    for(int i=0;i<32;i++)dense1[i]=max(float(0),dense1[i]);
    for(int i=0;i<32;i++)for(int j=0;j<16;j++)
        dense2[j]+=dense1[i]*weights2[i][j];
    for(int i=0;i<16;i++)dense2[i]=dense2[i]+weights3[i];
    pair<float,int>mx(-1e9,0);
    for(int i=0;i<16;i++)chkmx(mx,make_pair(dense2[i],i));
    return mx.second;
}

读取权重：

stringstream weights_str("....");
for(int i=0;i<81;i++)for(int j=0;j<32;j++)weights_str>>weights0[i][j];
for(int i=0;i<32;i++)weights_str>>weights1[i];
for(int i=0;i<32;i++)for(int j=0;j<16;j++)weights_str>>weights2[i][j];
for(int i=0;i<16;i++)weights_str>>weights3[i];

读取，分离数字并获得字符串：

ios::sync_with_stdio(0);cin.tie(0);
cin>>T>>m>>n;string tmp;Image<char>img(n,m);
for(int i=0;i<n;i++){
    cin>>tmp;
    for(int j=0;j<m;j++)img.a[i][j]=tmp[j]=='#';
}
img=dnoise(img);
Image<char>vis(n,m);
int mnx,mxx,mny,mxy;
function<void(int,int)>dfs1;
function<void(int,int,Image<char>&)>dfs2;
dfs1=[&](int x,int y){
    vis.a[x][y]=1;
    chkmx(mxx,x);chkmn(mnx,x);
    chkmx(mxy,y);chkmn(mny,y);
    for(int xx=max(0,x-1);xx<=x+1&&xx<n;xx++)
        for(int yy=max(0,y-1);yy<=y+1&&yy<m;yy++)
            if(!vis.a[xx][yy]&&img.a[xx][yy])
                dfs1(xx,yy);
};
dfs2=[&](int x,int y,Image<char>&nowimg){
    nowimg.a[x-mnx][y-mny]=1;
    vis.a[x][y]=2;
    for(int xx=max(0,x-1);xx<=x+1&&xx<n;xx++)
        for(int yy=max(0,y-1);yy<=y+1&&yy<m;yy++)
            if(vis.a[xx][yy]==1&&img.a[xx][yy])
                dfs2(xx,yy,nowimg);
};
string res="",name="0123456789)/-(+*";
for(int j=0;j<m;j++)for(int i=0;i<n;i++)if(img.a[i][j]&&vis.a[i][j]==0){
    mnx=mny=1e9;mxx=mxy=-1e9;
    dfs1(i,j);
    Image<char>nowimg(mxx-mnx+1,mxy-mny+1);
    dfs2(i,j,nowimg);
    if(mxy-mny>=8)
        res=res+name[mymodel(work(nowimg))];
}

最后输出：

cout<<calc(res)<<endl;

嘤嘤嘤不想写表达式求值怎么办？

可以用 python 的 eval 来计算值。但是 python 的整除是向下取整的，而题目要求向零取整，所以还需要自己实现一个整数类。

system(("python3 -c 'import re\ni=int\nclass I(i):\n  def __add__(a,b):return I(i(a)+i(b))\n  def __sub__(a,b):return I(i(a)-i(b))\n  def __mul__(a,b):return I(i(a)*i(b))\n  def __truediv__(a,b):return I(i(a)/i(b))\nprint(eval(re.sub(r\"(\\d+){1}\",r\"I(\\1)\",\""+res+"\")))'").c_str());

也就是执行：

import re
i=int
class I(i):
  def __add__(a,b):return I(i(a)+i(b))
  def __sub__(a,b):return I(i(a)-i(b))
  def __mul__(a,b):return I(i(a)*i(b))
  def __truediv__(a,b):return I(i(a)/i(b))
print(eval(re.sub(r"(\d+){1}",r"I(\1)","???")))

用 re.sub 把一个数用 I() 包起来。这个会比直接用 c++ 模拟慢一些，但是确实是可以过的。

现在准确度是 100\%，不知道可不可以 9\times 9 变成 7\times 7 之类的。读者可以自己尝试一下。

本当の本当に終わり。