Takaki MATSUNE Katsuhide FUJITA
Recently, multi-issue closed negotiations have attracted attention in multi-agent systems. In particular, multi-time and multilateral negotiation strategies are important topics in multi-issue closed negotiations. In multi-issue closed negotiations, an automated negotiating agent needs to have strategies for estimating an opponent's utility function by learning the opponent's behaviors since the opponent's utility information is not open to others. However, it is difficult to estimate an opponent's utility function for the following reasons: (1) Training datasets for estimating opponents' utility functions cannot be obtained. (2) It is difficult to apply the learned model to different negotiation domains and opponents. In this paper, we propose a novel method of estimating the opponents' utility functions using boosting based on the least-squares method and nonlinear programming. Our proposed method weights each utility function estimated by several existing utility function estimation methods and outputs improved utility function by summing each weighted function. The existing methods using boosting are based on the frequency-based method, which counts the number of values offered, considering the time elapsed when they offered. Our experimental results demonstrate that the accuracy of estimating opponents' utility functions is significantly improved under various conditions compared with the existing utility function estimation methods without boosting.
Hyun KWON Yongchul KIM Ki-Woong PARK Hyunsoo YOON Daeseon CHOI
Deep neural networks (DNNs) are widely used in many applications such as image, voice, and pattern recognition. However, it has recently been shown that a DNN can be vulnerable to a small distortion in images that humans cannot distinguish. This type of attack is known as an adversarial example and is a significant threat to deep learning systems. The unknown-target-oriented generalized adversarial example that can deceive most DNN classifiers is even more threatening. We propose a generalized adversarial example attack method that can effectively attack unknown classifiers by using a hierarchical ensemble method. Our proposed scheme creates advanced ensemble adversarial examples to achieve reasonable attack success rates for unknown classifiers. Our experiment results show that the proposed method can achieve attack success rates for an unknown classifier of up to 9.25% and 18.94% higher on MNIST data and 4.1% and 13% higher on CIFAR10 data compared with the previous ensemble method and the conventional baseline method, respectively.
Kotoko YAMADA Nuttapong ATTRAPADUNG Keita EMURA Goichiro HANAOKA Keisuke TANAKA
Attribute-based encryption (ABE), a cryptographic primitive, realizes fine-grained access control. Because of its attractive functionality, many systems based on ABE have been constructed to date. In such cryptographic systems, revocation functionality is indispensable to handle withdrawal of users, secret key exposure, and others. Although many ABE schemes with various functionalities have been proposed, only a few of these are revocable ABE (RABE). In this paper, we propose two generic constructions of RABE from ABE. Our first construction employs the pair encoding framework (Attrapadung, EUROCRYPT 2014), and combines identity-based revocation and ABE via the generic conjunctive conversion of Attrapadung and Yamada (CT-RSA 2015). Our second construction converts ABE to RABE directly when ABE supports Boolean formulae. Because our constructions preserve functionalities of the underlying ABE, we can instantiate various fully secure RABE schemes for the first time, e.g., supporting regular languages, with unbounded attribute size and policy structure, and with constant-size ciphertext and secret key.
Yusuke YAGI Keita TAKAHASHI Toshiaki FUJII Toshiki SONODA Hajime NAGAHARA
A light field, which is often understood as a set of dense multi-view images, has been utilized in various 2D/3D applications. Efficient light field acquisition using a coded aperture camera is the target problem considered in this paper. Specifically, the entire light field, which consists of many images, should be reconstructed from only a few images that are captured through different aperture patterns. In previous work, this problem has often been discussed from the context of compressed sensing (CS), where sparse representations on a pre-trained dictionary or basis are explored to reconstruct the light field. In contrast, we formulated this problem from the perspective of principal component analysis (PCA) and non-negative matrix factorization (NMF), where only a small number of basis vectors are selected in advance based on the analysis of the training dataset. From this formulation, we derived optimal non-negative aperture patterns and a straight-forward reconstruction algorithm. Even though our method is based on conventional techniques, it has proven to be more accurate and much faster than a state-of-the-art CS-based method.
Phuc V. TRINH Thanh V. PHAM Anh T. PHAM
Both spatial diversity and multihop relaying are considered to be effective methods for mitigating the impact of atmospheric turbulence-induced fading on the performance of free-space optical (FSO) systems. Multihop relaying can significantly reduce the impact of fading by relaying the information over a number of shorter hops. However, it is not feasible or economical to deploy relays in many practical scenarios. Spatial diversity could substantially reduce the fading variance by introducing additional degrees of freedom in the spatial domain. Nevertheless, its superiority is diminished when the fading sub-channels are correlated. In this paper, our aim is to study the fundamental performance limits of spatial diversity suffering from correlated Gamma-Gamma (G-G) fading channels in multihop coherent FSO systems. For the performance analysis, we propose to approximate the sum of correlated G-G random variables (RVs) as a G-G RV, which is then verified by the Kolmogorov-Smirnov (KS) goodness-of-fit statistical test. Performance metrics, including the outage probability and the ergodic capacity, are newly derived in closed-form expressions and thoroughly investigated. Monte-Carlo (M-C) simulations are also performed to validate the analytical results.
Hang CUI Shoichi HIRASAWA Hiroaki KOBAYASHI Hiroyuki TAKIZAWA
Sparse Matrix-Vector multiplication (SpMV) is a computational kernel widely used in many applications. Because of the importance, many different implementations have been proposed to accelerate this computational kernel. The performance characteristics of those SpMV implementations are quite different, and it is basically difficult to select the implementation that has the best performance for a given sparse matrix without performance profiling. One existing approach to the SpMV best-code selection problem is by using manually-predefined features and a machine learning model for the selection. However, it is generally hard to manually define features that can perfectly express the characteristics of the original sparse matrix necessary for the code selection. Besides, some information loss would happen by using this approach. This paper hence presents an effective deep learning mechanism for SpMV code selection best suited for a given sparse matrix. Instead of using manually-predefined features of a sparse matrix, a feature image and a deep learning network are used to map each sparse matrix to the implementation, which is expected to have the best performance, in advance of the execution. The benefits of using the proposed mechanism are discussed by calculating the prediction accuracy and the performance. According to the evaluation, the proposed mechanism can select an optimal or suboptimal implementation for an unseen sparse matrix in the test data set in most cases. These results demonstrate that, by using deep learning, a whole sparse matrix can be used to do the best implementation prediction, and the prediction accuracy achieved by the proposed mechanism is higher than that of using predefined features.
Nii L. SOWAH Qingbo WU Fanman MENG Liangzhi TANG Yinan LIU Linfeng XU
In this paper, we improve upon the accuracy of existing tracklet generation methods by repairing tracklets based on their quality evaluation and detection propagation. Starting from object detections, we generate tracklets using three existing methods. Then we perform co-tracklet quality evaluation to score each tracklet and filtered out good tracklet based on their scores. A detection propagation method is designed to transfer the detections in the good tracklets to the bad ones so as to repair bad tracklets. The tracklet quality evaluation in our method is implemented by intra-tracklet detection consistency and inter-tracklet detection completeness. Two propagation methods; global propagation and local propagation are defined to achieve more accurate tracklet propagation. We demonstrate the effectiveness of the proposed method on the MOT 15 dataset
Hidefumi HIRAISHI Hiroshi IMAI Yoichi IWATA Bingkai LIN
Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
An important problem in mathematics and data science, given two or more metric spaces, is obtaining a metric of the product space by aggregating the source metrics using a multivariate function. In 1981, Borsík and Doboš solved the problem, and much progress has subsequently been made in generalizations of the problem. The triangle inequality is a key property for a bivariate function to be a metric. In the metric aggregation, requesting the triangle inequality of the resulting metric imposes the subadditivity on the aggregating function. However, in some applications, such as the image matching, a relaxed notion of the triangle inequality is useful and this relaxation may enlarge the scope of the aggregators to include some natural superadditive functions such as the harmonic mean. This paper examines the aggregation of two semimetrics (i.e. metrics with a relaxed triangle inequality) by the harmonic mean is studied and shows that such aggregation weakly preserves the relaxed triangle inequalities. As an application, the paper presents an alternative simple proof of the relaxed triangle inequality satisfied by the robust Jaccard-Tanimoto set dissimilarity, which was originally shown by Gragera and Suppakitpaisarn in 2016.
A linear-time constructible data structure for a real number sequence supporting O(1)-time queries of the maximal local maximum-sum segment of any contiguous subsequence containing any specific position is proposed, where a local maximum-sum segment is a segment whose maximum-sum segment is itself.
V2V broadcast communication is not only promising for safety driving assistance but also enhancing automated driving ability by sharing information of vehicle moving behavior with other vehicles. However, an important issue is how to reduce information delivery delay and achieve dependable communication that is essential for automated vehicle control by machine. Since radio propagation often exhibits fading and shadowing on the road, V2V packet error happens probabilistically. Although repeated transmission method can enhance reliability of broadcast transmission, information delivery delay significantly increases as packet reception rate decreases. In order to reduce the delay, a relay-assisted broadcast transmission scheme is employed in this paper. The scheme can improve packet reception rate by path diversity and remarkably reduce average delivery delay due to repeated transmission. Performance with roadside relay stations considering urban environment with multiple intersections is evaluated through large-scale network simulation. The obtained results show that the average delivery delay is remarkably reduced by the relay-assist scheme to less than 20ms, which is less than a quarter of the direct V2V communication.
Yu NAKAHATA Jun KAWAHARA Takashi HORIYAMA Shoji KASAHARA
This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.
Dawei XU Jinfeng HUANG Yuta NAKANE Tomoo YOKOYAMA Takashi HORIYAMA Ryuhei UEHARA
Last year, a new notion of rep-cube was proposed. A rep-cube is a polyomino that is a net of a cube, and it can be divided into some polyominoes such that each of them can be folded into a cube. This notion was inspired by the notions of polyomino and rep-tile, which were introduced by Solomon W. Golomb. It was proved that there are infinitely many distinct rep-cubes. In this paper, we investigate this new notion and show further results.
Hyungkyu LEE Younho LEE Changho SEO Hyunsoo YOON
We propose a method for efficiently detecting phishing attacks in mobile environments. When a user visits a website of a certain URL, the proposed method first compares the URL to a generated whitelist. If the URL is not in the whitelist, it detects if the site is a phishing site based on the results of Google search with a carefully refined URL. In addition, the phishing detection is performed only when the user provides input to the website, thereby reducing the frequency of invoking phishing detection to decrease the amount of power used. We implemented the proposed method and used 8315 phishing sites and the same number of legitimate websites for evaluating the performance of the proposed method. We achieved a phishing detection rate of 99.22% with 81.22% reduction in energy consumption as compared to existing approaches that also use search engine for phishing detection. Moreover, because the proposed method does not employ any other algorithm, software, or comparison group, the proposed method can be easily deployed.
Zhi-xiong XU Lei CAO Xi-liang CHEN Chen-xi LI
Aiming at the contradiction between exploration and exploitation in deep reinforcement learning, this paper proposes “reward-based exploration strategy combined with Softmax action selection” (RBE-Softmax) as a dynamic exploration strategy to guide the agent to learn. The superiority of the proposed method is that the characteristic of agent's learning process is utilized to adapt exploration parameters online, and the agent is able to select potential optimal action more effectively. The proposed method is evaluated in discrete and continuous control tasks on OpenAI Gym, and the empirical evaluation results show that RBE-Softmax method leads to statistically-significant improvement in the performance of deep reinforcement learning algorithms.
Su LIU Xingguang GENG Yitao ZHANG Shaolong ZHANG Jun ZHANG Yanbin XIAO Chengjun HUANG Haiying ZHANG
The quality of edge detection is related to detection angle, scale, and threshold. There have been many algorithms to promote edge detection quality by some rules about detection angles. However these algorithm did not form rules to detect edges at an arbitrary angle, therefore they just used different number of angles and did not indicate optimized number of angles. In this paper, a novel edge detection algorithm is proposed to detect edges at arbitrary angles and optimized number of angles in the algorithm is introduced. The algorithm combines singularity detection with Gaussian wavelet transform and edge detection at arbitrary directions and contain five steps: 1) An image is divided into some pixel lines at certain angle in the range from 45° to 90° according to decomposition rules of this paper. 2) Singularities of pixel lines are detected and form an edge image at the certain angle. 3) Many edge images at different angles form a final edge images. 4) Detection angles in the range from 45° to 90° are extended to range from 0° to 360°. 5) Optimized number of angles for the algorithm is proposed. Then the algorithm with optimized number of angles shows better performances.
Satoshi IMAMURA Yuichiro YASUI Koji INOUE Takatsugu ONO Hiroshi SASAKI Katsuki FUJISAWA
The power consumption of server platforms has been increasing as the amount of hardware resources equipped on them is increased. Especially, the capacity of DRAM continues to grow, and it is not rare that DRAM consumes higher power than processors on modern servers. Therefore, a reduction in the DRAM energy consumption is a critical challenge to reduce the system-level energy consumption. Although it is well known that improving row buffer locality(RBL) and bank-level parallelism (BLP) is effective to reduce the DRAM energy consumption, our preliminary evaluation on a real server demonstrates that RBL is generally low across 15 multithreaded benchmarks. In this paper, we investigate the memory access patterns of these benchmarks using a simulator and observe that cache line-grained channel interleaving schemes, which are widely applied to modern servers including multiple memory channels, hurt the RBL each of the benchmarks potentially possesses. In order to address this problem, we focus on a row-grained channel interleaving scheme and compare it with three cache line-grained schemes. Our evaluation shows that it reduces the DRAM energy consumption by 16.7%, 12.3%, and 5.5% on average (up to 34.7%, 28.2%, and 12.0%) compared to the other schemes, respectively.
Koya MITSUZUKA Michihiro KOIBUCHI Hideharu AMANO Hiroki MATSUTANI
In parallel processing applications, a few worker nodes called “stragglers”, which execute their tasks significantly slower than other tasks, increase the execution time of the job. In this paper, we propose a network switch based straggler handling system to mitigate the burden of the compute nodes. We also propose how to offload detecting stragglers and computing their results in the network switch with no additional communications between worker nodes. We introduce some approximate techniques for the proxy computation and response at the switch; thus our switch is called “ApproxSW.” As a result of a simulation experiment, the proposed approximation based on task similarity achieves the best accuracy in terms of quality of generated Map outputs. We also analyze how to suppress unnecessary proxy computation by the ApproxSW. We implement ApproxSW on NetFPGA-SUME board that has four 10Gbit Ethernet (10GbE) interfaces and a Virtex-7 FPGA. Experimental results shows that the ApproxSW functions do not degrade the original 10GbE switch performance.
Hirofumi SUZUKI Shin-ichi MINATO
Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.