Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization

Combinatorial optimization in the face of uncertainty is a challenge in both operational research and machine learning. In this paper, we consider a special and important class called the adversarial online combinatorial optimization with semi-bandit feedback, in which a player makes combinatorial decisions and gets the corresponding feedback repeatedly. While existing algorithms focus on the regret guarantee or assume there exists an efficient offline oracle, it is still a challenge to solve this problem efficiently if the offline counterpart is NP-hard. In this paper, we propose a variant of the Followthe-Perturbed-Leader (FPL) algorithm to solve this problem. Unlike the existing FPL approach, our method employs an approximation algorithm as an offline oracle and perturbs the collected data by adding nonnegative random variables. Our approach is simple and computationally efficient. Moreover, it can guarantee a sublinear (1+ ε)-scaled regret of order O(T^{\frac{2}{3}}) for any small ε>0 for an important class of combinatorial optimization problems that admit an FPTAS (fully polynomial time approximation scheme), in which Tis the number of rounds of the learning process. In addition to the theoretical analysis, we also conduct a series of experiments to demonstrate the performance of our algorithm.     

基于神经正切核的多核学习方法

多核学习方法是一类重要的核学习方法,但大多数多核学习方法存在如下问题：多核学习方法中的基核函数大多选择传统的具有浅层结构的核函数,在处理数据规模大且分布不平坦的问题时表示能力较弱;现有的多核学习方法的泛化误差收敛率大多为O\left(\mathrm{1}/\sqrt[]{n}\right),收敛速度较慢。为此,提出了一种基于神经正切核（NTK）的多核学习方法。首先,将具有深层次结构的NTK作为多核学习方法的基核函数,从而增强多核学习方法的表示能力。然后,根据主特征值比例度量证明了一种收敛速率可达O\left(\mathrm{1}/n\right)的泛化误差界;在此基础上,结合核对齐度量设计了一种全新的多核学习算法。最后,在多个数据集上进行了实验,实验结果表明,相比Adaboost和K近邻（KNN）等分类算法,新提出的多核学习算法具有更高的准确率和更好的表示能力,也验证了所提方法的可行性与有效性。     

Probabilistic robust regression with adaptive weights–a case study on face recognition

Robust regression plays an important role in many machine learning problems. A primal approach relies on the use of Huber loss and an iteratively reweighted l₂ method. However, because the Huber loss is not smooth and its corresponding distribution cannot be represented as a Gaussian scale mixture, such an approach is extremely difficult to handle using a probabilistic framework. To address those limitations, this paper proposes two novel losses and the corresponding probability functions. One is called Soft Huber, which is well suited for modeling non-Gaussian noise. Another is Nonconvex Huber, which can help produce much sparser results when imposed as a prior on regression vector. They can represent any l_q loss () with tuning parameters, which makes the regression modelmore robust. We also show that both distributions have an elegant form, which is a Gaussian scale mixture with a generalized inverse Gaussian mixing density. This enables us to devise an expectation maximization (EM) algorithm for solving the regression model.We can obtain an adaptive weight through EM, which is very useful to remove noise data or irrelevant features in regression problems. We apply our model to the face recognition problem and show that it not only reduces the impact of noise pixels but also removes more irrelevant face images. Our experiments demonstrate the promising results on two datasets.     

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties. We are given a cost graph G=(V,E;c) and an integer k. This problem determines a vertex set S\subseteq V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function. We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.     

Adaptive sparse and dense hybrid representation with nonconvex optimization

Sparse representation has been widely used in signal processing, pattern recognition and computer vision etc. Excellent achievements have been made in both theoretical researches and practical applications. However, there are two limitations on the application of classification. One is that sufficient training samples are required for each class, and the other is that samples should be uncorrupted. In order to alleviate above problems, a sparse and dense hybrid representation (SDR) framework has been proposed, where the training dictionary is decomposed into a class-specific dictionary and a non-class-specific dictionary. SDR puts {\ell }_{\mathrm{1}} constraint on the coefficients of class-specific dictionary. Nevertheless, it over-emphasizes the sparsity and overlooks the correlation information in class-specific dictionary, which may lead to poor classification results. To overcome this disadvantage, an adaptive sparse and dense hybrid representation with nonconvex optimization (ASDR-NO) is proposed in this paper. The trace norm is adopted in class-specific dictionary, which is different from general approaches. By doing so, the dictionary structure becomes adaptive and the representationability of the dictionary will be improved. Meanwhile, a nonconvex surrogate is used to approximate the rank function in dictionary decomposition in order to avoid a suboptimal solution of the original rank minimization, which can be solved by iteratively reweighted nuclear norm (IRNN) algorithm. Extensive experiments conducted on benchmark data sets have verified the effectiveness and advancement of the proposed algorithm compared with the state-of-the-art sparse representation methods.     

ReCSA: a dedicated sort accelerator using ReRAM-based content addressable memory

With the increasing amount of data, there is an urgent need for efficient sorting algorithms to process large data sets. Hardware sorting algorithms have attracted much attention because they can take advantage of different hardware’s parallelism. But the traditional hardware sort accelerators suffer “memory wall” problems since their multiple rounds of data transmission between the memory and the processor. In this paper, we utilize the in-situ processing ability of the ReRAM crossbar to design a new ReCAM array that can process the matrix-vector multiplication operation and the vector-scalar comparison in the same array simultaneously. Using this designed ReCAM array, we present ReCSA, which is the first dedicated ReCAM-based sort accelerator. Besides hardware designs, we also develop algorithms to maximize memory utilization and minimize memory exchanges to improve sorting performance. The sorting algorithm in ReCSA can process various data types, such as integer, float, double, and strings. We also present experiments to evaluate the performance and energy efficiency against the state-of-the-art sort accelerators. The experimental results show that ReCSA has 90.92\times, 46.13\times, 27.38\times, 84.57\times, and 3.36\times speedups against CPU-, GPU-, FPGA-, NDP-, and PIM-based platforms when processing numeric data sets. ReCSA also has 24.82\times, 32.94\times, and 18.22\times performance improvement when processing string data sets compared with CPU-, GPU-, and FPGA-based platforms.     

基于差分表的Blow-CAST-Fish算法的密钥恢复攻击

针对Blow-CAST-Fish算法攻击轮数有限和复杂度高等问题,提出一种基于差分表的Blow-CAST-Fish算法的密钥恢复攻击。首先,对S盒的碰撞性进行分析,分别基于两个S盒和单个S盒的碰撞,构造6轮和12轮差分特征;然后,计算轮函数f₃的差分表,并在特定差分特征的基础上扩充3轮,从而确定密文差分与f₃的输入、输出差分的关系;最后,选取符合条件的明文进行加密,根据密文差分计算f₃的输入、输出差分值,并查寻差分表找到对应的输入、输出对,从而获取子密钥。在两个S盒碰撞的情况下,所提攻击实现了9轮Blow-CAST-Fish算法的差分攻击,比对比攻击多1轮,时间复杂度由2^107.9降低到2⁷⁴;而在单个S盒碰撞的情况下,所提攻击实现了15轮Blow-CAST-Fish算法的差分攻击,与对比攻击相比,虽然攻击轮数减少了1轮,但弱密钥比例由{\mathrm{2}}^{-\mathrm{52.4}}提高到{\mathrm{2}}^{-\mathrm{42}},数据复杂度由2⁵⁴降低到2⁴⁷。测试结果表明,在相同差分特征基础上,基于差分表的攻击的攻击效率更高。     

基于L-Metric重叠子图发现的B细胞表位预测模型

针对现有表位预测方法对抗原中存在的重叠表位预测能力不佳的问题,提出了将基于局部度量（L-Metric）的重叠子图发现算法用于表位预测的模型。首先,利用抗原上的表面原子构建原子图并升级为氨基酸残基图;然后,利用基于信息流的图划分算法将氨基酸残基图划分为互不重叠的种子子图,并使用基于L-Metric的重叠子图发现算法对种子子图进行扩展以得到重叠子图;最后,利用由图卷积网络（GCN）和全连接网络（FCN）构建的分类模型将扩展后的子图分类为抗原表位和非抗原表位。实验结果表明,所提出的模型在相同数据集上的F_{\mathrm{1}}值与现有表位预测模型DiscoTope 2、ElliPro、EpiPred和Glep相比分别提高了267.3%、57.0%、65.4%和3.5%。同时,消融实验结果表明,所提出的重叠子图发现算法能够有效改善预测能力,使用该算法的模型相较于未使用该算法的模型的F_{\mathrm{1}}值提高了19.2%。     

Dimensionality reduction via kernel sparse representation

Dimensionality reduction (DR) methods based on sparse representation as one of the hottest research topics have achieved remarkable performance in many applications in recent years. However, it’s a challenge for existing sparse representation based methods to solve nonlinear problem due to the limitations of seeking sparse representation of data in the original space. Motivated by kernel tricks, we proposed a new framework called empirical kernel sparse representation (EKSR) to solve nonlinear problem. In this framework, nonlinear separable data are mapped into kernel space in which the nonlinear similarity can be captured, and then the data in kernel space is reconstructed by sparse representation to preserve the sparse structure, which is obtained by minimizing a ?1 regularization-related objective function. EKSR provides new insights into dimensionality reduction and extends two models: 1) empirical kernel sparsity preserving projection (EKSPP), which is a feature extraction method based on sparsity preserving projection (SPP); 2) empirical kernel sparsity score (EKSS), which is a feature selection method based on sparsity score (SS). Both of the two methods can choose neighborhood automatically as the natural discriminative power of sparse representation. Compared with several existing approaches, the proposed framework can reduce computational complexity and be more convenient in practice.     

大数据上函数查询解答的复杂度分析

函数查询是大数据应用中重要的操作,查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度,首先,使用映射归约方法将函数查询语言归约到已知的可判定语言,证明了函数查询解答问题的可计算性;其次,使用一阶语言描述函数查询,并分析了一阶语言的复杂度;在此基础上,使用NC-factor归约方法将函数查询类归约到已知的\mathrm{\Pi }{\mathrm{{\rm T}}}_Q-complete类中。证明函数查询解答问题经过PTIME（多项式时间）预处理后,可以在NC（并行多项式-对数）时间内求解。通过以上证明可以推出,函数查询解答问题在大数据上是可处理的。     

基于阵列处理器的最小均方误差检测算法并行设计与实现

针对大规模多输入多输出（MIMO）系统中,最小均方误差（MMSE）检测算法在可重构阵列结构上适应性差、计算复杂度高和运算效率低的问题,基于项目组开发的可重构阵列处理器,提出了一种基于MMSE算法的并行映射方法。首先,利用Gram矩阵计算时较为简单的数据依赖关系,设计时间上和空间上可以高度并行的流水线加速方案;其次,根据MMSE算法中Gram矩阵计算和匹配滤波计算模块相对独立的特点,设计模块化并行映射方案;最后,基于Xilinx Virtex-6开发板对映射方案进行实现并统计其性能。实验结果表明,该方法在MIMO规模为\mathrm{128}\times \mathrm{4}、\mathrm{128}\times \mathrm{8}和\mathrm{128}\times \mathrm{16}的正交相移键控（QPSK）上行链路中,加速比分别2.80、4.04和5.57;在\mathrm{128}\times \mathrm{16}的大规模MIMO系统中,可重构阵列处理器比专用硬件减少了42.6%的资源消耗。     

Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

Secure k-Nearest Neighbor (k-NN) query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas, such as privacy-preserving machine learning and secure biometric identification. Several solutions have been put forward to solve this challenging problem. However, the existing schemes still suffer from various limitations in terms of efficiency and flexibility. In this paper, we propose a new encrypt-then-index strategy for the secure k-NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility). Specifically, we propose a novel algorithm to transform the encrypted database and encrypted query points in the cloud. By indexing the transformed database using spatial data structures such as the R-tree index, our strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted database. To the best of our knowledge, the proposed strategy is the first to simultaneously provide these two properties. Through theoretical analysis and extensive experiments, we formally prove the security and demonstrate the efficiency of our scheme.     

基于广义最大Versoria准则的稀疏自适应滤波算法

针对脉冲噪声干扰环境下传统稀疏自适应滤波稳态性能差,甚至无法收敛等问题,同时为提高稀疏参数辨识的精度的同时不增加过多计算代价,提出了一种基于广义最大Versoria准则（GMVC）的稀疏自适应滤波算法——带有CIM约束的GMVC（CIMGMVC）。首先,利用广义Versoria函数作为学习准则,其包含误差p阶矩的倒数形式,当脉冲干扰出现导致误差非常大时,GMVC将趋近于0,从而达到抑制脉冲噪声的目的。其次,将互相关熵诱导维度（CIM）作为稀疏惩罚约束和GMVC相结合来构建新代价函数,其中的CIM以高斯概率密度函数为基础,当选择合适核宽度时,可无限逼近于l_{\mathrm{0}}-范数。最后,应用梯度法推导出CIMGMVC算法,并分析了所提算法的均方收敛性。在Matlab平台上采用\alpha-stable分布模型产生脉冲噪声进行仿真,实验结果表明所提出的CIMGMVC算法能有效地抑制非高斯脉冲噪声的干扰,在稳健性方面优于传统稀疏自适应滤波,且稳态误差低于GMVC算法。     

Meta-BN Net for few-shot learning

In this paper, we propose a lightweight network with an adaptive batch normalization module, called Meta-BN Net, for few-shot classification. Unlike existing few-shot learning methods, which consist of complex models or algorithms, our approach extends batch normalization, an essential part of current deep neural network training, whose potential has not been fully explored. In particular, a meta-module is introduced to learn to generate more powerful affine transformation parameters, known as \gamma and \beta, in the batch normalization layer adaptively so that the representation ability of batch normalization can be activated. The experimental results on miniImageNet demonstrate that Meta-BN Net not only outperforms the baseline methods at a large margin but also is competitive with recent state-of-the-art few-shot learning methods. We also conduct experiments on Fewshot-CIFAR100 and CUB datasets, and the results show that our approach is effective to boost the performance of weak baseline networks. We believe our findings can motivate to explore the undiscovered capacity of base components in a neural network as well as more efficient few-shot learning methods.     

基于离散哈希的聚类

传统的聚类方法是在数据空间进行,且聚类数据的维度较高.为了解决这两个问题,提出了一种新的二进制图像聚类方法——基于离散哈希的聚类(CDH).该框架通过L21范数实现自适应的特征选择,从而降低数据的维度;同时通过哈希方法将数据映射到二进制的汉明空间,随后,在汉明空间中对稀疏的二进制矩阵进行低秩矩阵分解,完成图像的快速聚类...     

Zero-correlation linear attack on reduced-round SKINNY

At ToSC 2019, Ankele et al. proposed a novel idea for constructing zero-correlation linear distinguishers in a related-tweakey model. This paper further clarifies this principle and gives a search model for zero-correlation distinguishers. As a result, for the first time, the authors construct 15-round and 17-round zero-correlation linear distinguishers for SKINNY-n-2n and SKINNY-n-3n, respectively, which are both two rounds longer than Anekele et al.’s. Based on these distinguishers, the paper presents related-tweakey zero-correlation linear attacks on 22-round SKINNY-n-2n and 26-round SKINNY-n-3n, respectively.     

基于公证人组的跨链交互安全模型

针对公证人机制中存在的公证人节点职能集中以及跨链交易效率较低等问题,提出一种基于公证人组的跨链交互安全模型。首先,将公证人节点分为三类角色,即交易验证者、连接者和监督者,由交易验证组成员打包经过共识的多笔交易成一笔大的交易,并利用门限签名技术对它进行签名;其次,被确认的交易会被置于跨链待转账池中,连接者随机选取多笔交易,利用安全多方计算和同态加密等技术判断交易的真实性;最后,若打包所有符合条件的交易的哈希值真实可靠且被交易验证组验证过,则连接者可以继续执行多笔跨链交易的批处理任务,并与区块链进行信息交互。安全性分析表明,该跨链机制有助于保护信息的机密性和数据的完整性,实现数据在不出库的情况下的协同计算,保障区块链跨链系统的稳定性。与传统的跨链交互安全模型相比,所提模型的签名次数和需要分配公证人组数的复杂度从O(n)降为O(\mathrm{1})。     

基于动作周期退化相似性度量的机械轴健康指标构建与剩余寿命预测

针对工业机器人机械轴健康管理中检测效率和精准度较低的问题,提出了一种机械轴运行监控大数据背景下的基于动作周期退化相似性度量的健康指标（HI）构建方法,并结合长短时记忆（LSTM）网络进行机器人剩余寿命（RUL）的自动预测。首先,利用MPdist关注机械轴不同动作周期之间子周期序列相似性的特点,并计算正常周期数据与退化周期数据之间的偏离程度,进而构建HI;然后,利用HI集训练LSTM网络模型并建立HI与RUL之间的映射关系;最后,通过MPdist-LSTM混合模型自动计算RUL并适时预警。使用某公司六轴工业机器人进行实验,采集了加速老化数据约1 500万条,对HI单调性、鲁棒性和趋势性以及RUL预测的平均绝对误差（MAE）、均方根误差（RMSE）、决定系数（R^{\mathrm{2}}）、误差区间（ER）、早预测（EP）和晚预测（LP）等指标进行了实验测试,将该方法分别与动态时间规整（DTW）、欧氏距离（ED）、时域特征值（TDE）结合LSTM的方法,MPdist结合循环神经网络（RNN）和LSTM等方法进行比较。实验结果表明,相较于其他对比方法,所提方法所构建HI的单调性和趋势性分别至少提高了0.07和0.13,RUL预测准确率更高,ER更小,验证了所提方法的有效性。     

New Polarimetric Feature Parameter for Marine Oil Spill Detection in SAR Images

In order to improve the separability of oil film and other targets, a new polarization feature G based on eigenvalue and eigenvector decomposition is proposed. The new feature can not only reflect the polarization states between different targets in the corresponding set, but also has the ability to describe the statistical information impurities of the different scattering types. If the depolarization state was weaker, the impurities were smaller, then the value of the new polarimetric feature G in the specific region would be lower. Two sets of Radarsat-2 fully Pol-SAR (Polarimetric Synthetic Aperture Radar) data are used to verify the validity of the new feature G. The results show that there is a small eigenvalue in the seawater, a large eigenvalue in the oil film, the eigenvalue of the biofilm is between the oil film and seawater. In addition, the new feature G have better performance than span, \bar{\mathrm{\alpha }}, P, A and CPD in the image contrast, local standard deviation and probability density curve, which proves that the new feature G not only can distinguish bio-film(simulated by plant oil) and crude oil, but also has a good noise suppression ability.     

基于新极化特征参数的SAR海洋溢油检测

为了提升海上油膜与其他目标的可分离程度,提出基于特征值分解的一种新的极化特征G,该特征不仅能够反映集合中不同目标之间的极化状态,还能够描述不同散射类型在统计意义上的不纯度。若某个区域中去极化状态越弱,不纯度越低,则该区域中新极化特征G的值越低。利用两景Radarsat-2全极化SAR (Synthetic Aperture Radar)影像对新特征的有效性进行实验验证。结果表明：海水具有较小的特征值,油膜具有较大的特征值,生物膜的特征值介于两者之间。且与span、\bar{\mathrm{\alpha }}、P、A、CPD等5种经典的极化特征相比,新特征在图像对比度、局部标准偏差及概率密度曲线等三个指标上均有更好的表现,不仅能区分生物膜（植物油模拟）与原油,且具有更好的抑噪性。