169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大[n/2]的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解法1 HashMap

用HashMap存储数字的出现次数,空间复杂度为O(n),同时记录当前最大出现次数和对应的数字,遍历一遍数组,时间复杂度O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public int hashMapCount(int nums[]) {
    // 计数器
    HashMap<Integer, Integer> counter = new HashMap<>();
    // 当前出现最多的数字的出现次数
    int maxAppearance = 1;
    // 当前出现最多的数字
    int majorNum = nums[0];
    // 出现次数大于n/2提前停止
    int earlyStop=nums.length/2;
    for (int i = 0; i < nums.length; i++) {
        if (counter.get(nums[i]) == null) {
            counter.put(nums[i], 1);
        } else {
            int n = counter.get(nums[i]) + 1;
            
            counter.put(nums[i], n);
            if (n > maxAppearance) {
                maxAppearance = n;
                majorNum = nums[i];
                if(n>earlyStop){
                    break;
                }
            }
        }
    }
    return majorNum;
}

解法2 排序法

对数组进行排序, 使用快速排序,时间复杂度O(nlogn).出现次数大于n/2的数一定会出现在排序后的数组索引为n/2的位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Random random = new Random();
public int partition(int[] nums, int start, int end) {
    //用随机数寻找基数
    int idx = random.nextInt(end - start) + start;
    exchange(nums, start, idx);
    //交换基数和首位元素的位置,基数不参与排序
    int pivot = nums[start];
    int left = start + 1;
    int right = end;
    while (left < right) {
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        if (left != right) {
            exchange(nums, left, right);
            right--;
        }
    }
    if (left == right && nums[right] > pivot) {
        right--;
    }
    if (right != start) {
        exchange(nums, right, start);
    }
    //返回基数的位置
    return right;
}

public void exchange(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

public void quickSort(int[] nums, int start, int end) {
    if (start >= end)
        return;
    //排到n/2位置提前停止,返回索引n/2位置的数
    if (end <= nums.length / 2)
        return;
    int middle = partition(nums, start, end);
    quickSort(nums, start, middle - 1);
    quickSort(nums, middle + 1, end);
}

public int findMajorityBySorting(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums[nums.length / 2];
}

解法3 摩尔投票法

由于存在出现次数大于n/2的数,不断删除一对不同的数,剩下的数一定是该数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int majorityElement(int[] nums) {
    return mooreMajorityVote(nums);
}

public int mooreMajorityVote(int nums[]) {
    int count = 0;
    int result = nums[0];
    int n=nums.length/2;
    for (int i = 0; i < nums.length; i++) {
        //当前数和前一数相同则加1
        if (nums[i] == result) {
            count += 1;
            if(count>n)
            {
                break;
            }
        } else {
        //当前数和记录的数不同则抵消,之前相同的数少1个
            count -= 1;
            if (count == 0) {
                if (i + 1 < nums.length) {
                    result = nums[i + 1];
                }
            }

        }
    }
    return result;
}

解法4 随机数法

随机抽取一个数, 记录它的出现次数, 由于众数出现次数大于n/2, 期望次数$\lim\sum_{i}^{\infty}\frac{i}{2^i}=2$, 期望时间复杂度$O(n)$. 最坏情况下时间复杂度为 $O(\infty)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public int count(int[] nums, int n) {
    int m = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == n) {
            m++;
        }
    }
    return m;
}

public int randomPick(int nums[]) {
    Random random = new Random();
    while (true) {
        int candidate = nums[random.nextInt(nums.length)];
        int n = count(nums, candidate);
        if (n > nums.length / 2) {
            return candidate;
        }
    }
}

hpc tutorial

注册

https://nic.csu.edu.cn/info/1146/1789.htm

登录

在终端中输入ssh -p port username@host

简化登录流程

在~/.ssh目录下新建config文件,示例:

1
2
3
4

Host 规则名称
   HostName 网址
   User 用户名
   Port 端口号

保存后即可用ssh 规则名称登录

配置无密码登录

以linux系统为例

1. 在客户端生成密钥,在终端中输入ssh-keygen -t rsa,然后一路回车
2. 将~/.ssh文件夹下的id_rsa.pub中的内容复制到服务器的~/.ssh/authorized_keys中

slurm简介

slurm是集群使用的作业调度系统,申请节点计算资源(cpu与gpu资源)并运行自己的程序需要编写shell脚本实现,即*.sh文件

重要的目录

1. Softwares:/public/software; # anaconda3等软件在这个目录下.
2. Job templates: /public/job_templates; # 样例脚本, 参考信网中心提供的指南来使用样例脚本

常用命令

查看集群所有节点的状态

sinfo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

PARTITION AVAIL  TIMELIMIT  NODES  STATE NODELIST 
cpuQ*        up   infinite      3  down* node[0167,0445,0549] 
cpuQ*        up   infinite      2  drain node[0364,0391] 
cpuQ*        up   infinite      6    mix node[0069,0395,0625,0743,0874-0875] 
cpuQ*        up   infinite    989  alloc node[0001-0068,0070-0166,0168-0363,0365-0390,0392-0394,0396-0444,0446-0548,0550-0624,0626-0742,0744-0873,0876-1000] 
ResQ         up   infinite      1  drain node1009 
ResQ         up   infinite      1    mix node1008 
ResQ         up   infinite     13  alloc node[1002,1004-1007,1011-1012,1017-1022] 
ResQ         up   infinite      7   idle node[1001,1003,1010,1013-1016] 
gpu2Q        up   infinite      5    mix gpu[201,205-208] 
gpu2Q        up   infinite      5  alloc gpu[202-204,209-210] 
gpu4Q        up   infinite      1  down* gpu407 
gpu4Q        up   infinite      3    mix gpu[402,409-410] 
gpu4Q        up   infinite      8  alloc gpu[401,403-406,408,411-412] 
gpu8Q        up   infinite      4    mix gpu[801-804] 
fatQ         up   infinite      1    mix fat09 
fatQ         up   infinite      9  alloc fat[01-08,10]

cpuQ,ResQ,fatQ都为cpu分区,gpu2Q~gpu8Q为gpu分区. 如果想使用gpu,必须将作业提交到gpu分区

STATE

• [ ] down: 节点故障不可用
• [ ] drain: 正在运行的作业不受影响,但不接受新作业
• [x] mix: 节点cpu资源部分已分配,剩下的cpu为idle
• [ ] alloc: 节点所有资源都被占用,新提交的作业将排队
• [x] idle: 当前节点空闲
• [ ] unk: 节点刚刚启动,状态未知

查看自己提交的任务

使用squeue查看JOBID
使用scontrol show job JOBID追踪任务

取消任务

scancel JOBID

更新任务

scontrol update jobid=JOBID …

由于可修改的属性非常多，我们可以借助 SLURM 自动补全功能来查看可修改的内容。 这只需要我们在输入完 JOBID 后空一格并敲两下< TAB >键。

1
2
3
4
5
6
7
8
9
10
11
12
13

account=<account>                      mintmpdisknode=<megabytes>             reqnodelist=<nodes>
conn-type=<type>                       name>                                  reqsockets=<count>
contiguous=<yes|no>                    name=<name>                            reqthreads=<count>
dependency=<dependency_list>           nice[=delta]                           requeue=<0|1>
eligibletime=yyyy-mm-dd                nodelist=<nodes>                       reservationname=<name>
excnodelist=<nodes>                    numcpus=<min_count[-max_count]         rotate=<yes|no>
features=<features>                    numnodes=<min_count[-max_count]>       shared=<yes|no>
geometry=<geo>                         numtasks=<count>                       starttime=yyyy-mm-dd
gres=<list>                            or                                     switches=<count>[@<max-time-to-wait>]
licenses=<name>                        partition=<name>                       timelimit=[d-]h:m:s
mincpusnode=<count>                    priority=<number>                      userid=<UID
minmemorycpu=<megabytes>               qos=<name>                             wckey=<key>
minmemorynode=<megabytes>              reqcores=<count>

查看历史任务

sacct

安装python环境

1. 推荐在当前用户文件夹下创建一个目录并将环境安装到该目录下 command: mkdir ~/envs
2. 使用conda创建一个新的虚拟环境 command: /public/software/anaconda3/bin/conda create —prefix /path/to/your/dir (e.g., ~/envs/)
3. 先用/public/software/anaconda3/bin/conda init命令来初始化一下bash
4. 使用source activate /path/to/your/env来激活环境

编写一个测试脚本

1. 创建py文件

vim ~/hello.py

1
2
3

import torch
print("cuda",torch.cuda.is_available())
print("Hello world!")

注意: 此时在本地运行hello.py, torch.cuda.is_available()的结果为False, 因为登录节点是没有gpu的, 需要通过slurm脚本申请gpu并在计算节点上运行hello.py, 返回值才能为True.

1. 创建slurm脚本文件

vim ~/hello.sh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#!/bin/bash
#SBATCH -J hello                #任务名字
#SBATCH -o hello_%j.out            #保存屏幕输出到这个文件
#SBATCH -e hello_%j.err            #异常退出,则保存屏幕输出到这个文件,可选项,可以只指定*.out文件,则错误也会输出到*.out文件
#SBATCH -t 12:00:00             #最长运行时间, 此处为12小时
#SBATCH -N 1                    #申请节点数
#SBATCH --ntasks-per-node=1     #每个节点分配的任务数
#SBATCH --cpus-per-task=4       #每个任务分配的cpu数
#SBATCH -p gpu2Q                #提交到gpu分区才能申请gpu
#SBATCH -w gpu202               #指定gpu节点,不写则自动分配
#SBATCH --gres=gpu:1            #申请1块gpu
#SBATCH --mail-type=end                   #邮件通知类型start/end/failed, end表示作业结束时邮件通知, 可选项
#SBATCH --mail-user=your_email       #邮件通知邮箱, 可选项
eval "$(/public/software/anaconda3/bin/conda shell.bash hook)"
conda activate /path/to/your/env      #激活环境 
# python ~/prototype/main.py -few 1 -prefix exp1 -form Pre-Train  #运行代码
python ~/hello.py

通知邮件内容

1 2	Subject: Slurm Job_id=33653 Name=prototype Ended, Run time 00:22:18, COMPLETED, ExitCode 0 From: SLURM workload manager <slurm@mu01.localdomain>

1. 提交任务

sbatch ~/hello.sh

1. 查看任务状态

squeue

1
2

JOBID PARTITION     NAME     USER ST       TIME  NODES NODELIST(REASON)
33458      cpuQ prototyp hpc19471 PD       0:00      1 (None) 

scontrol show job 33458

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

JobId=33452 JobName=prototype
   UserId=hpc194711074(1293) GroupId=hpc(500) MCS_label=N/A
   Priority=666 Nice=0 Account=hpc194711074 QOS=normal
   JobState=PENDING Reason=None Dependency=(null)
   Requeue=1 Restarts=0 BatchFlag=1 Reboot=0 ExitCode=0:0
   RunTime=00:00:00 TimeLimit=00:01:00 TimeMin=N/A
   SubmitTime=2020-11-13T20:16:58 EligibleTime=2020-11-13T20:16:58
   AccrueTime=2020-11-13T20:16:58
   StartTime=Unknown EndTime=Unknown Deadline=N/A
   SuspendTime=None SecsPreSuspend=0 LastSchedEval=2020-11-13T20:16:58
   Partition=cpuQ AllocNode:Sid=ln01:86688
   ReqNodeList=(null) ExcNodeList=(null)
   NodeList=(null)
   NumNodes=1-1 NumCPUs=4 NumTasks=1 CPUs/Task=4 ReqB:S:C:T=0:0:*:*
   TRES=cpu=4,node=1,billing=4
   Socks/Node=* NtasksPerN:B:S:C=1:0:*:* CoreSpec=*
   MinCPUsNode=4 MinMemoryNode=0 MinTmpDiskNode=0
   Features=(null) DelayBoot=00:00:00
   OverSubscribe=OK Contiguous=0 Licenses=(null) Network=(null)
   Command=/public/home/hpc194711074/my_slurm.sh
   WorkDir=/public/home/hpc194711074/prototype
   StdErr=/public/home/hpc194711074/prototype/slurm.out
   StdIn=/dev/null
   StdOut=/public/home/hpc194711074/prototype/slurm.out
   Power=
   MailUser=(null) MailType=NONE

1. 查看保存的屏幕输出

cat ~/hello.out

1
2

cuda True
hello world

注意事项

1. 如果python代码中有中文,需要在py文件的第一行加上以下三行代码中的任一行,作用是声明文件的编码格式

1
2
3

#coding=utf-8
#coding:utf-8
#-*- coding:utf-8 -*-

1. 安装pytorch时,cuda版本需要低于10.2,否则可能报以下错误:The NVIDIA driver on your system is too old (found version 10010).

• [x] pytorch 1.7.0 + cuda 10.1 测试通过
• [ ] pytorch 1.7.0 + cuda 10.2 测试不通过

1. bash脚本的单行注释为#,sbatch参数也以#开头,注释sbatch参数的方法如下
   ##SBATCH --job-name=xxx

参考资料

[1] 北大工作站使用指南
[2] Slurm官方文档
[3] 中科大slurm使用指南.pdf

二维卷积

在二维卷积中, 将头实体与尾实体的向量上下拼接, 得到2*100的向量. 第一层卷积层, 使用128个2*1的卷积核从左往右滑动得到维度为1*100*128的输出. 后面的卷积层使用1*1卷积,主要作用是将多个通道的feature_map线性加权求和,以此减少通道数(降维). 这部分主要借鉴ConvKB的思想.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class ProtoNet(nn.Module):
    def __init__(self):
        super(ProtoNet, self).__init__()
        self.encoder_conv2d = nn.Sequential(
        # 第一层输入通道为1,输出通道为128,卷积核大小为(1,2)
        # 第一层卷积操作之后,feature_map=1*100*128
        Conv2d(1, 128, (1, 2)),
        ReLU(),
        # 第二层输入通道为128,输出通道为64,卷积核大小为(1,1)
        # 第二层卷积操作之后,feature_map=1*100*64
        Conv2d(128, 64, (1, 1)),
        ReLU(),
        Conv2d(64, 32, (1, 1)),
        ReLU(),
        Conv2d(32, 1, (1, 1)))

    def forward(self, x):
        batch_size, num_triples, input_length, dim = x.size()
        x = x.view(batch_size*num_triples, 1,
                   x.shape[2], x.shape[3]).transpose(2, 3)
        x = self.encoder_conv2d(x)
        return x.view(batch_size, num_triples, -1)

一维卷积

一维卷积是卷积神经网络在自然语言处理中的常用方法.以I like coding.为例,[I, like, coding]是词汇表,每个单词都用100维的向量表示,则输入是3*100的矩阵.一维卷积是固定住输入矩阵的第二维,卷积核只在第一维上纵向滑动.当句子长度为3时,可以使用2*100的卷积核提取前后两个单词之间的特征. 但是由于头尾实体只有2个单词, 所以卷积核只能设置为2*100, 无法在第一维上滑动.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class ProtoNet(nn.Module):
    def __init__(self):
        super(ProtoNet, self).__init__()
        self.encoder_conv1d = nn.Sequential(
            # 第一层输入通道为100,对应实体嵌入为100维.
            # 有256个卷积核,则输出通道为256,卷积核大小为(2,100)
            # 第一层卷积操作之后,feature_map=1*1*256
            Conv1d(100, 256, 2),
            ReLU(),
            # 第二层卷积操作之后,feature_map=1*1*128
            Conv1d(256, 128, 1))

    def forward(self, x):
        batch_size, num_triples, input_length, dim = x.size()
        x = x.view(batch_size*num_triples,
                   x.shape[2], x.shape[3]).transpose(1, 2)
        x = self.encoder_conv1d(x)
        return x.view(batch_size, num_triples, -1)

基于ConvKB的负样本选择器

• ConvKB的模型是1个2维卷积层+1个全连接层, 其中2维卷积层由n个3*1的卷积核组成,输出维度为1*100*n的feature_map. 全连接层接收卷积层的输入将feature_map的维度降为1, 作为衡量三元组有效性的分数.
• 构建一个卷积神经网络负样本选择器,对负样本实体对打分,选取其中分数最低的作为负样本的代表

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  def support_negative_triples_selector(self, support_negative): # batch_size是任务数,num_triples=few*num_support_negative # num_support_negative是支持集中每个有效三元组对应错误三元组的数量 # length=2,每个实体对由1个头实体和1个尾实体组成 # dim=100,实体嵌入维度为100 batch_size, num_triples, length, dim = support_negative.size() support_negative_score = self.convkb( support_negative.view(-1, length, dim)) # (batch_size,few,num_sn/few,1) support_negative_score = support_negative_score.view( batch_size, self.few, self.num_support_negative, 1) # 对每个正样本对应的n个负样本按分数增序排列 support_negative_score_sorted = torch.sort( support_negative_score, dim=2, descending=False) # 取分数最低的 (batch_size,few,1) choices = support_negative_score_sorted.indices[:, :, 0, :] idx_1 = torch.LongTensor( np.arange(batch_size).repeat(self.few)).to(self.device) idx_2 = torch.LongTensor( np.tile(np.arange(self.few), batch_size)).to(self.device) idx_3 = choices.view(batch_size*self.few).to(self.device) support_negative = support_negative.view( batch_size, self.few, self.num_support_negative, 2, -1) support_negative = support_negative[idx_1, idx_2, idx_3] support_negative = support_negative.view( batch_size, self.few, 2, self.dim) return support_negative

实验结果

1

dataset=NELL es_p=5

1

dataset=Wiki    es_p=1

1

dataset=Wiki    es_p=5

1

dataset=covid19    es_p=1

结论

1. 目前尝试用2种卷积替换全连接层,效果并未取得提升.
2. 基于卷积神经网络的负样本选择器可能需要放在背景知识图谱中单独训练效果才能更好.
3. 在新冠肺炎数据集上,Prototype的效果好于MetaR.

• prototype

• support_positive: 支持集中的n个正确三元组$(h,r,t)$
• support_negative: 支持集中的n个错误三元组$(h,r,t’)$
• query_positive: 查询集中的k/1个正确三元组$(h,r,t)$,k对应训练集,1对应验证/测试集
• query_negative: 支持集中的k/m个错误三元组$(h,r,t’)$,k对应训练集,m对应验证/测试集
• support_positive=>全连接层=>正类的向量表示
• support_negative=>全连接层=>负类的向量表示

超参数

• batch_size = 128
• eval_epoch = 1000 每训练n个epoch后验证一次
• early_stop_patience (es_p) = 1 验证集上的结果连续低于最好结果n次后停止训练并用最好的模型进行测试.该参数与epoch数正相关.验证结果可能在连续k次低于最好情况下在第k+1次验证时超过最好值, 所以可以通过增大es_p训练出拟合度更高的模型,负面影响是延长了训练时间.

实验结果

dataset=NELL es_p=1

dataset=NELL es_p=5

dataset=Wiki es_p=1

分析

1. TransE在5-shot情况下,在NELL数据集上效果最好,但是在Wiki数据集上,TransE在1-shot和5-shot条件下的效果都差于prototype
2. prototype方法收敛速度更快,可以通过更少的epoch达到更好的效果
3. prototype在不finetune的情况下比MetaR更好. MetaR使用hinge-loss,在不finetune条件下,损失只能降低到0.75左右. prototype使用交叉熵损失,在不finetune条件下,损失也能一直降低

华容一中校友会后台开发文档

数据字典

• 数据库名: alumni_association

alumni

class

level

alumni_class

grade

association

invitation

notification

card

help_registration

后台开发框架

SpringBoot+Mybatis+shiro
SpringBoot: Spring的简化版,通过大量的预定义配置简化Spring的配置
Mybatis: ORM框架, 负责与数据库交互
shiro: 权限控制框架,基于角色分配权限(暂未实现)

关键工具

jwt: 根据微信提供的openid和session_key生成token.将token加入到所有请求的header中,用于鉴权,判断是否为非法请求
lombok: 简化代码,自动生成POJO类的getter和setter方法
Tomcat: 可以处理动态资源的应用服务器.项目打成war包后部署到Tomcat下运行

设计模式

MVC架构

• model
  service层
  UserService
  AuthorizationService
  dao层
  AlumniMapper
  AlumniClassMapper
  NotificationMapper
  CardMapper

• view
  web端
• controller
  MainController
  UserController
  AuthorizationController

  接口url

• 目前正在将原java后台用springboot框架重构, 原api部分为php, 现在统一为java, 功能已迁移大约60%.
• 使用springboot框架开发新后台性能更好,加权限控制更方便(原后台没有编写权限管理的代码,权限都由前端控制,存在安全隐患).接口url(功能说明,参数说明,调用方法)待补充…

  1 2	举例: 原后台按不同条件查询校友信息需要通过多个不同的请求地址,现在可以统一为一个请求地址,根据传入的参数查找相应的内容

遗留bug

• Bug1(已解决): 发送邮件需要先通过官方api获取微信的access_token,api每天最多请求2000次,超过次数将不能再发送邮件.
• 解决方法: 每次获取的token有2个小时的过期时间,需要保存该token防止重复请求,设置一个springboot的定时任务.

  请求说明

• host
  https://www.csubigdata.com/xyh

  常量请求

• GET /years
• 获取所有年份
• 返回值
  数组
  [1999,2000,…,2029]
• GET /classes
• 获取所有班级
• 返回值: json数组

• GET /recent/invitation
• 获取最近一段时间的邀请记录
• 请求参数

• 返回值: json数组

• GET /rank/help
• 帮填信息排名,返回数据按邀请数递减排列
• 返回值: json数组

• GET /rank/invitation
• 邀请排名
• 返回值: json数组

登录

• GET /user/openid
• 获取openid
• 请求参数

• 返回值

名片相关

• POST /user/card/apply
• 申请交换名片
• 请求参数

• POST /user/card/agree
• 同意交换名片
• 请求参数

• POST /user/card/reject
• 拒绝交换名片
• 请求参数

• POST /user/cards
• 获取所有名片
• 请求参数
  | 参数 | 类型 | 描述 |
  | ———— | —— | ———— |
  | alumniId | int | 发起者id |
• 返回值: json数组
  [card1,card2,…]

• POST /user/notifications
• 获取所有名片交换消息
• 请求参数

• 返回值: json数组

• POST /user/notification/num
• 获取名片交换消息数
• 返回值: json数组

用户信息相关

• GET /user/info
• 获取个人信息
• POST /user/insert
• 录入信息
• PUT /user/update
• 修改信息
• GET /user/captcha
• 获取验证码

  二维码分享

• GET /user/qrcode
• 生成二维码

  班级相关

• POST /class/insert
• 录入班级信息
• PUT /class/update
• 修改班级信息

  查询信息

• GET /query/alumnus
• 查询用户信息
• 请求参数

• 返回值: json数组

个人成就相关

• GET /user/invitation
• 获取用户邀请记录
• 请求参数

• 返回值: json对象

• GET /user/help
• 获取用户帮填记录
• 请求参数

• 返回值: json对象

• GET /user/invitation/num
• 邀请人数
• 请求参数

• 返回值: json对象

• GET /user/help/num
• 帮填人数
• 请求参数

• 返回值: json对象

权限相关

统计与排名

• GET /auth/count/branch/{branch}
• 统计各个分会人数
• 返回值: json对象

• GET /auth/count/grade/{gradeId}
• 统计各个年级分会人数
• 返回值: json对象

• GET /auth/count/class/{classId}
• 统计各个班级人数
• 返回值: json对象

• GET /auth/count/period
• 统计某一段时间的人数
• 请求参数

• 返回值: json对象

• GET /count/everyday
• 所有班级每天新加入人数排名,返回值按人数递减排列
• 返回值: json对象

修改用户

• DELETE /auth/alumni
• 请求参数

错误识别码

• 200 查询成功
• 500 网络繁忙

链路预测与知识图谱补全的关系

知识图谱补全任务是根据知识图谱中的已知三元组预测未知的三元组.
对于知识图谱, 知识图谱补全和链路预测是同一种概念,可以进一步划分成实体预测和关系预测.

1. 实体预测 (entity prediction), 又分为(h,r,?)和(?,r,t), 知识图谱表示学习一般都通过实体预测任务评测模型好坏
2. 关系预测 (relation prediction), 即(h,?,t), 当数据集中的关系种数很少时, 预测难度较低

少样本实体预测任务的目的是希望让模型根据一种新的关系的少量三元组去预测这种关系的其他三元组
TransE学习到的实体嵌入在空间中的相对位置关系就可以理解为两个实体之间的关系, 用于训练实体的相关三元组越多,实体之间相对位置关系(t-h)代表它们之间的关系就越准确.

TransE和少样本知识图谱补全的区别

目标任务不同

• TransE的任务是学习知识图谱中实体和关系的向量表示,通过预测三元组中的尾实体是什么(h,r,?)来评测向量表示的好坏.
• 少样本知识图谱补全的任务是已知关系$r$的$n$个三元组中的头尾实体对$\{(h,t)|(h,r,t)\in G\}$. $h,t$的向量已知, $r$的向量未知. 预测其他关于$r$的三元组中的尾实体是什么(h,r,?).

数据集不同

1. TransE的验证/测试集中的实体和关系全都包含在训练集中
2. TransE在训练集上训练后得到了所有实体和关系的嵌入
3. 少样本数据集分成训练/验证/测试集和背景知识图谱,训练/验证/测试集的实体嵌入可以通过在背景知识图谱上预训练得到
4. 少样本训练/验证/测试集的关系集合的交集为$\varnothing$,
5. TransE在验证/测试时,分数计算公式$||h+r-t||_2$中的$h,r,t$都是已经训练好的向量.
6. 在少样本任务中,$||h+r-t||_2$中的$h,t$是预训练或随机初始化的向量,$r$则是根据支持集得到的向量.

• 知识图谱表示学习常用数据集

| dataset | #relation | #entity | # triple(train/valild/test)    |
| ------- | --------- | ------- | ------------------------------ |
| WN11    | 11        | 38696   | 112581    2609    10544        |
| WN18    | 18        | 40943   | 141442     5000     5000       |
| FB13    | 13        | 75043   | 316232     5908     23733      |
| FB15K   | 1345      | 14951   | 483142     50000     59071     |
| FB1M    | 23382     | 1\*10^6 | 17.5\*10^6    50000     177404 |
| FB5M    | 1192      | 5385322 | 19193556     5000     59071    |

• FB15K
  • 训练/验证/测试集之间实体/关系交集数

|       | train (e) | valid (e) | test (e) | train (r) | valid (r) | test (r) |
| ----- | --------- | --------- | -------- | --------- | --------- | -------- |
| train | 14951     | 13292     | 13584    | 1345      | 916       | 961      |
| valid |           | 13292     | 12568    |           | 916       | 821      |
| test  |           |           | 13584    |           |           | 961      |

• FB13
  • 训练/验证/测试集之间实体/关系交集数

|       | train (e) | valid (e) | test (e) | train (r) | valid (r) | test (r) |
| ----- | --------- | --------- | -------- | --------- | --------- | -------- |
| train | 75043     | 6158      | 18862    | 13        | 7         | 7        |
| valid |           | 6158      | 3208     |           | 7         | 7        |
| test  |           |           | 18862    |           |           | 7        |

• NELL-One
  • 训练/验证/测试集之间实体/关系交集数

|       | train (e) | valid (e) | test (e) | train (r) | valid (r) | test (r) |
| ----- | --------- | --------- | -------- | --------- | --------- | -------- |
| train | 6407      | 451       | 847      | 51        | 0         | 0        |
| valid |           | 712       | 135      |           | 5         | 0        |
| test  |           |           | 1639     |           |           | 11       |

• 背景知识图谱与训练/验证/测试集之间实体/关系交集数
  背景知识图谱与训练/验证/测试集之间的关系不相交,背景知识图谱中的实体集合包含训练/验证/测试集中的所有实体

  1 2 3 4 5 6

  background train entity 68544 6407 6407 background valid entity 68544 712 712 background test entity 68544 1639 1639 background train relation 291 51 0 background valid relation 291 5 0 background test relation 291 11 0

  通过以上3个表格可以看出,虽然TransE论文的实验同样是预测尾实体,但是数据集的切分方式与少样本数据集不同. TransE论文的实验效果依赖于训练集得到的实体嵌入和关系嵌入,少样本的实验效果依赖于背景知识图谱得到的实体嵌入.如果去掉背景知识图谱,采用随机初始化的方式进行少样本实验,实验效果依赖于通过对训练集的实体进行finetuning, 然而finetuning对实验效果是否有提升取决于训练集与验证集/测试集中的实体交集的个数,交集越大,效果越好. 在删除训练集中与测试集中的实体交集的条件下,MetaR效果下降得非常明显,但是TransE的结果不受影响,因为TransE不依赖finetuning,直接使用预训练的实体嵌入预测尾实体.

1
2
3
4
5
6

MetaR 5-shot batch_size=128
删除后 MRR: 0.098      Hits@10: 0.235  Hits@5: 0.153   Hits@1: 0.043
删除前 MRR: 0.189      Hits@10: 0.303  Hits@5: 0.250   Hits@1: 0.113
TransE 5-shot
删除前 MRR: 0.225	Hits@10: 0.389	Hits@5: 0.300	Hits@1: 0.144
删除后 MRR: 0.225	Hits@10: 0.389	Hits@5: 0.300	Hits@1: 0.144

目前的想法

计算分数的方式

• 融合邻居信息相似度与关系相似度
• 设n是实体e的邻居的个数,邻居是关系与尾实体的拼接,邻居的聚合方式有2种,第1种是每个邻居乘上其关系对应的tfidf值再求和,第2种是先把邻居中的关系和实体乘上各自的tfidf再拼接,多个邻居再相加求和. $$e_{neighbor}=\sum_{i=1}^{n}{w_i}N^{e}_{i}\\w_i=TFIDF(r_i)\\N_i=concat(r_i,t_i) \tag{w1}$$ $$e_{neighbor}=\sum_{i=1}^{n}{N_i^{e}}\\w_i=TFIDF((r/t)_i)\\N_i=concat(w_{r_i}r_i,w_{t_i}t_i) \tag{w2}$$
• 综合头实体和尾实体邻居信息的方式有3种 $$neighbor=concat(h_{neighbor},t_{neighbor}) \tag{n1}$$ $$neighbor=t_{neighbor}-h_{neighbor} \tag{n2}$$ $$neighbor=t_{neighbor}+h_{neighbor} \tag{n3}$$
• 最后计算分数的方式有两种,第1种是计算查询集头尾实体与支持集关系的欧式距离,再加上查询集与支持集实体对邻居信息的余弦相似度.第2种是把计算查询集头尾实体与支持集关系的相似度的方法换成余弦相似度.实验结果表明余弦距离效果更好. $$score=||h_q+r_s-t_q||_2+cos(query_{neighbor},support_{neighbor}) \tag{s1}$$ $$score=cos((h_q+r_s),t_q)+cos(query_{neighbor},support_{neighbor}) \tag{s2}$$

比较结果看出同时对邻居中的实体和关系加权效果更好,(尾实体邻居向量-头实体邻居向量)效果更好,使用余弦相似度比欧式距离更好.

5-shot条件下,加入邻居信息的效果差于不加.
1-shot条件下,加入邻居信息的效果好于不加.

1
2
3

1-shot
否  MRR: 0.144  Hits@10: 0.235  Hits@5: 0.178   Hits@1: 0.089
是  MRR: 0.150  Hits@10: 0.252  Hits@5: 0.186   Hits@1: 0.106

不finetune情况下,TransE效果好于MetaR和GMatching

最近的尝试

• Prototype Network with squared euclidean distance

• GMatching+MetaR

  1 2 3 4

  通过GMatching融合邻居信息并计算匹配分数,同时用MetaR计算匹配分数 score=GMatching_score(qry,spt)+MetaR_score(qry,spt) --max_neighbor 50 --batch_size 128

• 华为比赛
• 知识图谱研究
  • Formulation
  • TransE
  • TF-IDF
  • Concatenate
  • Experiments
    • 条件说明
    • 实验结果
    • 对比分析
  • 想法

华为比赛

• 由于华为NAIE平台操作不便,所以先从清华netman智能运维实验室的网站上下载了一个KPI异常检测数据集,其规模和格式均与比赛数据集基本相同.在该数据集上使用light-gbm(基于决策树)搭建了一个模型. 具体见代码kpi_anomaly.ipynb
• 比赛数据集更新, 训练集数据条数从3800+增加到30000+,测试集从500+增加到3000+

知识图谱研究

Formulation

• 设训练/验证/测试集中的三元组对应的知识图谱为$G=\{(h,r,t)|h,t \in E,r \in R\}$, $G$的背景知识图谱$G_b=\{(h,r,t)|h,t \in E_b,r \in R_b\}$, $E$和$E_b$是实体集,$R$和$R_b$是关系集. 其中$E \subset E_b$, $R \cap R_b=\varnothing$.
• 对$e \in E_b$, $e$的邻居集合为$N_e$, 邻居个数为$|N_e|$, 有$N_e=\{(r_i,e_i)|(e,r_i,e_i) \in G_b\}$, 对$n_i \in N_e$,$n_i= (r_i,e_i)$.
• TransE的训练目标: $\forall (h,r,t) \in G$, 有$v_h+v_r \approx v_t$
• 设任务集合为$T$, 对$task \in T$, $task=(support,query)$, $support=\{(h,r,t)|(h,r,t) \in G\}$,$query=\{(h,r,t),(h,r,t’)|(h,r,t)\in G,(h,r,t’) \notin G\}$. $|support|$为hyper-parameter, $|support|=1$表示one-shot. 在$Meta_{train}$阶段, query中的正确三元组与错误三元组的个数相等. 在$Meta_{test}$阶段,正确三元组个数为1,错误三元组数量为候选集实体数量减1, 即$|candidates|-1$

TransE

用transe表示不使用任何神经网络模型,直接通过预训练的实体嵌入完成预测任务

1. $\forall task\in T$, 其中$task=(support,query)$, 设$r_{s}$为根据$support=\{(h,r,t)|(h,r,t) \in G\}$计算得到的关系嵌入表示,$n$为$support$中三元组的个数.

   $$r_s=\frac{1}{n}\sum_{i=1}^n(t_i-h_i)$$

2. 将$r_s$迁移到$query$中,计算每个三元组的$score$, 用$score^+$和$score^-$分别表示有效三元组(正样本)和无效三元组(负样本)的得分.

   $$score=||h+r_s-t||_2$$

3. 在$Meta_{test}$阶段, 对query中所有三元组的score排名, 根据$score^+$的排名计算评测指标(MMR,Hits@10,Hits@5,Hits@1). 在$Meta_{train}$阶段, 则根据query中所有三元组的score计算Margin Loss.

1
2
3
4
5

def rank(positive_score,negative_score):
    scores=concat(negative_score,positive_score)
    sort(scores)
    rank=scores.indexof(len(scores)-1)
    return rank

TF-IDF

通过计算实体e的所有邻居的tfidf值对邻居的向量表示进行加权求和,作为e的初始向量

1. 设训练/验证/测试集中的三元组对应的知识图谱为$G=\{E,R\}$,$G$的背景知识图谱$G_b=\{E_b,R_b\}$, 其中$E \subset E_b$,$R \cap R_b=\varnothing$. 根据$G_b$中的三元组计算$e_i \in E_b$的邻居$N_i$,设$N=\{N_1,N_2,…,N_i\}$为所有邻居信息的集合, 其中$N_i=\{(r_1,e_1),(r_2,e_2),…,(r_k,e_n)|k\in range(|R_b|),n \in range(|E_b|)\}$, 计算$N_i$中$(r_k,e_n)$的$r_k$的TF-IDF值,将其作为$e_i$的邻居$(r_k,e_n)$的权重. $$TF_{r_k}=\frac{r_k在N_i中的出现次数}{N_i中r的个数}$$

1. 用第j个邻居$n_j=(r_k,e_n)$的$r_k$的$tfidf$值作为$n_j$的权重$w_j$,对邻居的向量$v_{n_j}$进行加权求和作为$e_i$的向量$v_{e_i}$,标记为pre-train=tfidf-neighbor $$v_{n}=concat(v_r,v_t)$$ $$v_{e_i}=\sum_{j=1}^{|N_i|}{w_j v_{n_j}}$$ 也可以将每个邻居的TF-IDF组成的向量作为e的向量.标记为pre-train=tfidf $$v_{e_i}=[w_1,w_2,...,w_j]$$ 也可以将每个邻居中关系向量的TFIDF加权之和作为e的向量.标记为pre-train=tfidf-relation $$v_{e_i}=\sum_{j=1}^{|N_i|}{w_j v_{r_j}}$$

Concatenate

通过拼接三元组中头实体和尾实体的向量得到实体对的向量,在预测过程中,比较support与query中实体对的余弦相似度.

1. 对于一个三元组$triplet$$(h,r,t)$,$v_{triplet}=concat(v_h,v_t)$. 计算$v_{spt}$与query中所有三元组向量的余弦距离. $$v_{spt}=\frac{1}{n}\sum_{i=1}^{n}{v_{triplet_i}}$$ $$score=cosine(v_{spt},v_{triplet}), triplet \in query$$
2. 根据query中有效三元组的分数排名计算评测指标.

Experiments

条件说明

• cosine表示用余弦距离替换欧式距离计算score
• transe表示用TransE中说明的方法做预测
• concat表示用concat中说明的方法做预测
• average表示将TF-IDF中的$w_j$替换为$\frac{1}{n}$
• finetune表示允许根据损失函数更新实体嵌入
• random表示随机初始化实体嵌入
• pre-train=transe表示用transe初始化实体嵌入
• pre-train=tfidf表示用邻居关系的tfidf向量$[w_1,w_2,…,w_j]$作为初始实体嵌入
• pre-train=tfidf-relation表示用邻居关系向量$v_r$的加权之和作为初始实体嵌入,权重是关系的tfidf
• pre-train=tfidf-neighbor表示用邻居向量$concat(v_r,v_t)$的加权之和作为初始实体嵌入,权重是关系的tfidf
• pre-train=average-neighbor表示用邻居向量$concat(v_r,v_t)$求和平均作为初始实体嵌入
• attention表示在n-shot条件下(n>1)用attention机制聚合support中的$v_r$
• batch_size=4, 在不finetune条件下,模型为基本的数学计算,所以速度很快

实验结果

对比分析

1. [1, 2, 3, 4] 表明使用attention,更适合用欧式距离计算分数而不是cosine. 不使用attention,则更适合用cosine而不是用欧式距离.
2. [8, 9] 表明其他方法需要高于0.11才能说明模型起正面作用. 5-shot结果比1-shot结果差, 初步分析是因为预测是针对query的, query中部分能预测正确的三元组在5-shot条件下被放入了support中,而这些三元组对评测指标的贡献较大,导致5-shot比1-shot差.
3. [5] 表明邻居信息的tfidf值对部分数据起正面作用, 即考虑不同实体的邻居信息中的关系种类的相似性对预测有正面作用
4. [13, 14, 15, 16] 表明不加权的邻居信息起负面作用. 加权的邻居信息对部分数据起正面作用, 即考虑不同实体的邻居信息之间的语义相关性对预测有正面作用.

想法

1. 将tf-idf加权的邻居信息拼接在实体的原始向量后,计算匹配分数时分别计算查询集与支持集之间关系的相似度与实体邻居信息的语义相似度. $$score=||h+r_s-t||_2+cosine(N_{spt},concat(N_h,N_t))$$
2. 目前只考虑了关系的tfidf作为一个邻居的权重,还可以考虑尾实体的tfidf. $$v_{e_i}=\sum_{j=1}^{|N_i|}w_{r_i}concat(r_i,t_i) \tag{1}$$ $$v_{e_i}=\sum_{j=1}^{|N_i|}concat(w_{r_i}r_i,w_{t_i}t_i)\tag{2}$$
3. 不同实体的邻居信息可以看作一个序列数据, 通过Seq2Seq与Auto-Encoder(自编码器)结合的方式编码邻居信息,通过目标函数学习不同邻居的权重.