Table of Content

15 June 2018, Volume 22 Issue 2

Previous Issue    Next Issue

A review of multi-instance learning research

TIAN Yingjie, XU Dongkuan, ZHANG Chunhua

2018, 22(2):  1-17. 

Asbtract ( 9716 )   PDF (9313KB) ( 900 )  

Related Articles | Metrics

Multi-instance learning is  a special kind of machine learning problem, has received extensive attention and been researched on in recent years. Many different types of multi-instance learning algorithms have been proposed to deal with practical problems in various fields. This paper reviews the algorithm research and application of multi-instance learning in detail, introduces various background assumptions， and introduces multi-instance learning from three aspects: instance level, bag level, and embedded space. Finally we provide the algorithm extensions  and major applications in several areas.

An inexact parallel alternating direction method for structured variational inequalities

FENG Junkai, ZHANG Haibin, QIN Yuan, ZHANG Kaili

2018, 22(2):  18-30.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.002

Asbtract ( 1514 )   PDF (585KB) ( 228 )  

Related Articles | Metrics

This paper considers the monotone variational inequality problems with two separable blocks subject to linear coupling constraints. Problems of this type arise in many contemporary applications including traffic assignment and economics. Based on its favorable separable structure, splitting type methods have been studied. In this paper, we introduce a new inexact parallel alternating direction method with a substitution to solve this family of problems. At each iteration, one can get a predictor by using projection in  parallel fashion, then corrects the predictor to generate the new iterate. For the proposed algorithm, we prove its convergence under mild conditions via the analytic framework of contractive type methods. Some numerical results  are reported to support the efficiency of the new method. Moreover,  the proposed method can be extended to solve the variational inequality problems with multi-blocks.

A survey on the initialization methods for the k-means algorithm

XU Dachuan, XU Yicheng, ZHANG Dongmei

2018, 22(2):  31-40.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.003

Asbtract ( 1223 )   PDF (583KB) ( 246 )  

Related Articles | Metrics

The k-means problem which is one of the classical NP-hard problems keeps attracting wide attention in combinatorial optimization and computer science area since been proposed. Given a set of observations consisting of N d-dimensional real vectors, the objective is to partition the N observations into k(\leqslant N) sets, so as to minimize the within-cluster sum of squares, where the center of a cluster is defined as the mean of all the observations in it. As one of the heuristic algorithms for solving k-means problem, k-means algorithm is quite popular in practice because of its excellent perform of convergence. The k-means algorithm can be described as: given initial solution for k-means problem, repeat assignment (assign observations to its nearest center) and update (compute the new centers in the new clusters) step until convergence to a solution. Although the algorithm is usually considered as linearly convergency, its shortcomings are obvious. The k-means algorithm is unable to ensure the global optimality and the output is rely badly on the choice of initial solutions. Therefore, variants of initialization methods are proposed to improve the performance of the k-means algorithm. In this paper we mainly filter and list some of them for readers.

Two factorizations for fourth-order tensors based on different tensor multiplications

XU Jiaojiao, YANG Zhixia

2018, 22(2):  41-54.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.004

Asbtract ( 1158 )   PDF (651KB) ( 247 )  

Related Articles | Metrics

In this paper, two factorizations for fourth-order tensors based on different multiplications of the fourth-order tensors are investigated. One is, called as F-TD, based on the fourth-order tensor multiplication (F-product). Another is, the fourth-order tensor multiplication and decomposition are defined, called as B-product and FT-SVD, based on the t-product of the third-order tensor multiplication.  Meanwhile, two tensor approximation theorems are present using two  decomposition methods. Finally, three numerical examples are given to demonstrate the accuracy and the feasibility of our proposed methods.

From support vector machine to nonparallel support vector machine

SHAO Yuanhai, YANG Kaili, LIU Mingzeng, et al.

2018, 22(2):  55-65.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.005

Asbtract ( 9515 )   PDF (1352KB) ( 577 )  

Related Articles | Metrics

Nonparallel support vector machine (NSVM) is the extension of support vector machine (SVM), and it has been widely studied in recent years. The NSVM constructs nonparallel support hyperplanes for each class, which can describe the distribution of different classes, thus applicable to wider problems. However, the study of the relationship between NSVM and SVM is rarely. And to now, there is no NSVM could be degenerate or equivalent to the standard SVM. We start from this view of point, and construct a new NSVM model. Our model not only can be reduced to the standard SVM, preserves the sparsity and kernel scalability, but also can describe the distribution of the different classes. At last, we compare our model with start-of-art SVMs and NSVMs on benchmark datasets, and confirm the superiority of proposed NSVM.

An intrinsic accelerated projection gradient algorithm for semi-supervised metric learning

YANG Di, BAI Yanqin, LI Qian

2018, 22(2):  66-78.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.006

Asbtract ( 1098 )   PDF (5001KB) ( 174 )  

Related Articles | Metrics

In this paper, we consider a class of semi-supervised metric learning problems. Due to the explosion in size and complexity of datasets, it is increasingly important to consider the sparse of metric learning. We add the constraint of sparse for the model of semi-supervised metric learning. To be easy to deal with the sparse constraint, we apply the Frobenius norm to define the sparse and transform it into the objective function of model by using the penalty parameter. Next we present an accelerated projection gradient algorithm, which is originally designed for convex smooth optimization in Euclidean space, over a positive definite matrix group.  We analyze the convergence of our algorithm. Finally, we show the numerical  test to demonstrate the effectiveness of the proposed algorithm.

ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization

JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong

2018, 22(2):  79-92.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.007

Asbtract ( 9811 )   PDF (647KB) ( 676 )  

Related Articles | Metrics

Based on the alternating direction method of multipliers (ADMM) and the sequential quadratic programming (SQP) method, this paper proposes a new efficient algorithm for two blocks nonconvex optimization with linear constrained. Firstly, taking SQP thought as the main line, the quadratic programming (QP)  is decomposed into two independent small scale QP according to ADMM idea. Secondly, the new iteration point of the prime variable is generated by Armijo line search  for the augmented Lagrange function. Finally, the dual variables are updated by an explicit expression. Thus, a new ADMM-SQP algorithm is constructed. Under the weaker conditions, the global convergence of the  algorithm is analyzed. Some preliminary numerical results  are reported to support the efficiency of the new algorithm.

A survey on approximation mechanism design without money for facility location games

CHENG Yukun, MEI Lili

2018, 22(2):  93-104.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.008

Asbtract ( 1191 )   PDF (560KB) ( 246 )  

Related Articles | Metrics

Facility location game is one of important research areas in the forefront of algorithmic game theory. Different with the traditional facility problem, there are $n$ selfish agents in game and the addresses where they are located are private information. The game designer tries to design a mechanism, which outputs the locations of facilities according to the reported addresses of agents. One of the most important objectives in the study of facility location game is to design approximation strategy-proof or group strategy-proof mechanisms without money in order to enforce all agents to choose strategies faithfully and to achieve the overall equlibria. Mechanism design without money for the facility location game is an interdisciplinary project with topics in the common part of combinatorial optimization and theoretical computer science, which has important applications in a few practical areas such as management science, information science, social economics, etc. This survey aims at listing the recent results on the approximation mechanism design without money for facility location games from different perspectives of agent preferences, facility types, metric spaces and social objectives, and summarizes some problems which have not been solved for readers.

PM2.5 pollution characteristic in Beijing-Tianjin-Hebei region based on the perspective of functional data analysis

LIANG Yinshuang, LIU Liming

2018, 22(2):  105-114.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.009

Asbtract ( 9112 )   PDF (2246KB) ( 469 )  

Related Articles | Metrics

In recent years, there have been frequent smog and heavy pollution incidents in the Beijing-Tianjin-Hebei (Jing-Jin-Ji) area, which have caused widespread concern in the country and society. Based on the data of 68 monitoring stations in the Jing-Jin-Ji area , this paper studied the main variation patterns of the annual data of PM2.5 hours in the Jing-Jin-Ji area, and the characteristics of the temporal and spatial changes. The effect of cumulative annual emissions of sulfur dioxide and nitrogen oxides on changes in PM2.5 concentrations has also been studied. The results show that the emission of nitrogen oxides contributes more to the concentration of PM2.5. The reduction of nitrogen oxides and other pollutants can effectively reduce the concentration of PM2.5 and improve air quality. In this paper, a functional data analysis method is used. Compared with the traditional statistical mean method, it can more effectively use the different data types collected to perform more detailed analysis and thus obtain more reliable conclusions.

The concentration research of PM2.5 in Beijing with time series analysis

LI Weidong, LI Li, XU Yan

2018, 22(2):  115-126.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.010

Asbtract ( 1215 )   PDF (4459KB) ( 262 )  

Related Articles | Metrics

We have analyzed the main components of PM2.5 with time series analysis based on the data which were collected in Beijing city from the http://www.cnemc.cn/. We have processed the stationarity, pure randomness of the data and the orders, parameters and significance testing of the model. Meanwhile we also predicted the PM2.5 concentration based on the rules which were got from the data. The results of prediction have showed that the error was in the reasonable range. We also analyzed the PM2.5 relative analysis and explored the dynamic relation of PM2.5 with other pollutants such as SO_{2}、NO_{2}、CO、O_{3}、PM10 on the Wanshougong position through vector auto-regressive model (VAR). It has been illustrated that the concentration of PM2.5 could be influenced by SO_{2}、NO_{2}、CO、O_{3} and PM10 with the other days. We found that PM2.5 was influenced mostly by PM10 with a long time. The influence of O_{3} and SO_{2} to PM2.5 concentration was remarkable at the second and third periods.

A simple primal-dual algorithm for minimization of the sum of three convex functions

WANG Shuo, ZHU Zhibin, ZHANG Benxin

2018, 22(2):  127-138.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.011

Asbtract ( 1117 )   PDF (985KB) ( 257 )  

Related Articles | Metrics

In this study, we propose a simple primal-dual algorithm for minimization of a sum of three convex separable functions, which are involved a smooth function with Lipschitz continuous gradient, a nonsmooth function and a linear composite nonsmooth function. A predictor-corrector scheme to the dual variable is used in our algorithm. Convergence and convergence rate are also discussed. In the end, numerical results illustrate the efficiency of this method.

Optimal replenishment and stocking strategies for inventory mechanism  with short-term price discount and double special replenishment

CHENG Cheng, ZUO Zhuan, WANG Yiju

2018, 22(2):  139-156.  doi:10.15960/j.cnki.issn.1007-6093.2018.02.012

Asbtract ( 898 )   PDF (2358KB) ( 193 )  

Related Articles | Metrics

This paper considers the inventory system in which the supplier may provide a short-term price discount to retailers at future time and retailers may make two special orders during the special period. For this system, based on maximizing the retailer's profit, we establish an optimal replenishment and stocking model. To solve the model, we first present several modified ordering policies for the model on the basis of the economic ordering strategy, and then establish a global optimal ordering policy for the inventory model. The given numerical experiments show the validity of the model and the efficiency of the algorithm.