Benchmark-based evaluation is the de facto standard for comparing large language models (LLMs).However, its reliability is increasingly threatened by test set contamination, where test samples or their close variants leak into training data and artificially inflate reported performance.To address this issue, prior work has explored two main lines of mitigation.One line attempts to identify and remove contaminated benchmark items before evaluation, but this inevitably alters the evaluation set itself and becomes unreliable when contamination is moderate or severe.The other line preserves the benchmark and instead suppresses contaminated behavior at evaluation time; however, such interventions often interfere with normal inference and lead to noticeable performance degradation on clean inputs.We propose DeconIEP, a decontamination framework that operates entirely during evaluation by applying small, bounded perturbations in the input embedding space.Guided by a relatively less-contaminated reference model, De-conIEP learns an instance-adaptive perturbation generator that steers the evaluated model away from memorization-driven shortcut pathways.Across multiple open-weight LLMs and benchmarks, extensive empirical results show that DeconIEP achieves strong decontamination effectiveness while incurring only minimal degradation in benign utility.

This study aims to assess the feasibility of applying adversarial examples to attack cardiac diagnosis systems powered by machine learning algorithms. To achieve this, we introduce “ adversarial beats ,” which are adversarial perturbations that are tailored specifically against classification systems designed to diagnose electrocardiograms (ECGs). We first formulated an algorithm to generate adversarial examples for multiple neural network models for ECG classification and studied their attack success rates. Next, to evaluate their feasibility in a physical environment, we mounted a hardware attack by designing a malicious signal generator that injects adversarial beats into ECG sensor readings using commercial off-the-shelf hardware. To the best of our knowledge, our research is the first to evaluate the proficiency of adversarial examples for ECGs in a physical setup. Our real-world experiments demonstrate that, against an automated ECG diagnosis apparatus, our attack method can fake the presence of potential signs of cardiomyopathy with approximately 42.1% chance of success and the attacker can repeat the attack until a fraudulent insurance claim or other health care fraud is established. Based on the comprehensive feasibility study of attacks using adversarial beats, we conclude that the attacks have a sufficient chance to succeed such that an attacker may be incentivized to fake the presence of cardiomyopathy, potentially leading to unnecessary medication prescriptions and fraudulent medical insurance claims.

Transfer learning enhances prediction accuracy on a target distribution by leveraging data from a source distribution, demonstrating significant benefits in various applications. This paper introduces a novel dissimilarity measure that utilizes vicinity information, i.e., the local structure of data points, to analyze the excess error in classification under covariate shift, a transfer learning setting where marginal feature distributions differ but conditional label distributions remain the same. We characterize the excess error using the proposed measure and demonstrate faster or competitive convergence rates compared to previous techniques. Notably, our approach is effective in the support non-containment assumption, which often appears in real-world applications, holds. Our theoretical analysis bridges the gap between current theoretical findings and empirical observations in transfer learning, particularly in scenarios with significant differences between source and target distributions.

Model merging is a technique that combines multiple finetuned models into a single model without additional training, allowing a free-rider to cheaply inherit specialized capabilities. This study investigates methodologies to suppress unwanted model merging by free-riders. Existing methods such as model watermarking or fingerprinting can only detect merging in hindsight. In contrast, we propose a first proactive defense against model merging. Specifically, our defense method modifies the model parameters so that the model is disrupted if the model is merged with any other model, while its functionality is kept unchanged if not merged with others. Our approach consists of two modules, rearranging MLP parameters and scaling attention heads, which push the model out of the shared basin in parameter space, causing the merging performance with other models to degrade significantly. We conduct extensive experiments on image classification, image generation, and text classification to demonstrate that our defense severely disrupts merging while retaining the functionality of the post-protect model. Moreover, we analyze potential adaptive attacks and further propose a dropout-based pruning to improve our proposal's robustness.

Conventional neural networks including Transformers encounter the catastrophic forgetting problem during sequential task learning, where learning new tasks interferes with previously learned knowledge. Existing memory replay and regularization methods cannot effectively eliminate interference among different tasks. Soft parameter sharing methods usually necessitate a large amount of additional parameters for learning each task, and task identity information is essential for leveraging task-specific parameters. To this end, we propose Remembering Transformer leveraging an adapter mixtures architecture enhanced by a generative routing mechanism for efficient task retention. In generative routing, input samples are allocated to the most relevant expert adapters based on a reconstruction loss. Moreover, unlike existing studies on soft parameter sharing that do not consider model capacity limitations, we investigate a challenging setting where the number of task-specific parameters is constrained. In particular, we devise an adapter fusion strategy to aggregate resembling experts based on similarity matching and knowledge distillation. Extensive empirical results measured by task accuracy, forgetting rate, and memory footprint, demonstrate that Remembering Transformer significantly enhances knowledge retention without task identity information. The proposed method surpasses various conventional methods with enhanced parameter efficiency in a broad range of incremental learning tasks.

Recent research on textual backdoor attacks (TBAs) showed that backdoors can be successfully implanted into the victim model on full-parameter fine-tuning. In this paper, we empirically show that existing TBAs cannot achieve high attack success rates on prefix-tuning, a parameter-efficient fine-tuning paradigm that prepends a prefix (i.e., deep continuous prompt) to the input. This failure is because the invasion of the inserted backdoor and general-purpose learning from clean samples are inherently incompatible due to the limited trainable parameters on the prefix. To address this problem, we propose a novel TBA that indirectly improves the effects of the inserted backdoor by weakening the prediction confidence of its specially embedded sample based on two strategies: susceptible sample selection (S3) and prediction confidence reduction (PCR). Specifically, S3 consciously selects susceptible samples with low prediction confidence to the target label according to their text lengths. Besides, PCR further weakens their prediction confidence by an iterative mask-and-infill word replacing process. In this way, the inserted backdoor triggers in samples with low prediction confidence to the target label can be implanted more effectively into the continuous prompts on prefix-tuning. Experiment results on four benchmarks validate the superiority of our proposed method1.

We propose a Trojan horse-type attribute inference attack (AlA) against the gradient boosting decision trees (GBDT) in the federated learning setting. Our Trojan AlA consists of a Trojan tree creation and an attribute inference. Both algorithms leverage the characteristics of the federated learning protocol for the GBDT training. First, the adversary creates a decision tree, a Trojan tree, that isolates a target data record from other data records. The adversary sends the Trojan tree to the server through the federated learning protocol at their round. Trojan tree forces the victim's tree to “memorize” a target attribute value of target data record that the adversary wants to know. The adversary can recover the target attribute value by observing the tree submitted by the victim if the victim uses the target data record for training the tree. For the regression task, we derive sufficient conditions for a successful attack. According to our theorem, if the target data record is distinct in the victim's dataset, the proposed attack is always successful. Experiments on multiple datasets and settings show results that align with the above theoretical analysis. Even if some conditions for theoretical analysis are relaxed, the proposed attack outperforms baseline attacks. To the best of our knowledge, this is the first study of an attribute inference attack against the GBDT in the federated learning setting.

Trojan attacks embed perturbations in input data leading to malicious behavior in neural network models. A combination of various Trojans in different modalities enables an adversary to mount a sophisticated attack on multimodal learning such as Visual Question Answering (VQA). However, multimodal Trojans in conventional methods are susceptible to parameter adjustment during processes such as fine-tuning. To this end, we propose an instance-level multimodal Trojan attack on VQA that efficiently adapts to fine-tuned models through a dual-modality adversarial learning method. This method compromises two specific neurons in a specific perturbation layer in the pretrained model to produce overly large neuron activations. Then, a malicious correlation between these overactive neurons and the malicious output of a fine-tuned model is established through adversarial learning. Extensive experiments are conducted using the VQA-v2 dataset, based on a wide range of metrics including sample efficiency, stealthiness, and robustness. The proposed attack demonstrates enhanced performance with diverse vision and text Trojans tailored for each sample. We demonstrate that the proposed attack can be efficiently adapted to different fine-tuned models, by injecting only a few shots of Trojan samples. Moreover, we investigate the attack performance under conventional defenses, where the defenses cannot effectively mitigate the attack.

Evolution strategy (ES) is one of the promising classes of algorithms for black-box continuous optimization. Despite its broad successes in applications, theoretical analysis on the speed of its convergence is limited on convex quadratic functions and their monotonic transformation. In this study, an upper bound and a lower bound of the rate of linear convergence of the (1+1)-ES on locally$L$-strongly convex functions with$U$-Lipschitz continuous gradient are derived as$\exp (-\Omega _{d\to \infty }({L}/({d\cdot U})))$and$\exp (-1/d)$, respectively. Notably, any prior knowledge on the mathematical properties of the objective function, such as the Lipschitz constant, is not given to the algorithm, whereas the existing analyses of derivative-free optimization algorithms require it.

Heterogeneous unsupervised domain adaptation (HUDA) is the most challenging domain adaptation setting where the feature spaces of source and target domains are heterogeneous, and the target domain has only unlabeled data. Existing HUDA methods assume that both positive and negative examples are available in the source domain, which may not be satisfied in some real applications. This paper addresses a new challenging setting called positive and unlabeled heterogeneous unsupervised domain adaptation (PU-HUDA), a HUDA setting where the source domain only has positives. PU-HUDA can also be viewed as an extension of PU learning where the positive and unlabeled examples are sampled from different domains. A naive combination of existing HUDA and PU learning methods is ineffective in PU-HUDA due to the gap in label distribution between the source and target domains. To overcome this issue, we propose a novel method, predictive adversarial domain adaptation (PADA), which can predict likely positive examples from the unlabeled target data and simultaneously align the feature spaces to reduce the distribution divergence between the whole source data and the likely positive target data. PADA achieves this by a unified adversarial training framework for learning a classifier to predict positive examples and a feature transformer to transform the target feature space to that of the source. Specifically, they are both trained to fool a common discriminator that determines whether the likely positive examples are from the target or source domain. We experimentally show that PADA outperforms several baseline methods, such as the naive combination of HUDA and PU learning.

The Transformer is a deep learning architecture that processes sequence data. The Transformer attains the state-of-the-art in several tasks of sequence data analysis, and its variants, such as BERT and GPT-3, are used as a defacto-standard for solving general tasks in natural language processing (NLP). This work presents a 3-party multi-party computation (MPC) protocol for secure inference of the Transfomer in the honest majority setting. The attention layer is the most time-consuming part when implementing an MPC protocol for the Transformer with existing building blocks. The attention mechanism is a core component of the Transformer that captures and exploits complex dependencies among elements in the input sequences. The attention mechanism invokes the exponentiation function O(S2) times, which becomes a major bottleneck when implementing the Transformer with existing MPC primitives. To deal with this, we employ the Performer [11], a variant of the Transformer where the sigmoid function that invokes the exponentiation function is replaced with the ReLU function, a more MPC-friendly nonlinear function. Also, by introducing a kernel-based approximation of the attention matrix with random orthogonal matrices, we show that the attention layer can be processed with O(S) times calls of the ReLU function. We investigate the efficiency of the proposed method by an end-to-end implementation of the Transformer with 3-party MPC. Experimental evaluation shows that, for translating a sequence where the output sequence length is 64, the entire computation time takes about 19 minutes in the LAN environment.

A concept-based classifier can explain the decision process of a deep learning model by human understandable concepts in image classification problems. However, sometimes concept-based explanations may cause false positives, which misregards unrelated concepts as important for the prediction task. Our goal is to find the statistically significant concept for classification to prevent misinterpretation. In this study, we propose a method using a deep learning model to learn the image concept and then using the knockoff sample to select the important concepts for prediction by controlling the False Discovery Rate (FDR) under a certain value. We evaluate the proposed method in our experiments on both synthetic and real data. Also, it shows that our method can control the FDR properly while selecting highly interpretable concepts to improve the trustworthiness of the model.

We explore the minimax optimal error associated with a demographic parity-constrained regression problem within the context of a linear model. Our proposed model encompasses a broader range of discriminatory bias sources compared to the model presented by Chzhen and Schreuder. Our analysis reveals that the minimax optimal error for the demographic parity-constrained regression problem under our model is characterized by $\Theta(\frac{dM}{n})$, where $n$ denotes the sample size, $d$ represents the dimensionality, and $M$ signifies the number of demographic groups arising from sensitive attributes. Moreover, we demonstrate that the minimax error increases in conjunction with a larger bias present in the model.

This paper develops a certified defense for deep neural network (DNN) based content based image retrieval (CBIR) against adversarial examples (AXs). Previous works put their effort into certified defense for classification to improve certified robustness, which guarantees that no AX to cause misclassification exists around the sample. Such certified defense, however, could not be applied to CBIR directly because the goals of adversarial attack against classification and CBIR are completely different. To develop the certified defense for CBIR, we first define new certified robustness of CBIR, which guarantees that no AX that changes the ranking of CBIR exists around the query or candidate images. Then, we propose computationally tractable verification algorithms that verify whether the certified robustness of CBIR is achieved by utilizing upper and lower bounds of distances between feature representations of perturbed and non-perturbed images. Finally, we propose new objective functions for training feature extraction DNNs that increases the number of inputs that satisfy the certified robustness of CBIR by tightening the upper and lower bounds. Experimental results show that our objective functions significantly improve the certified robustness of CBIR than existing methods.

In this study, we consider a continuous min–max optimization problem minx∈ 𝕏maxy∈ 𝕐f(x, y) whose objective function is a black-box. We propose a novel approach to minimize the worst-case objective functionF(x) = maxy∈ 𝕐f(x, y) directly using a covariance matrix adaptation evolution strategy in which the rankings of solution candidates are approximated by our proposed worst-case ranking approximation mechanism. We develop two variants of worst-case ranking approximation combined with a covariance matrix adaptation evolution strategy and approximate gradient ascent as numerical solvers for the inner maximization problem. Numerical experiments show that our proposed approach outperforms several existing approaches when the objective function is a smooth strongly convex–concave function and the interaction betweenxandyis strong. We investigate the advantages of the proposed approach for problems where the objective function is not limited to smooth strongly convex–concave functions. The effectiveness of the proposed approach is demonstrated in the robust berthing control problem with uncertainty.

Statistically significant pattern mining (SSPM), which evaluates each pattern via a hypothesis test, is an essential and challenging data mining task for knowledge discovery. We introduce a preference relation between patterns and aim to discover the most preferred patterns under the constraint of statistical significance, which has never been considered in existing SSPM problems. We propose an iterative multiple testing procedure that can alternately reject a hypothesis and safely ignore the less useful hypotheses than the rejected one. By filtering out patterns with low utility, we can avoid the significance budget consumption of rejecting useless (uninteresting) patterns and focus the significance budget on more useful patterns, leading to more useful discoveries. We show that the proposed method can control the familywise error rate (FWER) under certain assumptions, which can be satisfied by a realistic problem class in SSPM. We also show that the proposed method always discovers equally or more useful patterns than Tarone-Bonferroni and Subfamily-wise Multiple Testing (SMT). Finally, we conducted several experiments with both synthetic and real-world data to evaluate the performance of our method. The proposed method discovered many more useful patterns in the experiments with real-world datasets than the existing method for all five conducted tasks.

We aim to explain a black-box classifier with the form: "data X is classified as class Y because X has A, B and does not have C" in which A, B, and C are high-level concepts. The challenge is that we have to discover in an unsupervised manner a set of concepts, i.e., A, B and C, that is useful for explaining the classifier. We first introduce a structural generative model that is suitable to express and discover such concepts. We then propose a learning process that simultaneously learns the data distribution and encourages certain concepts to have a large causal influence on the classifier output. Our method also allows easy integration of user's prior knowledge to induce high interpretability of concepts. Finally, using multiple datasets, we demonstrate that the proposed method can discover useful concepts for explanation in this form.

In this study, we investigate the problem of min-max continuous optimization in a black-box setting minx maxy f (x,y). A popular approach updates x and y simultaneously or alternatingly. However, two major limitations have been reported in existing approaches. (I) As the influence of the interaction term between x and y (e.g., xTBy) on the Lipschitz smooth and strongly convex-concave function f increases, the approaches converge to an optimal solution at a slower rate. (II) The approaches fail to converge if f is not Lipschitz smooth and strongly convex-concave around the optimal solution. To address these difficulties, we propose minimizing the worst-case objective function F(x) = maxy f (x, y) directly using the covariance matrix adaptation evolution strategy, in which the rankings of solution candidates are approximated by our proposed worst-case ranking approximation (WRA) mechanism. Compared with existing approaches, numerical experiments show two important findings regarding our proposed method. (1) The proposed approach is eficient in terms of f-calls on a Lipschitz smooth and strongly convex-concave function with a large interaction term. (2) The proposed approach can converge on functions that are not Lipschitz smooth and strongly convex-concave around the optimal solution, whereas existing approaches fail.

This paper focuses on the domain generalization task, which aims to learn a model that generalizes to unseen domains by utilizing multiple training domains. More specifically, we follow the idea of adversarial data augmentation, which aims to synthesize and augment training data with “hard” domains for improving the model's domain generalization ability. Previous works augment training data only with samples similar to the training data, resulting in limited generalization ability. We propose a novel adversarial data augmentation method, termed GADA (Generative Adversarial Domain Augmentation), which employs an image-to-image translation model to obtain a distribution of novel domains that are semantically different from the training domains, and, at the same time, hard to classify. Evaluation and further analysis suggest that adversarial data augmentation with semantically different samples leads to better domain generalization performance.

This study proposes a method that enables attribution of GAN-generated images to the GAN model that generated the images. Existing attribution methods (e.g., model watermark) require preprossessing on the model before model publication to attain high attribution performance. This study proposes a post-hoc attribution method that does not require preprocessing before model publication. Our attribution method is designed based on the fact that latent recovery can attain better image recovery if images to be attributed are generated by the source model. Our experimental evaluation shows that our post-hoc attribution method attains almost the same attribution performance as existing methods that require preprocessing if more than five images are available for attribution.

In real-world applications of multi-class classification models, misclassification in an important class (e.g., stop sign) can be significantly more harmful than in other classes (e.g., speed limit). In this paper, we propose a loss function that can improve the recall of an important class while maintaining the same level of accuracy as the case using cross-entropy loss. For our purpose, we need to make the separation of the important class better than the other classes. However, existing methods that give a class-sensitive penalty for cross-entropy loss do not improve the separation. On the other hand, the method that gives a margin to the angle between the feature vectors and the weight vectors of the last fully connected layer corresponding to each feature can improve the separation. Therefore, we propose a loss function that can improve the separation of the important class by setting the margin only for the important class, called Class-sensitive Additive Angular Margin Loss (CAMRI Loss). CAMRI loss is expected to reduce the variance of angles between features and weights of the important class relative to other classes due to the margin around the important class in the feature space by adding a penalty to the angle. In addition, concentrating the penalty only on the important classes hardly sacrifices the separation of the other classes. Experiments on CIFAR-10, GTSRB, and AwA2 showed that the proposed method could improve up to 9% recall improvement on cross-entropy loss without sacrificing accuracy.

We investigate policy transfer using image-to-semantics translation to mitigate learning difficulties in vision-based robotics control agents. This problem assumes two environments: a simulator environment with semantics, that is, low-dimensional and essential information, as the state space, and a real-world environment with images as the state space. By learning mapping from images to semantics, we can transfer a policy, pre-trained in the simulator, to the real world, thereby eliminating real-world on-policy agent interactions to learn, which are costly and risky. In addition, using image-to-semantics mapping is advantageous in terms of the computational efficiency to train the policy and the interpretability of the obtained policy over other types of sim-to-real transfer strategies. To tackle the main difficulty in learning image-to-semantics mapping, namely the human annotation cost for producing a training dataset, we propose two techniques: pair augmentation with the transition function in the simulator environment and active learning. We observed a reduction in the annotation cost without a decline in the performance of the transfer, and the proposed approach outperformed the existing approach without annotation.

Model poisoning attacks on federated learning intrude in the entire system via compromising an edge model, resulting in malfunctioning of machine learning models. Such compromised models are tampered with to perform adversary-desired behaviors. In particular, we considered a semi-targeted situation where the source class is predetermined however the target class is not. The goal is to cause the global classifier to misclassify data of the source class. Though approaches such as label flipping have been adopted to inject poisoned parameters into federated learning, it has been shown that their performances are usually class-sensitive varying with different target classes applied. Typically, an attack can become less effective when shifting to a different target class. To overcome this challenge, we propose the Attacking Distance-aware Attack (ADA) to enhance a poisoning attack by finding the optimized target class in the feature space. Moreover, we studied a more challenging situation where an adversary had limited prior knowledge about a client's data. To tackle this problem, ADA deduces pair-wise distances between different classes in the latent feature space from shared model parameters based on the backward error analysis. We performed extensive empirical evaluations on ADA by varying the factor of attacking frequency in three different image classification tasks. As a result, ADA succeeded in increasing the attack performance by 1.8 times in the most challenging case with an attacking frequency of 0.01.

In the field of reinforcement learning, because of the high cost and risk of policy training in the real world, policies are trained in a simulation environment and transferred to the corresponding real-world environment.However, the simulation environment does not perfectly mimic the real-world environment, lead to model misspecification. Multiple studies report significant deterioration of policy performance in a real-world environment.In this study, we focus on scenarios involving a simulation environment with uncertainty parameters and the set of their possible values, called the uncertainty parameter set. The aim is to optimize the worst-case performance on the uncertainty parameter set to guarantee the performance in the corresponding real-world environment.To obtain a policy for the optimization, we propose an off-policy actor-critic approach called the Max-Min Twin Delayed Deep Deterministic Policy Gradient algorithm (M2TD3), which solves a max-min optimization problem using a simultaneous gradient ascent descent approach.Experiments in multi-joint dynamics with contact (MuJoCo) environments show that the proposed method exhibited a worst-case performance superior to several baseline approaches.

Neural architecture search (NAS) is an approach for automatically designing a neural network architecture without human effort or expert knowledge. However, the high computational cost of NAS limits its use in commercial applications. Two recent NAS paradigms, namely one-shot and sparse propagation, which reduce the time and space complexities, respectively, provide clues for solving this problem. In this paper, we propose a novel search strategy for one-shot and sparse propagation NAS, namely AdvantageNAS, which further reduces the time complexity of NAS by reducing the number of search iterations. AdvantageNAS is a gradient-based approach that improves the search efficiency by introducing credit assignment in gradient estimation for architecture updates. Experiments on the NAS-Bench-201 and PTB dataset show that AdvantageNAS discovers an architecture with higher performance under a limited time budget compared to existing sparse propagation NAS. To further reveal the reliabilities of AdvantageNAS, we investigate it theoretically and find that it monotonically improves the expected loss and thus converges.

We handle min-max black-box optimization problems in which the scenario variable to be maximized is discrete and the design variable to be minimized is a continuous vector. To reduce the number of objective function calls, which are assumed to be computationally expensive, we propose an approach that samples a subset of scenarios at each iteration to approximate the worst-case objective function and apply the covariance matrix adaptation evolution strategy to the approximated worst-case objective function. In addition, we develop an adaptation mechanism for the probability of sampling each scenario. Moreover, we introduce the notion of support scenarios to characterize min-max optimization problems with discrete scenario variables and design test problems with various characteristics of support scenarios. Empirical evaluations reveal that the proposed approach learns to sample the set of support scenarios, being more efficient than sampling all the scenarios, especially when the available scenarios outnumber the support scenarios.

The (1+1)-evolution strategy (ES) with success-based step-size adaptation is analyzed on a general convex quadratic function and its monotone transformation, that is, f(x) = g((x - x*)TH(x - x*)), where g: R → R is a strictly increasing function, H is a positive-definite symmetric matrix, and x* ∈ Rd is the optimal solution of f. The convergence rate, that is, the decrease rate of the distance from a search point mt to the optimal solution x*, is proven to be in O(exp(-L/Tr(H))), where L is the smallest eigenvalue of H and Tr(H) is the trace of H. This result generalizes the known rate of O(exp(-1/d)) for the case of H = Id (Id is the identity matrix of dimension d) and O(exp(-1/(d · ξ))) for the case of H = diag(ξ · Id/2, Id/2). To the best of our knowledge, this is the first study in which the convergence rate of the (1+1)-ES is derived explicitly and rigorously on a general convex quadratic function, which depicts the impact of the distribution of the eigenvalues in the Hessian H on the optimization and not only the impact of the condition number of H.

Video game level generation based on machine learning (ML), in particular, deep generative models, has attracted attention as a technique to automate level generation. However, applications of existing ML-based level generations are mostly limited to tile-based level representation. When ML techniques are applied to game domains with non-tile-based level representation, such as Angry Birds, where objects in a level are specified by real-valued parameters, ML often fails to generate playable levels. In this study, we develop a deep-generative-model-based level generation for the game domain of Angry Birds. To overcome these drawbacks, we propose a sequential encoding of a level and process it as text data, whereas existing approaches employ a tile-based encoding and process it as an image. Experiments show that the proposed level generator drastically improves the stability and diversity of generated levels compared with existing approaches. We apply latent variable evolution with the proposed generator to control the feature of a generated level computed through an AI agent's play, while keeping the level stable and natural.

In adversarial attacks intended to confound deep learning models, most studies have focused on limiting the magnitude of the modification so that humans do not notice the attack. On the other hand, during an attack against autonomous cars, for example, most drivers would not find it strange if a small insect image were placed on a stop sign, or they may overlook it. In this paper, we present a systematic approach to generate natural adversarial examples against classification models by employing such natural-appearing perturbations that imitate a certain object or signal. We first show the feasibility of this approach in an attack against an image classifier by employing generative adversarial networks that produce image patches that have the appearance of a natural object to fool the target model. We also introduce an algorithm to optimize placement of the perturbation in accordance with the input image, which makes the generation of adversarial examples fast and likely to succeed. Moreover, we experimentally show that the proposed approach can be extended to the audio domain, for example, to generate perturbations that sound like the chirping of birds to fool a speech classifier.

In this study, we consider black-box minimization problems with non-convex constraints, where the constraints are significantly cheaper to evaluate than the objective. Non-convex constraints generally make it difficult to solve problems using evolutionary approaches. In this paper, we revisit a conventional technique called decoder constraint handling, which transforms a feasible non-convex domain into an easy-to-control convex set. This approach is promising because it transforms a constrained problem into an almost unconstrained one. However, its application has been considerably limited, because designing or training such a nonlinear decoder requires domain knowledge or manually prepared training data. To fully automate the decoder design, we use deep generative models. We propose a novel scheme to train a deep generative model without using manually prepared training data. For this purpose, we first train feasible solution samplers, which are deep neural networks, using the constraint functions. Subsequently, we train another deep generative model using the data generated from the trained samplers as the training data. The proposed framework is applied to tasks inspired by topology optimization problems. The empirical study demonstrates that the proposed approach can locate better solutions with fewer objective function evaluations than the existing approach.

Statistically significant patterns mining (SSPM) is an essential and challenging data mining task in the field of knowledge discovery in databases (KDD), in which each pattern is evaluated via a hypothesis test. Our study aims to introduce a preference relation into patterns and to discover the most preferred patterns under the constraint of statistical significance, which has never been considered in existing SSPM problems. We propose an iterative multiple testing procedure that can alternately reject a hypothesis and safely ignore the hypotheses that are less useful than the rejected hypothesis. One advantage of filtering out patterns with low utility is that it avoids consumption of the significance budget by rejection of useless (that is, uninteresting) patterns. This allows the significance budget to be focused on useful patterns, leading to more useful discoveries. We show that the proposed method can control the familywise error rate (FWER) under certain assumptions, that can be satisfied by a realistic problem class in SSPM. We also show that the proposed method always discovers a set of patterns that is at least equally or more useful than those discovered using the standard Tarone-Bonferroni method SSPM. Finally, we conducted several experiments with both synthetic and real-world data to evaluate the performance of our method. As a result, in the experiments with real-world datasets, the proposed method discovered a larger number of more useful patterns than the existing method for all five conducted tasks.

Deep learning has been achieving top levels of performance in many tasks. However, since it is costly to train a deep learning model, neural network models must be treated as valuable intellectual properties. One concern arising from our current situation is that malicious users might redistribute proprietary models or provide prediction services using such models without permission. One promising solution to this problem is digital watermarking, which works by embedding a mechanism into the model so that the model owners can verify their ownership of the model externally. In this study, we present a novel attack method against such watermarks known as query modification and demonstrate that all currently existing watermarking methods are vulnerable to either query modification or other existing attack methods (such as model modification). To overcome these vulnerabilities, we then present a novel watermarking method that we have named exponential weighting and experimentally show that our watermarking method achieves high watermark verification performance even under malicious invalidation processing attempts by unauthorized service providers (such as model modification and query modification) without sacrificing the predictive performance of the neural network model itself.

We propose a method to generate audio adversarial examples that can attack a state-of-the-art speech recognition model in the physical world. Previous work assumes that generated adversarial examples are directly fed to the recognition model, and is not able to perform such a physical attack because of reverberation and noise from playback environments. In contrast, our method obtains robust adversarial examples by simulating transformations caused by playback or recording in the physical world and incorporating the transformations into the generation process. Evaluation and a listening experiment demonstrated that our adversarial examples are able to attack without being noticed by humans. This result suggests that audio adversarial examples generated by the proposed method may become a real threat.

Search engine logs have a great potential in tracking and predicting outbreaks of infectious disease. More precisely, one can use the search volume of some search terms to predict the infection rate of an infectious disease in nearly real-time. However, conducting accurate and stable prediction of outbreaks using search engine logs is a challenging task due to the following two-way instability characteristics of the search logs. First, the search volume of a search term may change irregularly in the short-term, for example, due to environmental factors such as the amount of media or news. Second, the search volume may also change in the long-term due to the demographic change of the search engine. That is to say, if a model is trained with such search logs with ignoring such characteristic, the resulting prediction would contain serious mispredictions when these changes occur. In this work, we proposed a novel feature selection method to overcome this instability problem. In particular, we employ a seasonal-adjustment method that decomposes each time series into three components: seasonal, trend and irregular component and build prediction models for each component individually. We also carefully design a feature selection method to select proper search terms to predict each component. We conducted comprehensive experiments on ten different kinds of infectious diseases. The experimental results show that the proposed method outperforms all comparative methods in prediction accuracy for seven of ten diseases, in both now-casting and forecasting setting. Also, the proposed method is more successful in selecting search terms that are semantically related to target diseases.

Private comparison is about privately determining whether a > b, given two input integers a and b which are held as private information. Private comparison is an important building block for applications such as secure auction and privacy-preserving decision tree evaluation.

This paper presents a proposal of a method to extract important byte sequences in malware samples to reduce the workload of human analysts who investigate the functionalities of the samples. This method, by applying convolutional neural network (CNN) with a technique called attention mechanism to an image converted from binary data, enables calculation of an "attention map," which shows regions having higher importance for classification in the image. This distinction of regions enables extraction of characteristic byte sequences peculiar to the malware family from the binary data and can provide useful information for the human analysts without a priori knowledge. Furthermore, the proposed method calculates the attention map for all binary data including the data section. Thus, it can process packed malware that might contain obfuscated code in the data section. Results of our evaluation experiment using malware datasets show that the proposed method provides higher classification accuracy than conventional methods. Furthermore, analysis of malware samples based on the calculated attention maps confirmed that the extracted sequences provide useful information for manual analysis, even when samples are packed.

This paper addresses a problem of estimating an additive functional given n i.i.d. samples drawn from a discrete distribution P=(p1, ...,pk) with alphabet size k. The additive functional is defined as θ(P;φ)=Σi=1kφ(pi) for a function φ, which covers the most of the entropy-like criteria. We revealed in the previous paper [1] that the minimax optimal rate of this problem is characterized by the divergence speed, whereas the characterization is valid only when α ∈ (0,1) where α denotes the parameter of the divergence speed. In this paper, we extend this characterization to a more general range of the divergence speed, including α ∈ (1,3/2) and α ∈ [3/2,2]. As a result, we show that the minimax rates for α ∈ (1,3/2) and α ∈ [3/2,2] are [1/n]+[(k2)/((nlnn)2α)] and [1/n], respectively.

The goal of fairness-aware classification is to categorize data while taking into account potential issues of fairness, discrimination, neutrality, and/or independence. For example, when applying data mining technologies to university admissions, admission criteria must be non-discriminatory and fair with regard to sensitive features, such as gender or race. In this context, such fairness can be formalized as statistical independence between classification results and sensitive features. The main purpose of this paper is to analyze this formal fairness in order to achieve better trade-offs between fairness and prediction accuracy, which is important for applying fairness-aware classifiers in practical use. We focus on a fairness-aware classifier, Calders and Verwer’s two-naive-Bayes ( CV2NB ) method, which has been shown to be superior to other classifiers in terms of fairness. We hypothesize that this superiority is due to the difference in types of independence. That is, because CV2NB achieves actual independence, rather than satisfying model-based independence like the other classifiers, it can account for model bias and a deterministic decision rule. We empirically validate this hypothesis by modifying two fairness-aware classifiers, a prejudice remover method and a reject option-based classification ( ROC ) method, so as to satisfy actual independence. The fairness of these two modified methods was drastically improved, showing the importance of maintaining actual independence, rather than model-based independence. We additionally extend an approach adopted in the ROC method so as to make it applicable to classifiers other than those with generative models, such as SVMs.

Abstract A number of studies have recently been made on discrete distribution estimation in the local model, in which users obfuscate their personal data (e.g., location, response in a survey) by themselves and a data collector estimates a distribution of the original personal data from the obfuscated data. Unlike the centralized model, in which a trusted database administrator can access all users’ personal data, the local model does not suffer from the risk of data leakage. A representative privacy metric in this model is LDP (Local Differential Privacy), which controls the amount of information leakage by a parameter ∈ called privacy budget. When ∈ is small, a large amount of noise is added to the personal data, and therefore users’ privacy is strongly protected. However, when the number of users ℕ is small (e.g., a small-scale enterprise may not be able to collect large samples) or when most users adopt a small value of ∈, the estimation of the distribution becomes a very challenging task. The goal of this paper is to accurately estimate the distribution in the cases explained above. To achieve this goal, we focus on the EM (Expectation-Maximization) reconstruction method, which is a state-of-the-art statistical inference method, and propose a method to correct its estimation error (i.e., difference between the estimate and the true value) using the theory of Rilstone et al. We prove that the proposed method reduces the MSE (Mean Square Error) under some assumptions.We also evaluate the proposed method using three largescale datasets, two of which contain location data while the other contains census data. The results show that the proposed method significantly outperforms the EM reconstruction method in all of the datasets when ℕ or ∈ is small.

Let us consider a scenario that a data holder (e.g., a hospital) encrypts a data (e.g., a medical record) which relates a keyword (e.g., a disease name), and sends its ciphertext to a server. We here suppose not only the data but also the keyword should be kept private. A receiver sends a query to the server (e.g., average of body weights of cancer patients). Then, the server performs the homomorphic operation to the ciphertexts of the corresponding medical records, and returns the resultant ciphertext. In this scenario, the server should NOT be allowed to perform the homomorphic operation against ciphertexts associated with different keywords. If such a mis-operation happens, then medical records of different diseases are unexpectedly mixed. However, in the conventional homomorphic encryption, there is no way to prevent such an unexpected homomorphic operation, and this fact may become visible after decrypting a ciphertext, or as the most serious case it might be never detected. To circumvent this problem, in this paper, we propose mis-operation resistant homomorphic encryption, where even if one performs the homomorphic operations against ciphertexts associated with keywords ω' and ω, where ω -ω', the evaluation algorithm detects this fact. Moreover, even if one (intentionally or accidentally) performs the homomorphic operations against such ciphertexts, a ciphertext associated with a random keyword is generated, and the decryption algorithm rejects it. So, the receiver can recognize such a mis-operation happens in the evaluation phase. In addition to mis-operation resistance, we additionally adopt secure search functionality for keywords since it is desirable when one would like to delegate homomorphic operations to a third party. So, we call the proposed primitive mis-operation resistant searchable homomorphic encryption (MR-SHE). We also give our implementation result of inner products of encrypted vectors. In the case when both vectors are encrypted, the running time of the receiver is millisecond order for relatively small-dimensional (e.g., 26) vectors. In the case when one vector is encrypted, the running time of the receiver is approximately 5 msec even for relatively high-dimensional (e.g., 213) vectors.

In this paper, we consider the problem of privacy-preserving release of function outputs that take private information as input. Disease susceptibilities are known to be associated with clinical features (e.g., age, sex) as well as genetic features represented by SNPs of individuals. Releasing outputs are not privacy-preserving if the private input can be uniquely identified by probabilistic inference using the outputs. To release useful outputs with preserving privacy, we present a mechanism that releases an interval as output, instead of an output value. We suppose adversaries perform probabilistic inference using released outputs to sharpen the posterior distribution of the target attributes. Then, our mechanism has two significant properties. First, when our mechanism provides the output, the increase of the adversary's posterior on any input attribute is upper-bounded by a prescribed level. Second, under this privacy constraint, the mechanism can provide the narrowest (optimal) interval that includes the true output. Building such a mechanism is often intractable. We formulate the design of the mechanism as a discrete constraint optimization problem so that it is solvable in a practical computation time. We also propose an algorithm to obtain the optimal mechanism based on dynamic programming. After applying our mechanism to release disease susceptibilities of obesity, we demonstrate that our mechanism performs better than existing methods in terms of privacy and utility.

This paper develops differentially private mechanisms for $\chi^2$ test of independence. While existing works put their effort into properly controlling the type-I error, in addition to that, we investigate the type-II error of differentially private mechanisms. Based on the analysis, we present unit circle mechanism: a novel differentially private mechanism based on the geometrical property of the test statistics. Compared to existing output perturbation mechanisms, our mechanism improves the dominated term of the type-II error from $O(1)$ to $O(\exp(-\sqrt{N}))$ where $N$ is the sample size. Furthermore, we introduce novel procedures for multiple $\chi^2$ tests by incorporating the unit circle mechanism into the sparse vector technique and the exponential mechanism. These procedures can control the family-wise error rate (FWER) properly, which has never been attained by existing mechanisms.

In this paper, we consider estimators for an additive functional of φ, which is defined as θ(P; φ) = Σki=1φ(pi), from n i.i.d. random samples drawn from a discrete distribution P = (p1,..., pk) with alphabet size k. We propose a minimax optimal estimator for the estimation problem of the additive functional. We reveal that the minimax optimal rate is characterized by the divergence speed of the fourth derivative of φ if the divergence speed is high. As a result, we show there is no consistent estimator if the divergence speed of the fourth derivative of φ is larger than p-4. Furthermore, if the divergence speed of the fourth derivative of φ is p4-αfor α ϵ (0,1), the minimax optimal rate is obtained within a universal multiplicative constant as k2/(n ln n)2α+ k2-2α/n.

In this work, we propose a novel framework for linear classification, differentially private semi-supervised classification. The previous method in the classification problem, differentially private empirical risk minimization (ERM) only generates a classifier from labeled data. Inspired by semi-supervised learning, we propose two differentially private semi-supervised methods, which train a classifier by using both labeled and unlabeled data. We analyze the global sensitivity of the objective function and introduce differentially private ERM for semi-supervised prediction using output perturbation and objective perturbation. We experimentally evaluate the performance of the proposed methods and demonstrate that the proposed methods give more accurate prediction than regular differentially private ERM by increasing the number of unlabeled data used for training.

Privacy concern has been increasingly important in many machine learning (ML) problems. We study empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. Main technical tools for MPC have been developed based on cryptography. One of limitations in current cryptographically private ML is that it is computationally intractable to evaluate non-linear functions such as logarithmic functions or exponential functions. Therefore, for a class of ERM problems such as logistic regression in which non-linear function evaluations are required, one can only obtain approximate solutions. In this paper, we introduce a novel cryptographically private tool called secure approximation guarantee (SAG) method. The key property of SAG method is that, given an arbitrary approximate solution, it can provide a non-probabilistic assumption-free bound on the approximation quality under cryptographically secure computation framework. We demonstrate the benefit of the SAG method by applying it to several problems including a practical privacy-preserving data analysis task on genomic and clinical information.

Data anonymization is required before a big-data business can run effectively without compromising the privacy of personal information it uses. It is not trivial to choose the best algorithm to anonymize some given data securely for a given purpose. In accurately assessing the risk of data being compromised, there needs to be a balance between utility and security. Therefore, using common pseudo microdata, we propose a competition for the best anonymization and re-identification algorithm. The paper addresses the aim of the competition, the target microdata, sample algorithms, utility and security metrics. The design of an evaluation platform is also considered.

BACKGROUND: Searching for similar compounds in a database is the most important process for in-silico drug screening. Since a query compound is an important starting point for the new drug, a query holder, who is afraid of the query being monitored by the database server, usually downloads all the records in the database and uses them in a closed network. However, a serious dilemma arises when the database holder also wants to output no information except for the search results, and such a dilemma prevents the use of many important data resources. RESULTS: In order to overcome this dilemma, we developed a novel cryptographic protocol that enables database searching while keeping both the query holder's privacy and database holder's privacy. Generally, the application of cryptographic techniques to practical problems is difficult because versatile techniques are computationally expensive while computationally inexpensive techniques can perform only trivial computation tasks. In this study, our protocol is successfully built only from an additive-homomorphic cryptosystem, which allows only addition performed on encrypted values but is computationally efficient compared with versatile techniques such as general purpose multi-party computation. In an experiment searching ChEMBL, which consists of more than 1,200,000 compounds, the proposed method was 36,900 times faster in CPU time and 12,000 times as efficient in communication size compared with general purpose multi-party computation. CONCLUSION: We proposed a novel privacy-preserving protocol for searching chemical compound databases. The proposed method, easily scaling for large-scale databases, may help to accelerate drug discovery research by making full use of unused but valuable data that includes sensitive information.

This paper studies privacy issues related to epidemiological studies. Epidemiological studies need to preserve the privacy of subjects because they use personal information. Thus, privacy is preserved using a secure scalar product protocol based on a public-key cryptosystem and the secure function evaluation. However, the secure function evaluation has performance limitations in evaluating a product and a squared root. Therefore, this paper proposes a new computationally efficient scheme for privacy-preserving epidemiological analysis. The performance and the security of the proposed scheme are evaluated based on its trial implementation.

Due to the rapid proliferation of ontology-based information systems and networks, there are strong demands for ontology-mapping in a privacy-aware way. To this problem, in this paper, we propose Privacy-Preserving Quick Ontology Mapping (P2QOM), a privacy-preserving ontology mapping scheme based on Quick Ontology Mapping (QOM). The idea is to implement QOM, a well-known ontology-mapping scheme, in a privacy-preserving setting. More precisely, we assume a (untrusted) third party. In each client, the ontology being matched is converted into a set of features, and they are transmitted to the third party after obfuscation. The schema mapping is performed in the third party by exploiting some techniques for computing the similarity between the obfuscated features. The experimental results reveal that the proposed scheme is comparable to the original (non-privacy preserving) QOM in terms of both accuracy and performance, though the proposed scheme involves some extra overheads.

Service providers want to know user attributes and recorded information in order to improve more satisfaction of the people, or the efficiency of their services by offering services specialized to the users' preferences. However, since they choose wrong way to collect, classify, analysis, use or disclose to others, of personal information, it may exceed the explicit or implicit of the user regarding the provision of personal information. So far, many anonymization methods for those data have been proposed to solve this problem. As one of anonymous method, we focus on k-anonymization technique to realize a `forest from the trees' as described above. In papers in which these methods are proposed, only qualitative analyze or examples are shown that demonstrate the usefulness of anonymized data, which are the outputs of those methods. Since it is generally said that, if the size of data gets bigger, the anonymization of data becomes easier, those methods have not been applied to real huge data. In this paper, we transform the travel records of 722,000 people traveling by train in the Tokyo area with our proposed anonymization methods, analyze the degree to which each of the results is useful, and conclude that the results are useless even when anonymity level is set to low.

Recent research in privacy-preserving data mining (PPDM) has become increasingly popular due to the wide application of data mining and the increased concern regarding the protection of private and personal information. Lately, numerous methods of privacy-preserving data mining have been proposed. Most of these methods are based on an assumption that semi-honest is and collusion is not present. In other words, every party follows such protocol properly with the exception that it keeps a record of all its intermediate computations without sharing the record with others. In this paper, we focus our attention on the problem of collusions, in which some parties may collude and share their record to deduce the private information of other parties. In particular, we consider a general problem in PPDM - multiparty secure computation of some functions of secure summations of data spreading around multiple parties. To solve such a problem, we propose a new method that entails a high level of security - full-privacy. With this method, no sensitive information of a party will be revealed even when all other parties collude. In addition, this method is efficient with a running time of O(m). We will also show that by applying this general method, a large number of problems in PPDM can be solved with enhanced security.

The purpose of this paper is to propose a new real-coded genetic algorithm (RCGA) named Networked Genetic Algorithm (NGA) that intends to find multiple optima simultaneously in deceptive globally multimodal landscapes. Most current techniques such as niching for finding multiple optima take into account big valley landscapes or non-deceptive globally multimodal landscapes but not deceptive ones called UV-landscapes. Adaptive Neighboring Search (ANS) is a promising approach for finding multiple optima in UV-landscapes. ANS utilizes a restricted mating scheme with a crossover-like mutation in order to find optima in deceptive globally multimodal landscapes. However, ANS has a fundamental problem that it does not find all the optima simultaneously in many cases. NGA overcomes the problem by an adaptive parent-selection scheme and an improved crossover-like mutation. We show the effectiveness of NGA over ANS in terms of the number of detected optima in a single run on Fletcher and Powell functions as benchmark problems that are known to have UV-landscapes. We also analyze the behavior of NGA to confirm that the adaptive parent-selection scheme contributes the performance of NGA.

Premature convergence is one of the most notable obstacles that GAs face with. Once it happens, GAs cannot generate candidate solutions globally and the solutions are finally captured by local minima. To overcome it, we propose a mechanism that indirectly controls the variety of the population. It is realized by adapting the expansion rate parameter of crossovers, which determines the variance of the crossover distribution. The resulting algorithm is called adaptation of expansion rate (AER). The performance of the proposed methods is compared to an existing GA on several benchmark functions including functions whose landscape have ridge or multimodal structure. On these functions, existing GAs are likely to lead to premature convergence. The experimental result shows our approach outperforms the existing one on deceptive functions without disturbing the performance on comparatively easy problems.

Link analysis methods have been used successfully for knowledge discovery from the link structure of mutually linking entities. Existing link analysis methods have been inherently designed based on the fact that the entire link structure of the target graph is observable such as public web documents; however, link information in graphs in the real world, such as human relationship or economic activities, is rarely open to public. If link analysis can be performed using graphs with private links in a privacy-preserving way, it enables us to rank entities connected with private ties, such as people, organizations, or business transactions. In this paper, we present a secure link analysis for graphs with private links by means of cryptographic protocols. Our solutions are designed as privacy-preserving expansions of well-known link analysis methods, PageRank and HITS. The outcomes of our protocols are completely equivalent to those of PageRank and HITS. Furthermore, our protocols theoretically guarantee that the private link information possessed by each node is not revealed to other nodes. %We demonstrate the efficiency of our solution by experimental studies, comparing with existing solutions, such as secure function evaluation, decentralized spectral analysis, and privacy-preserving link-analysis.

This paper aims the design of efficient and effective optimization algorithms for function optimization. This paper presents a new framework of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Recent studies modified the CMA-ES from the viewpoint of covariance matrix adaptation and resulted in drastic reduction of the number of generations. In addition to their modification, this paper modifies the CMA-ES from the viewpoint of step size adaptation. The main idea of modification is semantically specializing functions of covariance matrix adaptation and step size adaptation. This new method is evaluated on 8 classical unimodal and multimodal test functions and the performance is compared with standard CMA-ES. The experimental result demonstrates an improvement of the search performances in particular with large populations. This result is mainly because the proposed Hybrid-SSA instead of the existing CSA can adjust the global step length more appropriately under large populations and function specialization helps appropriate adaptation of the overall variance of the mutation distribution.

We consider the problem of distributed reinforcement learning (DRL) from private perceptions. In our setting, agents' perceptions, such as states, rewards, and actions, are not only distributed but also should be kept private. Conventional DRL algorithms can handle multiple agents, but do not necessarily guarantee privacy preservation and may not guarantee optimality. In this work, we design cryptographic solutions that achieve optimal policies without requiring the agents to share their private information.

Although multi-objective GA (MOGA) is an efficient multi-objective optimization (MOO) method, it has some limitations that need to be tackled, which include unguaranteed uniformity of solutions and uncertain finding of periphery of Pareto-optimal solutions. It has been shown that, on bi-objective problems, which are the subject of this paper, local Pareto-optimal solutions form curves. In this case, some of the limitations of MOGA can be resolved by sampling the curves uniformly in the variable space and in the objective space. This paper proposes Pareto Path Following (PPF) which does the sampling by extending the framework of Numerical Path Following, verifies that PPF exhibits the desired behaviors, and addresses the extension of PPF for problems with more than two objective functions.Application of PPF is not limited to refinement of solutions obtained with MOGA. PPF makes it natural to have a local Pareto-optimal solution curve as the unit of search, which leads to curve-based MOGA. PPF also enables examination of which Pareto-optimal solution curves are found by MOO methods, and performance metrics based on it can be defined. This paper proposes these applications of PPF in MOGA and compares standard MOGA and curve-based MOGA using the metrics to reveal their characteristics.

We propose a protocol for a local search and a genetic algorithm for the distributed traveling salesman problem (TSP). In the distributed TSP, information regarding the cost function such as traveling costs between cities and cities to be visited are separately possessed by distributed parties and both are kept private each other. We propose a protocol that securely solves the distributed TSP by means of a combination of genetic algorithms and a cryptographic technique, called the secure multiparty computation. The computation time required for the privacy preserving optimization is practical at some level even when the city-size is more than a thousand.

This paper describes a GA based lazy approach toward reinforcement learning. This approach employs data-driven policy, which is composed of an instance set and an instance-based action selector. This feature provides a number of advantages. However some difficulties remain uninvestigated. One of them is the huge and complicated search space. We have an idea that preserving characteristics of the GA population and introducing new characteristics can overcome these difficulties. On the basis of this idea, we propose two genetic operators; Binomial Distribution Crossover (BDX) and iterated refreshment. The BDX generates the descendants inheriting the parents’ characteristics and the iterated refreshment introduces new characteristics greedily. The GA powered by these operators was applied to the benchmark tasks to demonstrate the ability. Each operator also was investigated and discussed from the various perspectives. Finally, we provide the preferable parameter settings for our method.

Genetic Algorithm (GA) is known as a potent multiobjective optimization method, and the effectiveness of hybridizing it with local search (LS) has recently been reported in the literature. However, there is a relatively small number of studies on LS methods for multiobjective function optimization. Although each of the existing LS methods has some strong points, they have respective drawbacks such as high computational cost and inefficiency in improving objective functions. Hence, a more effective and efficient LS method is being sought, which can be used to enhance the performance of the hybridization.Defining Pareto descent directions as descent directions to which no other descent directions are superior in improving all objective functions, this paper proposes a new LS method, Pareto Descent Method (PDM), which finds Pareto descent directions and moves solutions in such directions thereby improving all objective functions simultaneously. In the case part or all of them are infeasible, it finds feasible Pareto descent directions or descent directions as appropriate. PDM finds these directions by solving linear programming problems, which is computationally inexpensive. Experiments have shown PDM's superiority over existing methods.

The function optimization is one of the most important optimization problems. In approaches to function optimization by evolutionary computation, a real-coded genetic algorithm, UNDX+MGG, shows good performance on multimodal functions with epistasis among parameters. However, UNDX+MGG has a problem that its performance is good on functions with big valley structures but deteriorates on those with the UV structures. On the other hand, ISM shows good performance on functions with the UV structures. However, ISM has two problems that 1) it fails in search when the region of the V valley including the optimum is very narrow and 2) its performance deteriorates on functions with big valley structures. In this paper, we propose a new evolutionary algorithm that aims at overcoming the problems of UNDX+MGG and ISM and examine its effectiveness through some experiments.

In this paper, we propose a GA model called Adaptive Isolation Model(AIM), for multimodal optimization. It uses a data clustering algorithm to detect clusters in GA population, which identifies the attractors in the fitness landscape. Then, subpopulations which makes-up the clusters are isolated and optimized independently. Meanwhile, the region of the isolated subpopulations in the original landscape are suppressed. The isolation increases comprehensiveness, i.e., the probability of finding weaker attractors, and the overall efficiency of multimodal search. The advantage of the AIM is that it does not require distance between the optima as a presumed parameter, as it is estimated from the variance/covariance matrix of the subpopulation.Further, AIM's behavior and efficiency is equivalent to basic GA in unimodal landscape, in terms of number of evaluation. Therefore, it is applied recursively to all subpopulations until they converge to a suboptima. This makes AIM suitable for locally-multimodal landscapes, which have closely located attractors that are difficult to distinguish in the initial run.The performance of AIM is evaluated in several benchmark problems and compared to iterated hill-climbing methods.

This paper presents a kernel density estimation method by means of real-coded crossovers. Estimation of density algorithms (EDAs) are evolutionary optimization techniques, which determine the sampling strategy by means of a parametric probabilistic density function estimated from the population. Real-coded Genetic Algorithm (RCGA) does not explicitly estimate any probabilistic distribution, however, the probabilistic model of the population is implicitly estimated by crossovers and the sampling strategy is determined by this implicit probabilistic model. Based on this understanding, we propose a novel density estimation algorithm by using crossovers as nonparametric kernels and apply this kernel density estimation to the Gaussian Mixture modeling. We show that the proposed method is superior in the robustness of the computation and in the accuracy of the estimation by the comparison of conventional EM estimation.

This paper presents the Real-coded Genetic Algorithms for high-dimensional ill-scaled structures, what is called, the k-tablet structure. The k-tablet structure is the landscape that the scale of the fitness function is different between a k-dimensional subspace and the orthogonal (n−k)-dimensional subspace. The search speed of traditional GAs degrades when a high dimensional k-tablet structure is included in the landscape of the fitness function. In this structure, offspring generated by crossovers are likely to spread wider region than the region where the parental population covers and this causes the stagnation of the search. To resolve this problem, we propose a new crossover LUNDX-m using only m-dimensional latent variables. The effectiveness of the proposal method is tested with several benchmark functions including k-tablet structures and we show that our proposed method performs better than traditional crossovers especially when the dimensionality n is higher than 100. As an example of a k-tablet structure in real world applications, we show that the lens design problem has a kind of k-tablet structures and that our proposed method also performs better than conventional crossovers in this problem.

This paper introduces a practical index for approximate similarity queries of large multi-dimensional data sets: the spatial approximation sample hierarchy (SASH). A SASH is a multi-level structure of random samples, recursively constructed by building a SASH on a large randomly selected sample of data objects, and then connecting each remaining object to several of their approximate nearest neighbors from within the sample. Queries are processed by first locating approximate neighbors within the sample, and then using the pre-established connections to discover neighbors within the remainder of the data set. The SASH index relies on a pairwise distance measure, but otherwise makes no assumptions regarding the representation of the data. Experimental results are provided for query-by-example operations on protein sequence, image, and text data sets, including one consisting of more than 1 million vectors spanning more than 1.1 million terms - far in excess of what spatial search indices can handle efficiently. For sets of this size, the SASH can return a large proportion of the true neighbors roughly 2 orders of magnitude faster than sequential search.

Proposes a new real-coded genetic algorithm (GA) using the combination of two crossovers: UNDX-m (unimodal normal distribution crossover - modified) and EDX (extrapolation-directed crossover). The search region of UNDX-m tends to be biased toward the inside of the area that the population of the GA covers. Because of this search bias, the GA using UNDX-m causes stagnation of its search if the cost surface has a certain kind of structure - viz. the so-called ridge structure or multiple-peak structure. In order to compensate for this fault of UNDX-m, we propose a new crossover - EDX - which has an extrapolative search area, and we show its effectiveness through numerical experiments.