Yixuan Wang, Yue Huang, Hong Qian, Yunzhao Wei, Yifei Ding, Wenkai Wang, Zhi Liu, Zhongjing Huang, Aimin Zhou, Jiajun Guo. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Learner-item cognitive modeling plays a central role in the web-based online intelligent education system by enabling cognitive diagnosis (CD) across diverse online educational scenarios. Although ID embedding remains the mainstream approach in cognitive modeling due to its effectiveness and flexibility, recent advances in language models (LMs) have introduced new possibilities for incorporating rich semantic representations to enhance CD performance. This highlights the need for a comprehensive analysis of how LMs enhance embeddings through semantic integration across mainstream CD tasks. This paper identifies two key challenges in fully leveraging LMs in existing work: Misalignment between the training objectives of LMs and CD models creates a distribution gap in feature spaces; A unified framework is essential for integrating textual embeddings across varied CD tasks while preserving the strengths of existing cognitive modeling paradigms to ensure the robustness of embedding enhancement. To address these challenges, this paper introduces EduEmbed, a unified embedding enhancement framework that leverages fine-tuned LMs to enrich learner-item cognitive modeling across diverse CD tasks. EduEmbed operates in two stages. In the first stage, we fine-tune LMs based on role-specific representations and an interaction diagnoser to bridge the semantic gap of CD models. In the second stage, we employ a textual adapter to extract task-relevant semantics and integrate them with existing modeling paradigms to improve generalization. We evaluate the proposed framework on four CD tasks and computerized adaptive testing (CAT) task, achieving robust performance. Further analysis reveals the impact of semantic information across diverse tasks, offering key insights for future research on the application of LMs in CD for online intelligent education systems.

In this paper, we introduce a novel approach for addressing the multi-objective optimization problem in large language model merging via black-box multi-objective optimization algorithms. The goal of model merging is to combine multiple models, each excelling in different tasks, into a single model that outperforms any of the individual source models. However, the effectiveness of conventional model merging methods is constrained by human intuition or domain knowledge. While existing optimization-based model merging methods can automatically search for model merging parameter configurations, they often struggle to find a satisfactory configuration within a limited evaluation budget. To address this challenge, we propose a novel and sample-efficient automated model merging method, named MM-MO. This method leverages multi-objective Bayesian optimization algorithms to autonomously search for great merging configurations across various tasks. In MMMO, we proposed an enhanced acquisition strategy and an auxiliary optimization objective to improve the search process. Our enhanced acquisition strategy integrates a weak-to-strong method to refine the acquisition function, enabling previously evaluated superior configurations to guide the search for new ones. Meanwhile, Fisher information is utilized to further filter these configurations, increasing the possibility of finding high-quality merging configurations. Additionally, we design a sparsity metric as an auxiliary optimization objective, further enhance the models generalization performance across different tasks. We conducted comprehensive experiments with other mainstream model merging methods, demonstrating that the proposed MMMO algorithm is competitive and effective in achieving high-quality model merging.

Multi-objective Bayesian optimization (MOBO) has shown promising performance on various expensive multi-objective optimization problems (EMOPs). However, effectively modeling complex distributions of the Pareto optimal solutions is difficult with limited function evaluations. Existing Pareto set learning algorithms may exhibit considerable instability in such expensive scenarios, leading to significant deviations between the obtained solution set and the Pareto set (PS). In this paper, we propose a novel Composite Diffusion Model based Pareto Set Learning algorithm (CDM-PSL) for expensive MOBO. CDM-PSL includes both unconditional and conditional diffusion model for generating high-quality samples efficiently. Besides, we introduce a weighting method based on information entropy to balance different objectives. This method is integrated with a guiding strategy to appropriately balancing different objectives during the optimization process. Experimental results on both synthetic and real-world problems demonstrates that CDM-PSL attains superior performance compared with state-of-the-art MOBO algorithms.

Offline black-box optimization aims to identify the optimal solution of a black-box objective function under the guidance of a surrogate model constructed solely from a pre-collected dataset. It is commonly used in industrial scenarios, which often involve constraints, i.e., constrained offline optimization (COO). Offline optimization has progressed in addressing the out-of-distribution (OOD) issue caused by its inherent inability to interact with the objective function. However, there is not enough research in addressing more difficult scenarios, which must simultaneously address OOD issues and constrained issues to find stable, high-quality (i.e., high-scoring and feasible) solutions. To bridge this gap, this paper proposes a method called constrained offline optimization via risk evaluation and management (COOREM), which is capable of consistently surpassing the offline dataset under the condition of satisfying constraints. Specifically, COOREM employs a dual-energy model to separately evaluate OOD risk and constrained risk. This separation strategy aims to distinguish and address two difficult cases: the infeasible but not OOD solutions and the feasible but OOD solutions. Moreover, COOREM effectively manages OOD risk and constrained risk, ensuring the identification of high-quality solutions. Extensive experiments on real-world tasks, e.g., space missions, process synthesis, and design problems, showcase COOREM's effectiveness in managing both OOD risk and constrained risk. Furthermore, our findings indicate that COOREM could outperform online methods that need to access the objective function in certain space missions.

Diagnostic models aim to precisely infer individuals’ cognitive or non-cognitive competencies from their response logs, such as mathematical or social-emotional skills. While deep learning shows success in cognitive diagnosis, it remains underexplored in the equally important area of non-cognitive trait diagnosis. Accurate non-cognitive trait estimation is critical for individuals’ development. Unlike cognitive assessments using right or wrong responses, non-cognitive trait assessments typically use subjective Likert-scale items with ordinal polytomous options to reflect latent trait levels. Furthermore, individual response styles, such as tendencies toward higher or lower options, introduce bias in trait inference, causing estimations that deviate from true trait levels. Thus, maintaining options ordinal semantic structure and mitigating the response style bias in trait estimation are two major challenges for accurate trait diagnosis. To address these issues, this paper proposes a Style-Aware Polytomous Diagnosis (SAPD) model. Specifically, to capture the ordinal semantics of response options, SAPD constructs an Ordinal Option Graph (OOG) that explicitly encodes the ordinal relationship among polytomous options, where higher options reflect higher latent trait levels. To mitigate the bias caused by individual response styles, we first design a Style-Aware Relational Graph (SARG), a heterogeneous graph that integrates multiple interactions among participants, items, options and traits, implicitly embedding response style information within node representations. We then propose a Response Style Corrector (RSC) that explicitly captures individual response tendencies and disentangles response style bias during trait diagnosis, allowing for dynamic and adaptive correction of trait levels. Extensive experiments on five real-world datasets show that SAPD improves accuracy by an average of 4% over competitive methods. Visualizations confirm SAPD effectively disentangles response style effects, leading to more accurate and interpretable trait diagnosis.

Optimization problems are prevalent across various scenarios. Formulating and then solving optimization problems described by natural language often requires highly specialized human expertise, which could block the widespread application of optimization-based decision making. To automate problem formulation and solving, leveraging large language models (LLMs) has emerged as a potential way. However, this kind of approach suffers from the issue of optimization generalization. Namely, the accuracy of most current LLM-based methods and the generality of optimization problem types that they can model are still limited. In this paper, we propose a unified learning-based framework called LLMOPT to boost optimization generalization. Starting from the natural language descriptions of optimization problems and a pre-trained LLM, LLMOPT constructs the introduced five-element formulation as a universal model for learning to define diverse optimization problem types. Then, LLMOPT employs the multi-instruction tuning to enhance both problem formalization and solver code generation accuracy and generality. After that, to prevent hallucinations in LLMs, such as sacrificing solving accuracy to avoid execution errors, the model alignment and self-correction mechanism are adopted in LLMOPT. We evaluate the optimization generalization ability of LLMOPT and compared methods across six real-world datasets covering roughly 20 fields such as health, environment, energy and manufacturing, etc. Extensive experiment results show that LLMOPT is able to model various optimization problem types such as linear/nonlinear programming, mixed integer programming, and combinatorial optimization, and achieves a notable 11.08% average solving accuracy improvement compared with the state-of-the-art methods. The code is available at https://github.com/caigaojiang/LLMOPT.

Recommender systems aim to predict personalized item rankings by modeling user preference distributions derived from historical behavior data. While diffusion models (DMs) have recently gained attention for their ability to model complex distributions, current DM-based recommenders typically rely on traditional objectives such as mean squared error (MSE) or standard recommendation objectives. These approaches are either suboptimal for personalized ranking tasks or fail to exploit the full generative potential of DMs. To address these limitations, we propose \textbf{PreferDiff}, an optimization objective tailored for DM-based recommenders. PreferDiff reformulates the traditional Bayesian Personalized Ranking (BPR) objective into a log-likelihood generative framework, enabling it to effectively capture user preferences by integrating multiple negative samples. To handle the intractability, we employ variational inference, minimizing the variational upper bound. Furthermore, we replace MSE with cosine error to improve alignment with recommendation tasks, and we balance generative learning and preference modeling to enhance the training stability of DMs. PreferDiff devises three appealing properties. First, it is the first personalized ranking loss designed specifically for DM-based recommenders. Second, it improves ranking performance and accelerates convergence by effectively addressing hard negatives. Third, we establish its theoretical connection to Direct Preference Optimization (DPO), demonstrating its potential to align user preferences within a generative modeling framework. Extensive experiments across six benchmarks validate PreferDiff's superior recommendation performance. Our codes are available at \url{https://github.com/lswhim/PreferDiff}.

Black-box optimization aims to find the optima through building a model close to the black-box objective function based on function value evaluation. However, in many real-world tasks, such as the design of molecular formulas and mechanical structures, it is perilous, costly, or even infeasible to evaluate the objective function value of an actively sampled solution. In this situation, optimization can only be conducted via utilizing offline historical data, which yields offline black-box optimization. Different from the traditional goal that is to pursue the optimal solution, this paper emphasizes that the goal of offline optimization is to stably surpass the offline dataset during optimization procedure. Although benchmarks called Design-Bench already exist in this emerging field, it can hardly evaluate the stability of offline optimization and mainly provides real-world offline tasks and the corresponding offline datasets. To this end, this paper proposes benchmarks named SOO-Bench (i.e., Stable Offline Optimization Benchmarks) for offline black-box optimization algorithms, so as to systematically evaluate the stability of surpassing the offline dataset under different data distributions. Along with SOO-Bench, we also propose a stability indicator to measure the degree of stability. Specifically, SOO-Bench includes various real-world offline optimization tasks and offline datasets under different data distributions, involving the fields of satellites, materials science, structural mechanics, and automobile manufacturing. Empirically, baseline and state-of-the-art algorithms are tested and analyzed on SOO-Bench. Hopefully, SOO-Bench is expected to serve as a catalyst for the rapid developments of more novel and stable offline optimization methods. The code is available at \url{https://github.com/zhuyiyi-123/SOO-Bench}.

Causal discovery aims to identify causal relationships from observational data. Recently, optimization-based causal discovery methods have attracted extensive attention in the literature due to their efficiency in handling high-dimensional problems. However, we observe that optimization-based methods often perform well on certain problems but struggle with others. This paper identifies a specific characteristic of causal structural equations that determines the difficulty of identification in causal discovery and, in turn, the performance of optimization-based methods. We conduct an in-depth study of the additive noise model (ANM) and propose to further divide identifiable problems into strongly and weakly identifiable types based on the difficulty of identification. We also provide a sufficient condition to distinguish the two categories. Inspired by these findings, this paper further proposes GENE, a generic method for addressing strongly and weakly identifiable problems in a unified way under the ANM assumption. GENE adopts an order-based search framework that incorporates conditional independence tests into order fitness evaluation, ensuring effectiveness on weakly identifiable problems. In addition, GENE restricts the dimensionality of the effect variables to ensure scale invariance, a property crucial for practical applications. Experiments demonstrate that GENE is uniquely effective in addressing weakly identifiable problems while also remaining competitive with state-of-the-art causal discovery algorithms for strongly identifiable problems.

Computerized Adaptive Testing (CAT) measures student ability by iteratively selecting informative questions, with core components being the Cognitive Diagnosis Model (CDM) and selection strategy. Current research focuses on optimizing the selection strategy, assuming relatively accurate CDM results. However, existing static CDMs struggle with rapid and accurate diagnosis in the early stage of CAT. To this end, this paper proposes a Fast Adaptive Cognitive Diagnosis (FACD) framework, which incorporates dynamic collaborative and personalized diagnosis modules. Specifically, the collaborative module in FACD uses a dynamic response graph to quickly build student cognitive profiles, while the personalized module leverages each student's response sequence for robust and individualized diagnosis. Extensive experiments on real-world datasets show that, compared with existing static CDMs, FACD not only achieves superior prediction performance across various selection strategies with an improvement between roughly 5%-10% in the early stage of CAT, but also maintains a commendable inference speed.

In black-box optimization, when directly evaluating the function values of solutions is very costly or infeasible, access to the objective function is often limited to comparing pairs of solutions, which yields dueling black-box optimization. Dueling optimization is solely based on pairwise preferences, and thus notably reduces cost compared with function value based methods. However, the optimization performance of dueling optimization is often limited due to that most existing dueling optimization methods do not make full use of the pairwise preferences collected. To better utilize these preferences, this paper proposes relation-augmented dueling Bayesian optimization (RADBO) via preference propagation. By considering solution similarity, RADBO aims to uncover the potential dueling relations between solutions within different preferences through the proposed preference propagation technique. Specifically, RADBO first clusters solutions using a Gaussian mixture model. After obtaining the solution set with the highest intra-cluster similarity, RADBO utilizes a directed hypergraph to model the potential dueling relations between solutions, thereby realizing relation augmentation. Extensive experiments are conducted on both synthetic functions and real-world tasks such as motion control, car cab design and spacecraft trajectory optimization. The experimental results disclose the satisfactory accuracy of augmented preferences in RADBO, and show the superiority of RADBO compared with existing dueling optimization methods. Notably, it is verified that, under the same evaluation cost budget, RADBO can be competitive with or even surpass the function value based Bayesian optimization methods with respect to optimization performance.

Computerized Adaptive Testing (CAT) is a testing technique that accurately infers students' proficiency levels using a relatively small number of questions.Most existing CAT systems operate on a question-level adaptive paradigm, which is suitable for practice scenarios.However, in computerized standardized high-stakes examinations such as the GRE and GMAT, this paradigm faces several challenges: (1) the lack of comparability in exam results, (2) high implementation costs due to the reliance on real-time interactions and the financial burden of maintaining CAT testing system, and (3) the difficulty in balancing multiple factors of diagnosis quality, attribute coverage, and question exposure.To address these challenges, we propose a Paper-level Computerized Adaptive Testing (PCAT) and its corresponding evaluation method.PCAT divides an exam into multiple testing stages, where examinees adaptively receive test papers of varying difficulty based on their performance in previous stages.The paper assembly problem in PCAT is solved using a population-based multi-objective optimization (MOO) approach.PCAT offers several advantages: First, the paper-level adaptive mechanism ensures that the questions faced by examinees depend solely on their performance in the earlier stages, maintaining adaptability while enhancing the comparability of results across different examinees.Second, PCAT replaces the selection strategy module in traditional CAT with an assembly module, allowing computationally intensive tasks such as cognitive diagnosis and paper assembly to be completed offline before the exam, eliminating the need for real-time interactions.Additionally, the population-based MOO approach generates a set of high-quality solutions in one run, meeting the demands of frequent administration of standardized high-stakes exams like the GRE and reducing the financial burden of maintaining a large-scale CAT system.Finally, MOO naturally

Knowledge Tracing (KT) is a crucial task in computer-aided education and intelligent tutoring systems, predicting students’ performance on new questions from their responses to prior ones. An accurate KT model can capture a student’s mastery level of different knowledge topics, as reflected in their predicted performance on different questions. This helps improve the learning efficiency by suggesting appropriate new questions that complement students’ knowledge states. However, current KT models have significant drawbacks that they neglect the imbalanced discrimination of historical responses. A significant proportion of question responses provide limited information for discerning students’ knowledge mastery, such as those that demonstrate uniform performance across different students. Optimizing the prediction of these cases may increase overall KT accuracy, but also negatively impact the model’s ability to trace personalized knowledge states, especially causing a deceptive surge of performance. Towards this end, we propose a framework to reweight the contribution of different responses based on their discrimination in training. Additionally, we introduce an adaptive predictive score fusion technique to maintain accuracy on less discriminative responses, achieving proper balance between student knowledge mastery and question difficulty. Experimental results demonstrate that our framework enhances the performance of three mainstream KT methods on three widely used datasets.

Cognitive diagnosis assessment is a fundamental and crucial task for student learning. It models the student-exercise interaction, and discovers the students' proficiency levels on each knowledge attribute. In real-world intelligent education systems, generalization and interpretability of cognitive diagnosis methods are of equal importance. However, most existing methods can hardly make the best of both worlds due to the complicated student-exercise interaction. To this end, this paper proposes a symbolic cognitive diagnosis~(SCD) framework to simultaneously enhance generalization and interpretability. The SCD framework incorporates the symbolic tree to explicably represent the complicated student-exercise interaction function, and utilizes gradient-based optimization methods to effectively learn the student and exercise parameters. Meanwhile, the accompanying challenge is that we need to tunnel the discrete symbolic representation and continuous parameter optimization. To address this challenge, we propose to hybridly optimize the representation and parameters in an alternating manner. To fulfill SCD, it alternately learns the symbolic tree by derivative-free genetic programming and learns the student and exercise parameters via gradient-based Adam. The extensive experimental results on various real-world datasets show the superiority of SCD on both generalization and interpretability. The ablation study verifies the efficacy of each ingredient in SCD, and the case study explicitly showcases how the interpretable ability of SCD works.

Causal global optimization (CGO) aims to complete optimization tasks through causal inference. In the high-dimensional CGO problems, traditional causal Bayesian optimization (CBO) methods struggle with the curse of dimensionality attributed to the number of variables in the causal graph, and scale inconsistency among Gaussian Process (GP) models. These issues limit the application of CBO in domains requiring optimization over large causal graphs. To address these limitations, this paper proposes a high-dimensional causal Bayesian optimization (HCBO) algorithm. To address the curse of dimensionality, HCBO introduces a submodularity indicator for variable subsets through the concept of causal intrinsic dimensionality (CID). It then uses the submodular optimization algorithm to find approximations of CID within polynomial sample complexity. Theoretically, we disclose a sufficient condition for CID’s existence. To address the issue of scale inconsistency among GP models, HCBO introduces a scale-normalized scoring function, ensuring stable identification of the optimal GP model corresponding to CID for intervention. Extensive experiments are conducted on high-dimensional synthetic and real-world tasks, i.e., coral ecology and health. The existence of CID is verified across the datasets of all tasks. HCBO achieves state-of-the-art performance in CGO problems and can handle causal graphs at a scale 10 times larger than that manageable by previous CBO methods.

The traditional architecture of supercomputers comprises a control unit and heterogeneous accelerators with distinct memory spaces, necessitating developers to code separately for each accelerator. The notion of performance portability has been introduced to facilitate the swift adaptation of a singular codebase across multiple heterogeneous accelerators, enabling the same code to efficiently harness the performance of various platforms with minimal alterations. Frameworks such as Kokkos, RAJA, and YAKL accomplish this through a data parallel model, primarily targeting SIMT devices but also applicable to SIMD devices. With the advent of manycore architectures that provide high levels of parallelism and performance, it becomes imperative to extend performance portability to these architectures, which currently require users to manually partition and map tasks to fully exploit their capabilities. This paper introduces a data parallel programming runtime for the Sunway manycore architecture and adapts YAKL to this platform, termed swYAKL. This runtime capitalizes on the computational characteristics of Sunway, including task division and mapping, and supports Sunway’s CPE LDM and native vectorization. It employs a specialized task division method for multi-dimensional stencil kernels to leverage the DMA capabilities of Sunway’s CPE. Performance evaluations using several common computational kernels and a proxy application named miniWeather indicate that swYAKL achieves speedups exceeding 100x compared to execution on Sunway’s MPE for various workloads, and under specific conditions, it surpasses the performance of the NVIDIA A100 GPU.

Knowledge tracing (KT) is a crucial task in intelligent education, focusing on predicting students' performance on given questions to trace their evolving knowledge. The advancement of deep learning in this field has led to deep-learning knowledge tracing (DLKT) models that prioritize high predictive accuracy. However, many existing DLKT methods overlook the fundamental goal of tracking students' dynamical knowledge mastery. These models do not explicitly model knowledge mastery tracing processes or yield unreasonable results that educators find difficulty to comprehend and apply in real teaching scenarios. In response, our research conducts a preliminary analysis of mainstream KT approaches to highlight and explain such unreasonableness. We introduce GRKT, a graph-based reasonable knowledge tracing method to address these issues. By leveraging graph neural networks, our approach delves into the mutual influences of knowledge concepts, offering a more accurate representation of how the knowledge mastery evolves throughout the learning process. Additionally, we propose a fine-grained and psychological three-stage modeling process as knowledge retrieval, memory strengthening, and knowledge learning/forgetting, to conduct a more reasonable knowledge tracing process. Comprehensive experiments demonstrate that GRKT outperforms eleven baselines across three datasets, not only enhancing predictive accuracy but also generating more reasonable knowledge tracing results. This makes our model a promising advancement for practical implementation in educational settings. The source code is available at https://github.com/JJCui96/GRKT.

Customer segmentation plays a crucial role in credit risk assessment by dividing users into specific risk levels based on their credit scores. Previous methods fail to comprehensively consider the stability in the segmentation process, resulting in frequent changes and inconsistencies in users' risk levels over time. This increases potential risks to a company. To this end, this paper at first introduces and formalizes the concept of stability regret in the segmentation process. However, evaluating stability is challenging due to its black-box nature and the computational burden posed by vast user data sets. To address these challenges, this paper proposes a large-scale stable customer segmentation approach named LASCA. LASCA consists of two phases: high-quality dataset construction (HDC) and reliable data-driven optimization (RDO). Specifically, HDC utilizes an evolutionary algorithm to collect high-quality binning solutions. RDO subsequently builds a reliable surrogate model to search for the most stable binning solution based on the collected dataset. Extensive experiments conducted on real-world large-scale datasets (up to 0.8 billion) show that LASCA surpasses the state-of-the-art binning methods in finding the most stable binning solution. Notably, HDC greatly enhances data quality by 50%. RDO efficiently discovers more stable binning solutions with a 36% improvement in stability, accelerating the optimization process by 25 times via data-driven evaluation. Currently, LASCA has been successfully deployed in the large-scale credit risk assessment system of Alipay.

Cognitive diagnosis models (CDMs) are designed to learn students' mastery levels using their response logs.CDMs play a fundamental role in online education systems since they significantly influence downstream applications such as teachers' guidance and computerized adaptive testing.Despite the success achieved by existing CDMs, we find that they suffer from a thorny issue that the learned students' mastery levels are too similar.This issue, which we refer to as oversmoothing, could diminish the CDMs' effectiveness in downstream tasks.CDMs comprise two core parts: learning students' mastery levels and assessing mastery levels by fitting the response logs.This paper contends that the oversmoothing issue arises from that existing CDMs seldom utilize response signals on exercises in the learning part but only use them as labels in the assessing part.To this end, this paper proposes an oversmoothing-resistant cognitive diagnosis framework (ORCDF) to enhance existing CDMs by utilizing response signals in the learning part.Specifically, OR-CDF introduces a novel response graph to inherently incorporate response signals as types of edges.Then, ORCDF designs a tailored response-aware graph convolution network (RGC) that effectively captures the crucial response signals within the response graph.Via ORCDF, existing CDMs are enhanced by replacing the input embeddings with the outcome of RGC, allowing for the consideration of response signals on exercises in the learning part.Extensive experiments on real-world datasets show that ORCDF not only *

Cognitive diagnosis is a vital upstream task in intelligent education systems. It models the student-exercise interaction, aiming to infer the students' proficiency levels on each knowledge concept. This paper observes that most existing methods can hardly effectively capture the homogeneous influence due to its inherent complexity. That is to say, although students exhibit similar performance on given exercises, their proficiency levels inferred by these methods vary significantly, resulting in shortcomings in interpretability and efficacy. Given the complexity of homogeneous influence, a hypergraph could be a choice due to its flexibility and capability of modeling high-order similarity which aligns with the nature of homogeneous influence. However, before incorporating hypergraph, one at first needs to address the challenges of distorted homogeneous influence, sparsity of response logs, and over-smoothing. To this end, this paper proposes a hypergraph cognitive diagnosis model (HyperCDM) to address these challenges and effectively capture the homogeneous influence. Specifically, to avoid distortion, HyperCDM employs a divide-and-conquer strategy to learn student, exercise and knowledge representations in their own hypergraphs respectively, and interconnects them via a feature-based interaction function. To construct hypergraphs based on sparse response logs, the auto-encoder is utilized to preprocess response logs and K-means is applied to cluster students. To mitigate over-smoothing, momentum hypergraph convolution networks are designed to partially keep previous representations during the message propagation. Extensive experiments on both offline and online real-world datasets show that HyperCDM achieves state-of-the-art performance in terms of interpretability and capturing homogeneous influence effectively, and is competitive in generalization. The ablation study verifies the efficacy of each component, and the case study explicitly showcases the homogeneous influence captured by HyperCDM.

The fraudulent insurance claim is critical for the insurance industry.Insurance companies or agency platforms aim to confidently estimate the fraud risk of claims by gathering data from various sources.Although more data sources can improve the estimation accuracy, they inevitably lead to increased costs.Therefore, a great challenge of fraud risk verification lies in well balancing these two aspects.To this end, this paper proposes a framework named cost-efficient fraud risk optimization with submodularity (CEROS) to optimize the process of fraud risk verification.CEROS efficiently allocates investigation resources across multiple information sources, balancing the trade-off between accuracy and cost.CEROS consists of two parts that we propose: a submodular set-wise classification model * Equal Contribution.

In modern telecommunication networks, faults manifest as alarms, generating thousands of events daily. Network operators need an efficient method to identify the root causes of these alarms to mitigate potential losses. This task is challenging due to the increasing scale of telecommunication networks and the interconnected nature of devices, where one fault can trigger a cascade of alarms across multiple devices within a topological network. Recent years have seen a growing focus on causal approaches to addressing this problem, emphasizing the importance of learning a Granger causal graph from topological event sequences. Such causal graphs delineate the relations among alarms and can significantly aid engineers in identifying and rectifying faults. However, existing methods either ignore the topological relationships among devices or suffer from relatively low scalability and efficiency, failing to deliver high-quality responses in a timely manner. To this end, this paper proposes $S^2GCSL$, a simple yet scalable Granger causal structural learning approach for topological event sequences. $S^2GCSL$ utilizes a linear kernel to model activation interactions among various event types within a topological network, and employs gradient descent to efficiently optimize the likelihood function. Notably, it can seamlessly incorporate expert knowledge as constraints within the optimization process, which enhances the interpretability of the outcomes. Extensive experimental results on both large-scale synthetic and real-world problems verify the scalability and efficacy of $S^2GCSL$.

Derivative-free optimization has achieved remarkable success across a variety of applications where the explicit formulation of an objective function is inaccessible. Learning an accurate surrogate model from solutions and their function values is crucial for derivative-free optimization. Methods for constructing global surrogate models, such as Bayesian optimization (BO), encounter the challenge of high learning cost, which impairs optimization efficiency. Splitting the entire search domain into smaller regions, a series of domain partition methods are proposed, like simultaneous optimistic optimization (SOO). It has demonstrated notable effectiveness in derivative-free optimization but still has room for improvement due to its relatively coarse-grained partition strategy. To this end, this paper proposes a fine-grained simultaneous optimistic optimization (FGSOO) method with local Gaussian process. Specifically, FGSOO designs a fine-grained partition strategy to endow SOO with the capability of cross-height comparison, and utilizes local Gaussian process to make nodes' potential more representative, so as to reduce the required number of solutions for learning surrogate models. Compared with BO, FGSOO reduces the learning cost. Meanwhile, compared with SOO, FGSOO could avoid unnecessary partition. The experimental results on real-world tasks, such as trajectory optimization and molecule substructure optimization, verify that FGSOO surpasses the compared methods in improving efficiency while maintaining effectiveness.

Cognitive diagnosis aims to gauge students' mastery levels based on their response logs. Serving as a pivotal module in web-based online intelligent education systems (WOIESs), it plays an upstream and fundamental role in downstream tasks like learning item recommendation and computerized adaptive testing. WOIESs are open learning environment where numerous new students constantly register and complete exercises. In WOIESs, efficient cognitive diagnosis is crucial to fast feedback and accelerating student learning. However, the existing cognitive diagnosis methods always employ intrinsically transductive student-specific embeddings, which become slow and costly due to retraining when dealing with new students who are unseen during training. To this end, this paper proposes an inductive cognitive diagnosis model (ICDM) for fast new students' mastery levels inference in WOIESs. Specifically, in ICDM, we propose a novel student-centered graph (SCG). Rather than inferring mastery levels through updating student-specific embedding, we derive the inductive mastery levels as the aggregated outcomes of students' neighbors in SCG. Namely, SCG enables to shift the task from finding the most suitable student-specific embedding that fits the response logs to finding the most suitable representations for different node types in SCG, and the latter is more efficient since it no longer requires retraining. To obtain this representation, ICDM consists of a construction-aggregation-generation-transformation process to learn the final representation of students, exercises and concepts. Extensive experiments across real-world datasets show that, compared with the existing cognitive diagnosis methods that are always transductive, ICDM is much more faster while maintains the competitive inference performance for new students.

In many scenarios of black-box optimization, evaluating the objective function values of solutions is expensive, while comparing a pair of solutions is relatively cheap, which yields the dueling black-box optimization. The side effect of dueling optimization is that it doubles the dimension of solution space and exacerbates the dimensionality scalability issue of black-box optimization, e.g., Bayesian optimization. To address this issue, the existing dueling optimization methods fix one solution when dueling throughout the optimization process, but it may reduce their efficacy. Fortunately, it has been observed that, in recommendation systems, the dueling results are mainly determined by the latent human preferences. In this paper, we abstract this phenomenon as the preferential intrinsic dimension and inject it into the dueling Bayesian optimization, resulting in the preferential embedding dueling Bayesian optimization (PE-DBO). PE-DBO decouples optimization and pairwise comparison via the preferential embedding matrix. Optimization is performed in the preferential intrinsic subspace with much lower dimensionality, while pairwise comparison is completed in the original dueling solution space. Theoretically, we disclose that the preference function can be approximately preserved in the lower-dimensional preferential intrinsic subspace. Experiment results verify that, on molecule discovery and web page recommendation dueling optimization tasks, the preferential intrinsic dimension exists and PE-DBO is superior in scalability compared with that of the state-of-the-art (SOTA) methods.

Cognitive diagnosis is vital for intelligent education to determine students’ knowledge mastery levels from their response logs. The Q-matrix, representing the relationships between exercises and knowledge attributes, improves the interpretability of cognitive diagnosis models. However, completing the Q-matrix poses an expensive and challenging task due to the fine-grained division of knowledge attributes. Moreover, a manually sparse Q-matrix can also compromise the accuracy and interpretability of deducing students’ mastery levels, especially for infrequently observed or unseen knowledge attributes. To address this issue, this paper proposes a Q-augmented Causal Cognitive Diagnosis Model (QCCDM) for student learning. Specifically, QCCDM incorporates the structure causal model (SCM) to capture the causality between students’ mastery levels on different attributes, which enables to infer their proficiency on rarely observed knowledge attributes with better accuracy and interpretability. Notably, with SCM, one can guide students on how to realize their self-improvement through intervention. Furthermore, we propose to augment the Q-matrix in QCCDM, which uses the manual Q-matrix as a prior to deduce the relationships between exercises and explicit as well as latent knowledge attributes, resulting in a complete and comprehensive assessment of students’ abilities. We assess the efficacy of Q-augmentation across the widely-used Q-based cognitive diagnosis models and conduct the ablation study. The extensive experimental results on real-world datasets show that QCCDM outperforms the compared methods in terms of both accuracy and interpretability.

Offline optimization aims to elaborately construct a solution that optimizes a black-box function with only access to the offline dataset. A typical manner of constructing the solution is to train a surrogate model of the black-box function on the offline dataset and optimize the solution guided by the surrogate model. However, this manner often encounters a fundamental challenge that the surrogate model could erroneously estimate out-of-distribution (OOD) solutions. Therefore, the optimizer would be misled to produce inferior solutions for online applications, i.e., degradation of performance. To this end, this paper formalizes the risk of degradation for OOD solutions and proposes an accumulative risk controlled offline optimization (ARCOO) method. Specifically, ARCOO learns a surrogate model in conjunction with an energy model. The energy model characterizes the risk of degradation by learning on high-risk solutions and low-risk ones contrastively. In the optimization procedure, the behavior of the optimizer in each step is controlled by a risk suppression factor calculated via the energy model, which leads to the controllable accumulative risk. Theoretically, we justify the efficacy of energy for accumulative risk control. Extensive experiments on offline optimization tasks show that ARCOO surpasses state-of-the-art methods in both degradation-resistance and optimality of the output solution.

Due to computationally and/or financially costly evaluation, tackling expensive multi-objective optimization problems is quite challenging for evolutionary algorithms. One popular approach to these problems is building cheap surrogate models to replace the expensive real function evaluations. To this end, various kinds of surrogate-assisted evolutionary algorithms (SAEAs) have been proposed, building surrogate models which predict the fitness values, classifications, or relation of the candidate solutions. However, off-spring generation, despite its important role in evolutionary optimization, has not received enough attention in these SAEAs. In this paper, a regularity model based framework, namely RM-SAEA, is proposed for better offspring generation in expensive multi-objective optimization. To be specific, RM-SAEA is featured with a heterogeneous offspring generation module, which is composed of a regularity model and a general genetic operator. Moreover, in order to alleviate the data deficiency issue in the expensive optimization scenario, a data augmentation strategy is employed while training the regularity model. Finally, two representative SAEAs are embedded into RM-SAEA in order to instantiate the proposed framework. Experimental results on benchmark multi-objective problems with up to 10 objectives demonstrate that RM-SAEA achieves the best overall performance compared with 6 state-of-the-art algorithms.

Most downstream adaptation methods tune all or part of the parameters of pre-trained models (PTMs) through gradient descent, where the tuning cost increases linearly with the growth of the model size.By contrast, gradient-free methods only require the forward computation of the PTM to tune the prompt, retaining the benefits of efficient tuning and deployment.Though, past work on gradient-free tuning often introduces gradient descent to seek a good initialization of prompt and lacks versatility across tasks and PTMs.In this paper, we present BBTv2, an improved version of Black-Box Tuning (Sun et al., 2022b), to drive PTMs for few-shot learning.We prepend continuous prompts to every layer of the PTM and propose a divide-and-conquer gradient-free algorithm to optimize the prompts at different layers alternately.Extensive experiments across various tasks and PTMs show that BBTv2 can achieve comparable performance to full model tuning and state-of-the-art parameter-efficient methods (e.g., Adapter, LoRA, BitFit, etc.) under few-shot settings while maintaining much fewer tunable parameters.

Teaching dimension (TD) is a fundamental theoretical property for understanding machine teaching algorithms. It measures the sample complexity of teaching a target hypothesis to a learner. The TD of linear learners has been studied extensively, whereas the results of teaching non-linear learners are rare. A recent result investigates the TD of polynomial and Gaussian kernel learners. Unfortunately, the theoretical bounds therein show that the TD is high when teaching those non-linear learners. Inspired by the fact that regularization can reduce the learning complexity in machine learning, a natural question is whether the similar fact happens in machine teaching. To answer this essential question, this paper proposes a unified theoretical framework termed STARKE to analyze the TD of regularized kernel learners. On the basis of STARKE, we derive a generic result of any type of kernels. Furthermore, we disclose that the TD of regularized linear and regularized polynomial kernel learners can be strictly reduced. For regularized Gaussian kernel learners, we reveal that, although their TD is infinite, their epsilon-approximate TD can be exponentially reduced compared with that of the unregularized learners. The extensive experimental results of teaching the optimization-based learners verify the theoretical findings.

Extremely large pre-trained language models (PTMs) such as GPT-3 are usually released as a service. It allows users to design task-specific prompts to query the PTMs through some black-box APIs. In such a scenario, which we call Language-Model-as-a-Service (LMaaS), the gradients of PTMs are usually unavailable. Can we optimize the task prompts by only accessing the model inference APIs? This paper proposes the black-box tuning framework to optimize the continuous prompt prepended to the input text via derivative-free optimization. Instead of optimizing in the original high-dimensional prompt space, which is intractable for traditional derivative-free optimization, we perform optimization in a randomly generated subspace due to the low intrinsic dimensionality of large PTMs. The experimental results show that the black-box tuning with RoBERTa on a few labeled samples not only significantly outperforms manual prompt and GPT-3’s in-context learning, but also surpasses the gradient-based counterparts, i.e., prompt tuning and full model tuning.

Intratumor cellular heterogeneity and non-genetic cell plasticity in tumors pose a recently recognized challenge to cancer treatment. Because of the dispersion of initial cell states within a clonal tumor cell population, a perturbation imparted by a cytocidal drug only kills a fraction of cells. Due to dynamic instability of cellular states the cells not killed are pushed by the treatment into a variety of functional states, including a "stem-like state" that confers resistance to treatment and regenerative capacity. This immanent stress-induced stemness competes against cell death in response to the same perturbation and may explain the near-inevitable recurrence after any treatment. This double-edged-sword mechanism of treatment complements the selection of preexisting resistant cells in explaining post-treatment progression. Unlike selection, the induction of a resistant state has not been systematically analyzed as an immanent cause of relapse. Here, we present a generic elementary model and analytical examination of this intrinsic limitation to therapy. We show how the relative proclivity towards cell death versus transition into a stem-like state, as a function of drug dose, establishes either a window of opportunity for containing tumors or the inevitability of progression following therapy. The model considers measurable cell behaviors independent of specific molecular pathways and provides a new theoretical framework for optimizing therapy dosing and scheduling as cancer treatment paradigms move from "maximal tolerated dose," which may promote therapy induced-stemness, to repeated "minimally effective doses" (as in adaptive therapies), which contain the tumor and avoid therapy-induced progression.

Expensive multiobjective optimization problems pose great challenges to evolutionary algorithms due to their costly evaluation. Building cheap surrogate models to replace the expensive real models has been proved to be a practical way to reduce the number of costly evaluations. Supervised learning techniques from the community of machine learning have been widely applied to build either regressors, which approximate the fitness values of candidate solutions, or classifiers, which estimate the categories of candidate solutions. Considering the characteristics of the data produced in optimization, this article proposes a new surrogate model, called a relation model, for evolutionary multiobjective optimization. Instead of estimating the qualities of candidate solutions directly, the relation model tries to estimate the relationship between a pair of solutions$\langle \mathbf {x}, \mathbf {y}\rangle $, i.e.,$\mathbf {x}$dominates$\mathbf {y}$,$\mathbf {x}$is dominated by$\mathbf {y}$, or$\mathbf {x}$is nondominated with$\mathbf {y}$in the case of multiobjective optimization. To implement this idea, first a balanced training set is prepared, then a classifier is built based on the training data set to learn the relationship, and finally, the classifier with a voting-scoring strategy is applied to estimate the relationship between the candidate solutions and parent solutions. By this way, the promising candidate solutions are recognized and evaluated by the real models. The new approach is applied to three well-known benchmark suites and two real-world applications, and the experimental results suggest that the proposed method outperforms some state-of-the-art methods based on regression and classification models on the given instances.

Abstract During program traversing, symbolic execution collects path conditions and feeds them to a constraint solver to obtain feasible solutions. However, complex path conditions, like nonlinear constraints, which widely appear in programs, are hard to be handled efficiently by the existing solvers. In this paper, we adapt the classical symbolic execution framework with a machine learning approach for constraint satisfaction. The approach samples and learns from different solutions to identify potentially feasible area. This sampling-learning style solving can be applied in different class of complex problems easily. Therefore, incorporating this approach, our framework, MLBSE, supports the symbolic execution of not only simple linear path conditions, but also nonlinear arithmetic operations, and even black-box function calls of library methods. Meanwhile, thanks to the theoretical foundation of the machine learning based approach, when the solver fails to solve a path condition, we can have an estimation of the confidence in the satisfiability (ECS) of the problem to give users insights about how the problem is analyzed and whether they could ultimately find a solution. We implement MLBSE on the basis of Symbolic Path Finder (SPF) into a fully automatic Java symbolic execution engine. Users can feed their code to MLBSE directly, which is very convenient to use. To evaluate its performance, 22 real case programs are used as the benchmarks for MLBSE to generate test cases, which involve a total number of 1042 methods that are full of nonlinear operations, floating-point arithmetic as well as native method calls. Experiment results show that the coverage achieved by MLBSE is much higher than the state-of-the-art tools.

Asynchronous parallelization is an effective way to accelerate optimization. While asynchronous parallelization can destroy the sequential structure of optimization algorithms, it has been found counter-intuitively that some optimization algorithms are proven to preserve their performance under asynchronous parallelization, including the stochastic gradient descent for first-order optimization of differentiable functions and Pareto optimization for zeroth-order optimization in binary space. Following this direction, in this paper, we show that the classification-based optimization, which is a recently developed framework for zeroth-order optimization in continuous space, can also enjoy the asynchronous parallelization. We implement ASRacos, an asynchronous version of a classification-based optimization algorithm SRacos, to accelerate the optimization through asynchronous parallelization. We theoretically provide the query complexity of ASRacos and further show that on certain conditions, ASRacos can achieve a better performance than SRacos even if using the same number of evaluations. Experiments on synthetic functions and controlling tasks in OpenAI Gym demonstrate that ASRacos can achieve almost linear speedup while preserving good solution quality.

Derivative-free optimization has shown advantage in solving sophisticated problems such as policy search, when the environment is noise-free. Many real-world environments are noisy, where solution evaluations are inaccurate due to the noise. Noisy evaluation can badly injure derivative-free optimization, as it may make a worse solution looks better. Sampling is a straightforward way to reduce noise, while previous studies have shown that delay the noise handling to the comparison time point (i.e., threshold selection) can be helpful for derivative-free optimization. This work further delays the noise handling, and proposes a simple noise handling mechanism, i.e., value suppression. By value suppression, we do nothing about noise until the best-so-far solution has not been improved for a period, and then suppress the value of the best-so-far solution and continue the optimization. On synthetic problems as well as reinforcement learning tasks, experiments verify that value suppression can be significantly more effective than the previous methods.

D numbers has been previously introduced in linguistic decision making due to its effectiveness and flexibility in dealing with uncertain information. The study applies the integration operator of D numbers to obtain the decision result by aggregating different opinions of experts which may be imprecise and uncertain. However, sometimes it would be more reasonable to consider the risk preference of the decision maker. In this paper, we proposed an improved aggregating method for linguistic information based on D numbers and OWAWA operator. The main advantage is that it can integrate the degree of importance that each experts has and the risk preference of the decision maker in the aggregation of linguistic information. An example is used to demonstrate the flexibility and reasonability of the proposed method.

Within an isogenic population, even in the same extracellular environment, individual cells can exhibit various phenotypic states. The exact role of stochastic gene-state switching regulating the transition among these phenotypic states in a single cell is not fully understood, especially in the presence of positive feedback. Recent high-precision single-cell measurements showed that, at least in bacteria, switching in gene states is slow relative to the typical rates of active transcription and translation. Hence using the lac operon as an archetype, in such a region of operon-state switching, we present a fluctuating-rate model for this classical gene regulation module, incorporating the more realistic operon-state switching mechanism that was recently elucidated. We found that the positive feedback mechanism induces bistability (referred to as deterministic bistability), and that the parameter range for its occurrence is significantly broadened by stochastic operon-state switching. We further show that in the absence of positive feedback, operon-state switching must be extremely slow to trigger bistability by itself. However, in the presence of positive feedback, which stabilizes the induced state, the relatively slow operon-state switching kinetics within the physiological region are sufficient to stabilize the uninduced state, together generating a broadened parameter region of bistability (referred to as stochastic bistability). We illustrate the opposite phenotype-transition rate dependence upon the operon-state switching rates in the two types of bistability, with the aid of a recently proposed rate formula for fluctuating-rate models. The rate formula also predicts a maximal transition rate in the intermediate region of operon-state switching, which is validated by numerical simulations in our model. Overall, our findings suggest a biological function of transcriptional "variations" among genetically identical cells, for the emergence of bistability and transition between phenotypic states.

Classification-based optimization is a recently developed framework for derivative-free optimization, which has shown to be effective for non-convex optimization problems with many local optima. This framework requires to sample a batch of solutions for every update of the search model. However, in reinforcement learning, direct policy search often offers only sequential policy evaluation. Thus, classificationbased optimization is not efficient for direct policy search where solutions have to be sampled sequentially. In this paper, we adapt the classification-based optimization for sequential sampled solutions by forming the batch of reused historical solutions. Experiments on helicopter hovering control task and reinforcement learning benchmark tasks in OpenAI Gym show that the new algorithm is superior to state-of-the-art derivative-free optimization approaches.

Multi-objective (MO) optimization problems require simultaneously optimizing two or more objective functions. An MO algorithm needs to find solutions that reach different optimal balances of the objective functions, i.e., optimal Pareto front, therefore, high dimensionality of the solution space can hurt MO optimization much severer than single-objective optimization, which was little addressed in previous studies. This paper proposes a general, theoretically-grounded yet simple approach ReMO, which can scale current derivative-free MO algorithms to the high-dimensional non-convex MO functions with low effective dimensions, using random embedding. We prove the conditions under which an MO function has a low effective dimension, and for such functions, we prove that ReMO possesses the desirable properties of optimal Pareto front preservation, time complexity reduction, and rotation perturbation invariance. Experimental results indicate that ReMO is effective for optimizing the high-dimensional MO functions with low effective dimensions, and is even effective for the high-dimensional MO functions where all dimensions are effective but most only have a small and bounded effect on the function value.

Simultaneous optimistic optimization (SOO) is a recently proposed global optimization method with a strong theoretical foundation. Previous studies have shown that SOO has a good performance in low-dimensional optimization problems, however, its performance is unsatisfactory when the dimensionality is high. This paper adapts random embedding to scaling SOO, resulting in the RESOO algorithm. We prove that the simple regret of RESOO depends only on the effective dimension of the problem, while that of SOO depends on the dimension of the solution space. Empirically, on some high-dimensional non-convex testing functions as well as hyper-parameter tuning tasks for multi-class support vector machines, RESOO shows significantly improved performance from SOO.

Many randomized heuristic derivative-free optimization methods share a framework that iteratively learns a model for promising search areas and samples solutions from the model. This paper studies a particular setting of such framework, where the model is implemented by a classification model discriminating good solutions from bad ones. This setting allows a general theoretical characterization, where critical factors to the optimization are discovered. We also prove that optimization problems with Local Lipschitz continuity can be solved in polynomial time by proper configurations of this framework. Following the critical factors, we propose the randomized coordinate shrinking classification algorithm to learn the model, forming the RACOS algorithm, for optimization in continuous and discrete domains. Experiments on the testing functions as well as on the machine learning tasks including spectral clustering and classification with Ramp loss demonstrate the effectiveness of RACOS.

As a kind of model-based optimization framework, the sampling-and-classification (SAC) algorithms, where the model is specified to be a classifier, has been recently studied in both theoretical foundation and algorithm implementation. However, the previous work only studied SAC algorithms in real domains. While significant progresses of theoretical evolutionary algorithm have been developed major in discrete domains, it is interesting to understand the SAC algorithms also in finite discrete domains. This paper studies the (e,ó)-query complexity of SAC algorithms, which measures how soon can an algorithm obtain a solution with the desired approximation quality with a probability. Some classical pseudo-Boolean problems are employed to probe the SAC algorithms, including OneMax problem, linear pseudo-Boolean functions, LeadingOnes problem, and Trap problem. The theoretical results disclose that SAC algorithms can achieve a small complexity for approximating these problems. Moreover, an implementation of the SAC framework, the RACOS algorithm, is compared with the well-analyzed (1+1)-EA on these problems.

Symbolic execution is a widely-used program analysis technique. It collects and solves path conditions to guide the program traversing. However, due to the limitation of the current constraint solvers, it is difficult to apply symbolic execution on programs with complex path conditions, like nonlinear constraints and function calls. In this paper, we propose a new symbolic execution tool MLB to handle such problem. Instead of relying on the classical constraint solving, in MLB, the feasibility problems of the path conditions are transformed into optimization problems, by minimizing some dissatisfaction degree. The optimization problems are then handled by the underlying optimization solver through machine learning guided sampling and validation. MLB is implemented on the basis of Symbolic PathFinder and encodes not only the simple linear path conditions, but also nonlinear arithmetic operations, and even black-box function calls of library methods, into symbolic path conditions. Experiment results show that MLB can achieve much better coverage on complex real-world programs.

Evolutionary algorithms (EAs), a large class of general purpose optimization algorithms inspired from the natural phenomena, are widely used in various industrial optimizations and often show excellent performance. This paper presents an attempt towards revealing their general power from a statistical view of EAs. By summarizing a large range of EAs into the sampling-and-learning framework, we show that the framework directly admits a general analysis on the probable-absolute-approximate (PAA) query complexity. We particularly focus on the framework with the learning subroutine being restricted as a binary classification, which results in the sampling-and-classification (SAC) algorithms. With the help of the learning theory, we obtain a general upper bound on the PAA query complexity of SAC algorithms. We further compare SAC algorithms with the uniform search in different situations. Under the error-target independence condition, we show that SAC algorithms can achieve polynomial speedup to the uniform search, but not super-polynomial speedup. Under the one-side-error condition, we show that super-polynomial speedup can be achieved. This work only touches the surface of the framework. Its power under other conditions is still open.

Network-enabled devices use standard Internet TCP/IP protocols and security protocols to communicate with other network nodes. They can provide services and access resources over the Internet. Small network-enabled devices may not have hardware for direct network connections. In this case, they connect to the Internet via host computers, which provide routing, remote access, and network address translation (NAT). However, organizations' security policies often prevent users from enabling these services. This paper presents a proxy agent to support network-enabled devices while respecting the security policies. The proxy agent uses the web proxy tunneling with added security features. Although proxy tunneling is well defined for web proxy servers, we must resolve several security and deployment related issues in order to adopt it securely for network-enabled devices. The paper describes the application of proxy tunneling and security methods built around this service to solve the routing related problems.

Many temporal problems arising in automated planning and scheduling can be expressed as disjunctive temporal problems (DTPs). Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems (CSPs) or satisfiability problems (SATs), and solve them using standard CSP (SAT) techniques. Basically DTPs are represented through logically related topological relations between temporal variables, however, unfortunately little work has been done on exploiting the topological information to direct the search for DTP resolving. According to the "fail-first "(FF) principle for dynamic variable ordering (DVO) heuristics in CSP literature, this paper proposes a DVO which is based on the topological structure of DTP (which is defined to be Disjunctive Temporal Network). Experimental results reveal that the proposed DVO outperforms Minimal Remaining Values heuristics-a DVO that is widely used in existing DTP solvers, especially for the hard and large-scale problems. And, a CSP based procedure with the best of the heuristics wins TSAT++ on most of the test problems.

We study an expressive quantitative temporal model: disjunctive temporal problem (DTP), which was first proposed only in 1998 (Stergiou and Koubarakis). As extension of temporal constraint satisfaction problem (TCSP) (Dechter et al. 1991), DTP differs from TCSP in that two disjuncts in a same disjunctive constraint do not necessarily refer to same temporal variables. Traditionally, most of the DTP algorithms in the literature solve DTPs by treating them as constraint satisfaction problems (CSPs), and searching for solutions using standard CSP techniques, e.g. backtracking, back-jumping, forward checking, semantic branching, removal of subsumed variables, nogood recording, etc. Those CSP techniques are powerful in solving DTPs. However, an evident drawback of viewing DTPs as general CSPs is that much semantic information encoded in DTPs is neglected. In fact we can mine rich semantic information that can be exploited to reduce search space for DTPs (more than semantic branching). Through some topological analysis on the graphical representation of the problems, some techniques are developed to help to search solutions for other temporal models (e.g. TCSP), or to identify "crucial subproblems" for CSP (Epstein and Wallace, 2006). However, little effort has been made to exploit the inherent topological information in solving DTPs. Our idea runs on a graphical representation of DTPs - disjunctive temporal network (DTN). We define DTN as an edge-labeled weighted digraph, on which some relevant concepts are identified. Then, we define the concept of equivalency between DTNs with respect to their consistency. For a given DTN, deciding its consistency is ascribed to check the consistency of a DTN which is equivalent to it and has less constraints (edges). We iteratively reduce a DTN to a simpler but equivalent one according to a set of designed reduction rules (which can be performed within polynomial time). It is hoped that when the DTN reaches a fixed point under such reduction operation, the resulted DTN has minimal edges (which is like backdoor in SAT, or "near clique"). At last the resulted DTN (DTP) is transferred to CSP search phase, where we derive a special variable ordering strategy again through the DTN structure. We shall describe the generation of DTN structure, the DTN reduction rules, the implementation of the complete graph-DTP algorithm, and some first results of this approach.

BACKGROUND: Genomic deletions and duplications are important in the pathogenesis of diseases, such as cancer and mental retardation, and have recently been shown to occur frequently in unaffected individuals as polymorphisms. Affymetrix GeneChip whole genome sampling analysis (WGSA) combined with 100 K single nucleotide polymorphism (SNP) genotyping arrays is one of several microarray-based approaches that are now being used to detect such structural genomic changes. The popularity of this technology and its associated open source data format have resulted in the development of an increasing number of software packages for the analysis of copy number changes using these SNP arrays. RESULTS: We evaluated four publicly available software packages for high throughput copy number analysis using synthetic and empirical 100 K SNP array data sets, the latter obtained from 107 mental retardation (MR) patients and their unaffected parents and siblings. We evaluated the software with regards to overall suitability for high-throughput 100 K SNP array data analysis, as well as effectiveness of normalization, scaling with various reference sets and feature extraction, as well as true and false positive rates of genomic copy number variant (CNV) detection. CONCLUSION: We observed considerable variation among the numbers and types of candidate CNVs detected by different analysis approaches, and found that multiple programs were needed to find all real aberrations in our test set. The frequency of false positive deletions was substantial, but could be greatly reduced by using the SNP genotype information to confirm loss of heterozygosity.