Precise detection of eggs on conveyor belts in industrial automated production lines is of significant importance for reducing detection error rates and improving production efficiency. However, existing detection models face considerable challenges in detection accuracy and real-time processing when handling practical scenarios such as densely arranged eggs, complex background interference, and high-speed conveyor belts. This paper proposes a lightweight real-time detection Transformer model called RCD-DETR, consisting of three key innovative components: (1) a lightweight Reparam Context-aware Network (RCNet) that effectively balances feature extraction capability and computational efficiency; (2) a Context-Sensitive Refinement Feature Pyramid Network (CSRFPN) with enhanced contextual awareness and multi-scale feature representation capabilities, strengthening the model’s ability to recognize small and dense objects; and (3) a Dilated Reparam Bottleneck C3 (DRepC3) module that expands the receptive field range while further reducing computational resource requirements. Experimental evaluation indicates that, compared to the RT-DETR baseline model, the proposed method achieves improved detection accuracy while reducing computational complexity by 54.1%, decreasing parameter count by 51.3%, and compressing model size by 50.8%. The method achieves an excellent balance between accuracy, inference speed, and resource consumption, making it suitable for deployment on resource-constrained edge computing devices for precise real-time egg detection on conveyor belts.

Clustering ensemble often provides robust and stable results without accessing original features of data, and thus has been widely studied. The conventional clustering ensemble methods often take the full multiple base partitions as inputs and provide a consensus clustering result. However, in many real-world applications, full base partitions are hard to obtain because some data may be missing in some base partitions. To tackle this problem, in this paper, we propose a novel partial clustering ensemble method, which takes the partial multiple base partitions as inputs. In this method, we simultaneously fill the missing values in the base partitions and ensemble them by fully considering the consensus and diversity. Moreover, to address the unreliability issue in the partial data scenario, we seamlessly plug it into a self-paced learning framework. The extensive experiments on benchmark data sets demonstrate the effectiveness and efficiency of the proposed method when handling incomplete data.

Image-text retrieval is a central problem for understanding the semantic relationship between vision and language, and serves as the basis for various visual and language tasks. Most previous works either simply learn coarse-grained representations of the overall image and text, or elaborately establish the correspondence between image regions or pixels and text words. However, the close relations between coarse- and fine-grained representations for each modality are important for image-text retrieval but almost neglected. As a result, such previous works inevitably suffer from low retrieval accuracy or heavy computational cost. In this work, we address image-text retrieval from a novel perspective by combining coarse- and fine-grained representation learning into a unified framework. This framework is consistent with human cognition, as humans simultaneously pay attention to the entire sample and regional elements to understand the semantic content. To this end, a Token-Guided Dual Transformer (TGDT) architecture which consists of two homogeneous branches for image and text modalities, respectively, is proposed for image-text retrieval. The TGDT incorporates both coarse- and fine-grained retrievals into a unified framework and beneficially leverages the advantages of both retrieval approaches. A novel training objective called Consistent Multimodal Contrastive (CMC) loss is proposed accordingly to ensure the intra- and inter-modal semantic consistencies between images and texts in the common embedding space. Equipped with a two-stage inference method based on the mixed global and local cross-modal similarity, the proposed method achieves state-of-the-art retrieval performances with extremely low inference time when compared with representative recent approaches. Code is publicly available: github.com/LCFractal/TGDT.

Multi-Target Multi-Camera Tracking has a wide range of applications and is the basis for many high-level inference and prediction tasks. How to make the system perform efficiently on a large number of cameras is a crucial research issue. Previous works have proposed many matching strategies to reduce the matching range and improve the matching accuracy. However, these works require human participation when formulating matching strategies, which becomes infeasible as the scale of the camera system increases. To tackle this problem, we propose an adaptive matching strategy to replace manual rules when guiding the matching between cameras. Specifically, we use the Markov decision process to model the tracklets matching problem between cameras. Reinforcement learning and imitation learning are combined to predict a set of cameras where the tracking target might be located. The predicted candidate camera set can be used for intercamera matching and association between tracklets. Moreover, our method can be trained with or without ground truth inter-camera trajectories, making it more practical in real scenarios. We evaluate our method on the city-scale tracking dataset Cityflow, and the proposed method is sufficient to replace manual rules, and finally improve the performance of the overall MTMCT system.

Should the properties of constraint monotonicity and foundedness be mandatory requirements that every answer set and world view semantics must satisfy? This question is challenging and has incurred a debate in answer set programming (ASP). In this paper we address the question by introducing natural logic programs whose expected answer sets and world views violate these properties and thus may be viewed as counter-examples to these requirements. Specifically we use instances of the generalized strategic companies problem for ASP benchmark competitions as concrete examples to demonstrate that the requirements of constraint monotonicity and foundedness may exclude expected answer sets for some simple disjunctive programs and world views for some epistemic specifications. In conclusion these properties should not be mandatory conditions for an answer set and world view semantics in general.

Clustering ensemble generates a consensus clustering result by integrating multiple weak base clustering results. Although it often provides more robust results compared with single clustering methods, it still suffers from the robustness problem if it does not treat the unreliability of base results carefully. Conventional clustering ensemble methods often use all data for ensemble, while ignoring the noises or outliers on the data. Although some robust clustering ensemble methods are proposed, which extract the noises on the data, they still characterize the robustness in a single level, and thus they cannot comprehensively handle the complicated robustness problem. In this paper, to address this problem, we propose a novel Tri-level Robust Clustering Ensemble (TRCE) method by transforming the clustering ensemble problem to a multiple graph learning problem. Just as its name implies, the proposed method tackles robustness problem in three levels: base clustering level, graph level and instance level. By considering the robustness problem in a more comprehensive way, the proposed TRCE can achieve a more robust consensus clustering result. Experimental results on benchmark datasets also demonstrate it. Our method often outperforms other state-of-the-art clustering ensemble methods. Even compared with the robust ensemble methods, ours also performs better.

Vision-language Navigation (VLN) tasks require an agent to navigate step-by-step while perceiving the visual observations and comprehending a natural language instruction. Large data bias, which is caused by the disparity ratio between the small data scale and large navigation space, makes the VLN task challenging. Previous works have proposed various data augmentation methods to reduce data bias. However, these works do not explicitly reduce the data bias across different house scenes. Therefore, the agent would overfit to the seen scenes and achieve poor navigation performance in the unseen scenes. To tackle this problem, we propose the Random Environmental Mixup (REM) method, which generates cross-connected house scenes as augmented data via mixuping environment. Specifically, we first select key viewpoints according to the room connection graph for each scene. Then, we cross-connect the key views of different scenes to construct augmented scenes. Finally, we generate augmented instruction-path pairs in the cross-connected scenes. The experimental results on benchmark datasets demonstrate that our augmentation data via REM help the agent reduce its performance gap between the seen and unseen environment and improve the overall performance, making our model the best existing approach on the standard VLN benchmark.

The clustering ensemble has emerged as an important extension of the classical clustering problem. It provides an elegant framework to integrate multiple weak base clusterings to generate a strong consensus result. Most existing clustering ensemble methods usually exploit all data to learn a consensus clustering result, which does not sufficiently consider the adverse effects caused by some difficult instances. To handle this problem, we propose a novel self-paced clustering ensemble (SPCE) method, which gradually involves instances from easy to difficult ones into the ensemble learning. In our method, we integrate the evaluation of the difficulty of instances and ensemble learning into a unified framework, which can automatically estimate the difficulty of instances and ensemble the base clusterings. To optimize the corresponding objective function, we propose a joint learning algorithm to obtain the final consensus clustering result. Experimental results on benchmark data sets demonstrate the effectiveness of our method.

Style variation has been a major challenge for person re-identification, which aims to match the same pedestrians across different cameras. Existing works attempted to address this problem with camera-invariant descriptor subspace learning. However, there will be more image artifacts when the difference between the images taken by different cameras is larger. To solve this problem, we propose a UnityStyle adaption method, which can smooth the style disparities within the same camera and across different cameras. Specifically, we firstly create UnityGAN to learn the style changes between cameras, producing shape-stable style-unity images for each camera, which is called UnityStyle images. Meanwhile, we use UnityStyle images to eliminate style differences between different images, which makes a better match between query and gallery. Then, we apply the proposed method to Re-ID models, expecting to obtain more style-robust depth features for querying. We conduct extensive experiments on widely used benchmark datasets to evaluate the performance of the proposed framework, the results of which confirm the superiority of the proposed model.

Multi-modal clustering aims to cluster data into different groups by exploring complementary information from multiple modalities or views. Little work learns the deep fused representations and simutaneously discovers the cluster structure with a discriminative loss. In this paper, we present an End-to-end Adversarial-attention network for Multi-modal Clustering (EAMC), where adversarial learning and attention mechanism are leveraged to align the latent feature distributions and quantify the importance of modalities respectively. To benefit from the joint training, we introducea divergence-based clustering objective that not only encourages the separation and compactness of the clusters but also enjoy a clear cluster structure by embedding the simplex geometry of the output space into the loss. The proposed network consists of modality-specific feature learning, modality fusion and cluster assignment three modules. It can be trained from scratch with batch-mode based optimization and avoid an autoencoder pretraining stage. Comprehensive experiments conducted on five real-world datasets show the superiority and effectiveness of the proposed clustering method.

[Gelfond and Lifschitz, 1991] introduced simple disjunctive logic programs and defined the answer set semantics called GL-semantics. We observed that the requirement of GL-semantics, i.e., an answer set should be a minimal model of the GL-reduct may be too strong and exclude some answer sets that would be reasonably acceptable. To address this, we present a novel and more permissive semantics, called determining inference semantics.

The goal of person reidentification (Re-ID) is to identify a given pedestrian from a network of nonoverlapping surveillance cameras. Most existing works follow the supervised learning paradigm which requires pairwise labeled training data for each pair of cameras. However, this limits their scalability to real-world applications where abundant unlabeled data are available. To address this issue, we propose a multi-feature fusion with adaptive graph learning model for unsupervised Re-ID. Our model aims to negotiate comprehensive assessment on the consistent graph structure of pedestrians with the help of special information of feature descriptors. Specifically, we incorporate multi-feature dictionary learning and adaptive multi-feature graph learning into a unified learning model such that the learned dictionaries are discriminative and the subsequent graph structure learning is accurate. An alternating optimization algorithm with proved convergence is developed to solve the final optimization objective. Extensive experiments on four benchmark data sets demonstrate the superiority and effectiveness of the proposed method.

Matching images and sentences demands a fine understanding of both modalities. In this article, we propose a new system to discriminatively embed the image and text to a shared visual-textual space. In this field, most existing works apply the ranking loss to pull the positive image/text pairs close and push the negative pairs apart from each other. However, directly deploying the ranking loss on heterogeneous features (i.e., text and image features) is less effective, because it is hard to find appropriate triplets at the beginning. So the naive way of using the ranking loss may compromise the network from learning inter-modal relationship. To address this problem, we propose the instance loss, which explicitly considers the intra-modal data distribution. It is based on an unsupervised assumption that each image/text group can be viewed as a class. So the network can learn the fine granularity from every image/text group. The experiment shows that the instance loss offers better weight initialization for the ranking loss, so that more discriminative embeddings can be learned. Besides, existing works usually apply the off-the-shelf features, i.e., word2vec and fixed visual feature. So in a minor contribution, this article constructs an end-to-end dual-path convolutional network to learn the image and text representations. End-to-end learning allows the system to directly learn from the data and fully utilize the supervision. On two generic retrieval datasets (Flickr30k and MSCOCO), experiments demonstrate that our method yields competitive accuracy compared to state-of-the-art methods. Moreover, in language-based person retrieval, we improve the state of the art by a large margin. The code has been made publicly available.

The success of batch mode active learning (BMAL) methods lies in selecting both representative and uncertain samples. Representative samples quickly capture the global structure of the whole dataset, while the uncertain ones refine the decision boundary. There are two principles, namely the direct approach and the screening approach, to make a trade-off between representativeness and uncertainty. Although widely used in literature, little is known about the relationship between these two principles. In this paper, we discover that the two approaches both have shortcomings in the initial stage of BMAL. To alleviate the shortcomings, we bound the certainty scores of unlabeled samples from below and directly combine this lower-bounded certainty with representativeness in the objective function. Additionally, we show that the two aforementioned approaches are mathematically equivalent to two special cases of our approach. To the best of our knowledge, this is the first work that tries to generalize the direct and screening approaches. The objective function is then solved by super-modularity optimization. Extensive experiments on fifteen datasets indicate that our method has significantly higher classification accuracy on testing data than the latest state-of-the-art BMAL methods, and also scales better even when the size of the unlabeled pool reaches 106.

Multi-view classification has received considerable attention in recent years. We observed that the existing multi-view classification methods learn a consensus result by collecting all views and thus have two critical limitations. First, it is not scalable. Second, in many applications views of data are available over time; it is in-feasible to apply the existing multi-view learning methods to such streaming views. To address the two limitations, in this paper we propose a novel incremental multi-view SVM method, i.e., instead of processing all views simultaneously, we integrate them one by one in an incremental way. We first learn an initial model from the first view; next when a new view is available, we update the model and then apply it to learn a new consensus result. This incremental method is scalable and applicable to streaming views. We present a block coordinate descent algorithm whose convergence is theoretically guaranteed to optimize the induced objective function. Experimental results on several benchmark data sets further demonstrate the effectiveness of our method.

In a seminal paper, Gelfond and Lifschitz [34] introduced simple disjunctive logic programs, where in rule heads the disjunction operator “|” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct ) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics . Specifically, we introduce a head selection function to formalize the operator | and define answer sets as follows: (i) Given an interpretation I and a selection function sel , we transform a disjunctive program Π into a normal program Π s e l I , called a disjunctive program reduct ; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w.r.t. X if I is an answer set of Π s e l I under X ; and (iii) we define I to be an answer set of Π w.r.t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GL n l p -semantics defined by Gelfond and Lifschitz [33] , we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. [65] , we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda [36] about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics [24] , where deciding whether Π has some answer set is Σ 2 p -complete, while brave and cautious reasoning are Σ 2 p - and Π 2 p -complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.

Recognizing human actions in video clips has been an important topic in computer vision. Sufficient labeled data is one of the prerequisites for the good performance of action recognition algorithms. However, while abundant videos can be collected from the Internet, categorizing each video clip is tedious and even time-consuming. Active learning is one way to alleviate the labeling labor by allowing the classifier to choose the most informative unlabeled instances for manual annotation. Among various active learning algorithms, uncertainty sampling is arguably the most widely-used strategy. Conventional uncertainty sampling strategies such as entropy-based methods are usually tested under accuracy. However, in action recognition Average Precision (AP) is an acknowledged evaluation metric, which is somehow ignored in the active learning community. It is defined as the area under the precision-recall curve. In this paper, we propose a novel uncertainty sampling algorithm for action recognition using expected AP. We conduct experiments on three real-world action recognition datasets and show that our algorithm outperforms other uncertainty-based active learning algorithms.

Epistemic negation 'not' along with default negation 'neg' plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing approaches behave not satisfactorily in that they suffer from the problems of unintended world views due to recursion through the epistemic modal operator K or M ( K F and M F are shorthands for (neg not F) and (not neg F), respectively). In this paper we present a general approach to epistemic negation which is free of unintended world views and thus offers a solution to the long-standing problem of epistemic specifications which were introduced by Gelfond 1991 over two decades ago.

Cold-start recommendation is one of the most challenging problems in recommender systems. An important approach to cold-start recommendation is to conduct an interview for new users, called the interview-based approach . Among the interview-based methods, Representative-Based Matrix Factorization (RBMF) [24] provides an effective solution with appealing merits: it represents users over selected representative items, which makes the recommendations highly intuitive and interpretable. However, RBMF only utilizes a global set of representative items to model all users. Such a representation is somehow too strict and may not be flexible enough to capture varying users’ interests. To address this problem, we propose a novel interview-based model to dynamically create meaningful user groups using decision trees and then select local representative items for different groups. A two-round interview is performed for a new user. In the first round, l 1 global questions are issued for group division, while in the second round, l 2 local-group-specific questions are given to derive local representation. We collect the feedback on the (l 1 +l 2 ) items to learn the user representations. By putting these steps together, we develop a joint optimization model, named local representative-based matrix factorization , for new user recommendations. Extensive experiments on three public datasets have demonstrated the effectiveness of the proposed model compared with several competitive baselines.

Epistemic negation not along with default negation ¬ plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing epistemic approaches such as those by Gelfond [13], [15], [14], Truszczynski [33] and Kahl et al. [18] behave not satisfactorily in that they suffer from the problems of unintended world views due to recursion through the epistemic modal operator K or M (KF and MF are shorthands for ¬notF and not¬F, respectively). In this paper we present a new approach to handling epistemic negation which is free of unintended world views and thus offers a solution to the long-standing problem of epistemic specifications which were introduced by Gelfond [13] over two decades ago. We consider general logic programs consisting of rules of the form H←B, where H and B are arbitrary first-order formulas possibly containing epistemic negation, and define a general epistemic answer set semantics for general logic programs by introducing a novel program transformation and a new definition of world views in which we apply epistemic negation to minimize the knowledge in world views. The general epistemic semantics is applicable to extend any existing answer set semantics, such as those defined in [26], [27], [32], [1], [8], [12], [29], with epistemic negation. For illustration, we extend FLP answer set semantics of Faber et al. [8] for general logic programs with epistemic negation, leading to epistemic FLP semantics. We also extend the more restrictive well-justified FLP semantics of Shen et al. [29], which is free of circularity for default negation, to an epistemic well-justified semantics. We consider the computational complexity of epistemic FLP semantics and show that for a propositional program Π with epistemic negation, deciding whether Π has epistemic FLP answer sets is Σ3p-complete and deciding whether a propositional formula F is true in Π under epistemic FLP semantics is Σ4p-complete in general, but has lower complexity for logic programs that match normal epistemic specifications, where the complexity of world view existence and query evaluation drops by one level in the polynomial hierarchy.

The critical behaviors of NP-complete problems have been studied extensively, and numerous results have been obtained for Boolean formula satisfiability (SAT) and constraint satisfaction (CSP), among others. However, few results are known for the critical behaviors of NP-hard nonmonotonic reasoning problems so far; in particular, a mathematical model for phase transition in nonmonotonic reasoning is still missing. In this article, we investigate the phase transition of negative two-literal logic programs under the answer-set semantics. We choose this class of logic programs since it is the simplest class for which the consistency problem of deciding if a program has an answer set is still NP-complete. We first introduce a new model, called quadratic model for generating random logic programs in this class. We then mathematically prove that the consistency problem for this class of logic programs exhibits a phase transition. Furthermore, the phase-transition follows an easy-hard-easy pattern. Given the correspondence between answer sets for negative two-literal programs and kernels for graphs, as a corollary, our result significantly generalizes de la Vega's well-known theorem for phase transition on the existence of kernels in random graphs. We also report some experimental results. Given our mathematical results, these experimental results are not really necessary. We include them here as they suggest that our phase-transition result is more general and likely holds for more general classes of logic programs.

ABox abduction plays an important role in reasoning over description logic (DL) ontologies. However, it does not work with inconsistent DL ontologies. To tackle this problem while achieving tractability, we generalize ABox abduction from the classical semantics to an inconsistency-tolerant semantics, namely the Intersection ABox Repair (IAR) semantics, and propose the notion of IAR-explanations in inconsistent DL ontologies. We show that computing all minimal IAR-explanations is tractable in data complexity for first-order rewritable ontologies. However, the computational method may still not be practical due to a possibly large number of minimal IAR-explanations. Hence we propose to use preference information to reduce the number of explanations to be computed.

Active learning is a machine learning technique that trains a classifier after selecting a subset from an unlabeled dataset for labeling and using the selected data for training. Recently, batch mode active learning, which selects a batch of samples to label in parallel, has attracted a lot of attention. Its challenge lies in the choice of criteria used for guiding the search of the optimal batch. In this paper, we propose a novel approach to selecting the optimal batch of queries by minimizing the α-relative Pearson divergence (RPE) between the labeled and the original datasets. This particular divergence is chosen since it can distinguish the optimal batch more easily than other measures especially when available candidates are similar. The proposed objective is a min-max optimization problem, and it is difficult to solve due to the involvement of both minimization and maximization. We find that the objective has an equivalent convex form, and thus a global optimal solution can be obtained. Then the subgradient method can be applied to solve the simplified convex problem. Our empirical studies on UCI datasets demonstrate the effectiveness of the proposed approach compared with the state-of-the-art batch mode active learning methods.

In classification tasks, labeled data is a necessity but sometimes difficult or expensive to obtain. On the contrary, unlabeled data is usually abundant. Recently, different active learning algorithms are proposed to alleviate this issue by selecting the most informative data points to label. One family of active learning methods comes from Optimum Experimental Design (OED) in statistics. Instead of selecting data points one by one iteratively, OED-based approaches select data in a one-shot manner, that is, a fixed-sized subset is selected from the unlabeled dataset for manually labeling. These methods usually use kernels to represent pair-wise similarities between different data points. It is well known that choosing optimal kernel types (e.g. Gaussian kernel) and kernel parameters (e.g. kernel width) is tricky, and a common way to resolve it is by Multiple Kernel Learning (MKL), i.e., to construct a few candidate kernels and merge them to form a consensus kernel. There would be different ways to combine multiple kernels, one of which, called the the globalised approach is to assign a weight to each candidate kernel. In practice different data points in the same candidate kernel may not have the same contribution in the consensus kernel, this requires assigning different weights to different data points in the same candidate kernel, leading to the localized approach. In this paper, we introduce MKL to OED-based active learning, specifically we propose globalised and localized multiple kernel active learning methods, respectively. Our experiments on six benchmark datasets demonstrate that the proposed methods have better performance than existing OED-based active learning methods.

The problem of feature selection has raised considerable interests in the past decade. Traditional unsupervised methods select the features which can faithfully preserve the intrinsic structures of data, where the intrinsic structures are estimated using all the input features of data. However, the estimated intrinsic structures are unreliable/inaccurate when the redundant and noisy features are not removed. Therefore, we face a dilemma here: one need the true structures of data to identify the informative features, and one need the informative features to accurately estimate the true structures of data. To address this, we propose a unified learning framework which performs structure learning and feature selection simultaneously. The structures are adaptively learned from the results of feature selection, and the informative features are reselected to preserve the refined structures of data. By leveraging the interactions between these two essential tasks, we are able to capture accurate structures and select more informative features. Experimental results on many benchmark data sets demonstrate that the proposed method outperforms many state of the art unsupervised feature selection methods.

With unstructured heterogeneous multimedia data such as texts, images being more and more widely used on the web, cross-media retrieval has become an increasingly important task. One of the key techniques in cross-media retrieval is how to compute distances or similarities among different types of media data. In this paper, we propose a novel heterogeneous metric learning method to compute distances between images and texts. We extend Locally Linear Embedding (LLE) to deal with heterogeneous data, so that we can not only preserve homogeneous local information but also capture heterogeneous constraints. In order to handle the out-of-sample problem, we learn two map functions from the embedding, and use them to transform heterogeneous data into a homogeneous space and do the retrieval in the new space. The experimental results on two real-world datasets show the effectiveness of our approach.

ABox abduction is an important reasoning mechanism for description logic ontologies. It computes all minimal explanations (sets of ABox assertions) whose appending to a consistent ontology enforces the entailment of an observation while keeps the ontology consistent. We focus on practical computation for a general problem of ABox abduction, called the query abduction problem, where an observation is a Boolean conjunctive query and the explanations may contain fresh individuals neither in the ontology nor in the observation. However, in this problem there can be infinitely many minimal explanations. Hence we first identify a class of TBoxes called first-order rewritable TBoxes. It guarantees the existence of finitely many minimal explanations and is sufficient for many ontology applications. To reduce the number of explanations that need to be computed, we introduce a special kind of minimal explanations called representative explanations from which all minimal explanations can be retrieved. We develop a tractable method (in data complexity) for computing all representative explanations in a consistent ontology. xperimental results demonstrate that the method is efficient and scalable for ontologies with large ABoxes.

We propose an unsupervised approach to constructing templates from a large collection of semantic category names, and use the templates as the semantic representation of categories.The main challenge is that many terms have multiple meanings, resulting in a lot of wrong templates.Statistical data and semantic knowledge are extracted from a web corpus to improve template generation.A nonlinear scoring function is proposed and demonstrated to be effective.Experiments show that our approach achieves significantly better results than baseline methods.As an immediate application, we apply the extracted templates to the cleaning of a category collection and see promising results (precision improved from 81% to 89%).

In this paper, we consider the problem of unsupervised feature selection. Recently, spectral feature selection algorithms, which leverage both graph Laplacian and spectral regression, have received increasing attention. However, existing spectral feature selection algorithms suffer from two major problems: 1) since the graph Laplacian is constructed from the original feature space, noisy and irrelevant features may have adverse effect on the estimated graph Laplacian and hence degenerate the quality of the induced graph embedding, 2) since the cluster labels are discrete in natural, relaxing and approximating these labels into a continuous embedding can inevitably introduce noise into the estimated cluster labels. Without considering the noise in the cluster labels, the feature selection process may be misguided. In this paper, we propose a Robust Spectral learning framework for unsupervised Feature Selection (RSFS), which jointly improves the robustness of graph embedding and sparse spectral regression. Compared with existing methods which are sensitive to noisy features, our proposed method utilizes a robust local learning method to construct the graph Laplacian and a robust spectral regression method to handle the noise on the learned cluster labels. In order to solve the proposed optimization problem, an efficient iterative algorithm is proposed. We also show the close connection between the proposed robust spectral regression and robust Huber M-estimator. Experimental results on different datasets show the superiority of RSFS.

The answer set semantics presented by Faber et al. [27] has been widely used to define so called FLP answer sets for different types of logic programs. However, it was recently observed that when being extended from normal to more general classes of logic programs, this approach may produce answer sets with circular justifications that are caused by self-supporting loops. The main reason for this behavior is that the FLP answer set semantics is not fully constructive by a bottom up construction of answer sets. In this paper, we overcome this problem by enhancing the FLP answer set semantics with a level mapping formalism such that every answer set I can be built by fixpoint iteration of a one-step provability operator (more precisely, an extended van Emden–Kowalski operator for the FLP reduct fΠI). This is inspired by the fact that under the standard answer set semantics, each answer set I of a normal logic program Π is obtainable by fixpoint iteration of the standard van Emden–Kowalski one-step provability operator for the Gelfond–Lifschitz reduct ΠI, which induces a level mapping. The enhanced FLP answer sets, which we call well-justified FLP answer sets, are thanks to the level mapping free of circular justifications. As a general framework, the well-justified FLP answer set semantics applies to logic programs with first-order formulas, logic programs with aggregates, description logic programs, hex-programs etc., provided that the rule satisfaction is properly extended to such general logic programs. We study in depth the computational complexity of FLP and well-justified FLP answer sets for general classes of logic programs. Our results show that the level mapping does not increase the worst-case complexity of FLP answer sets. Furthermore, we describe an implementation of the well-justified FLP answer set semantics, and report about an experimental evaluation, which indicates a potential for performance improvements by the level mapping in practice.

In this paper, we consider the problem of feature selection in unsupervised learning scenario. Recently, spectral feature selection methods, which leverage both the graph Laplacian and the learning mechanism, have received considerable attention. However, when there are lots of irrelevant or noisy features, such graphs may not be reliable and then mislead the selection of features. In this paper, we propose the Local and Global Discriminative learning for unsupervised Feature Selection (LGDFS), which integrates a global and a set of locally linear regression model with weighted l2-norm regularization into a unified learning framework. By exploring the discriminative and geometrical information in the weighted feature space, which alleviates the effects of the irrelevant features, our approach can find the most representative features to well respect the cluster structure of the data. Experimental results on several benchmark data sets are provided to validate the effectiveness of the proposed approach.

Due to the fast evolution of the information on the Internet, update summarization has received much attention in recent years. It is to summarize an evolutionary document collection at current time supposing the users have read some related previous documents. In this paper, we propose a graph-ranking-based method. It performs constrained reinforcements on a sentence graph, which unifies previous and current documents, to determine the salience of the sentences. The constraints ensure that the most salient sentences in current documents are updates to previous documents. Since this method is NP-hard, we then propose its approximate method, which is polynomial time solvable. Experiments on the TAC 2008 and 2009 benchmark data sets show the effectiveness and efficiency of our method.

The FLP semantics presented by (Faber, Leone, and Pfeifer 2004) has been widely used to define answer sets, called FLP answer sets, for different types of logic programs such as logic programs with aggregates, description logic programs (dl-programs), Hex programs, and logic programs with first-order formulas (general logic programs). However, it was recently observed that the FLP semantics may produce unintuitive answer sets with circular justifications caused by self-supporting loops. In this paper, we address the circular justification problem for general logic programs by enhancing the FLP semantics with a level mapping formalism. In particular, we extend the Gelfond-Lifschitz three step definition of the standard answer set semantics from normal logic programs to general logic programs and define for general logic programs the first FLP semantics that is free of circular justifications. We call this FLP semantics the well-justified FLP semantics. This method naturally extends to general logic programs with additional constraints like aggregates, thus providing a unifying framework for defining the well-justified FLP semantics for various types of logic programs. When this method is applied to normal logic programs with aggregates, the well-justified FLP semantics agrees with the conditional satisfaction based semantics defined by (Son, Pontelli, and Tu 2007); and when applied to dl-programs, the semantics agrees with the strongly well-supported semantics defined by (Shen 2011).

Nonnegative matrix factorization (NMF) is a popular technique for learning parts-based representation and data clustering. It usually uses the squared residuals to quantify the quality of factorization, which is optimal specifically to zero-mean, Gaussian noise and sensitive to outliers in general cases. In this paper, we propose a robust NMF method based on the correntropy induced metric, which is much more insensitive to outliers. A half-quadratic optimization algorithm is developed to solve the proposed problem efficiently. The proposed method is further extended to handle outlier rows by incorporating structural knowledge about the outliers. Experimental results on data sets with and without apparent outliers demonstrate the effectiveness of the proposed algorithms.

In order to directly reason over inconsistent OWL 2 DL ontologies, this paper considers linear order inference which comes from propositional logic. Consequences of this inference in an inconsistent ontology are defined as consequences in a certain consistent sub-ontology. This paper proposes a novel framework for compiling an OWL 2 DL ontology to a Horn propositional program so that the intended consistent sub-ontology for linear order inference can be approximated from the compiled result in polynomial time. A tractable method is proposed to realize this framework. It guarantees that the compiled result has a polynomial size. Experimental results show that the proposed method computes the exact intended sub-ontology for almost all test cases, while it is significantly more efficient and scalable than state-of-the-art exact methods.

This paper is concerned with the prediction of clicking an ad in sponsored search. The accurate prediction of user's click on an ad plays an important role in sponsored search, because it is widely used in both ranking and pricing of the ads. Previous work on click prediction usually takes a single ad as input, and ignores its relationship to the other ads shown in the same page. This independence assumption here, however, might not be valid in the real scenario. In this paper, we first perform an analysis on this issue by looking at the click-through rates (CTR) of the same ad, in the same position and for the same query, but surrounded by different ads. We found that in most cases the CTR varies largely, which suggests that the relationship between ads is really an important factor in predicting click probability. Furthermore, our investigation shows that the more similar the surrounding ads are to an ad, the lower the CTR of the ad is. Based on this observation, we design a continuous conditional random fields (CRF) based model for click prediction, which considers both the features of an ad and its similarity to the surrounding ads. We show that the model can be effectively learned using maximum likelihood estimation, and can also be efficiently inferred due to its closed form solution. Our experimental results on the click-through log from a commercial search engine show that the proposed model can predict clicks more accurately than previous independent models. To our best knowledge this is the first work that predicts ad clicks by considering the relationship between ads.

ABox abduction is an important reasoning facility in Description Logics (DLs). It finds all minimal sets of ABox axioms, called abductive solutions, which should be added to a background ontology to enforce entailment of an observation which is a specified set of ABox axioms. However, ABox abduction is far from practical by now because there lack feasible methods working in finite time for expressive DLs. To pave a way to practical ABox abduction, this paper proposes a new problem for ABox abduction and a new method for computing abductive solutions accordingly. The proposed problem guarantees finite number of abductive solutions. The proposed method works in finite time for a very expressive DL, , which underpins the W3C standard language OWL 2, and guarantees soundness and conditional completeness of computed results. Experimental results on benchmark ontologies show that the method is feasible and can scale to large ABoxes.

ABox abduction is an important aspect for abductive reasoning in Description Logics (DLs). It finds all minimal sets of ABox axioms that should be added to a background ontology to enforce entailment of a specified set of ABox axioms. As far as we know, by now there is only one ABox abduction method in expressive DLs computing abductive solutions with certain minimality. However, the method targets an ABox abduction problem that may have infinitely many abductive solutions and may not output an abductive solution in finite time. Hence, in this paper we propose a new ABox abduction problem which has only finitely many abductive solutions and also propose a novel method to solve it. The method reduces the original problem to an abduction problem in logic programming and solves it with Prolog engines. Experimental results show that the method is able to compute abductive solutions in benchmark OWL DL ontologies with large ABoxes.

Computing all diagnoses of an inconsistent ontology is important in ontology-based applications. However, the number of diagnoses can be very large. It is impractical to enumerate all diagnoses before identifying the target one to render the ontology consistent. Hence, we propose to represent all diagnoses by multiple sets of partial diagnoses, where the total number of partial diagnoses can be small and the target diagnosis can be directly retrieved from these partial diagnoses. We also propose methods for computing the new representation of all diagnoses in an OWL DL ontology. Experimental results show that computing the new representation of all diagnoses is much easier than directly computing all diagnoses.

[Fages, 1994] introduces the notion of well-supportedness as a key requirement for the seman-tics of normal logic programs and characterizes the standard answer set semantics in terms of the well-supportedness condition. With the property of well-supportedness, answer sets are guaranteed to be free of circular justifications. In this pa-per, we extend Fages ’ work to description logic programs (or DL-programs). We introduce two forms of well-supportedness for DL-programs. The first one defines weakly well-supported models that are free of circular justifications caused by posi-tive literals in rule bodies. The second one de-fines strongly well-supported models that are free of circular justifications caused by either positive or negative literals. We then define two new an-swer set semantics for DL-programs and charac-terize them in terms of the weakly and strongly well-supported models, respectively. The first se-mantics is based on an extended Gelfond-Lifschitz transformation and defines weakly well-supported answer sets that are free of circular justifications for the class of DL-programs without negative dl-atoms. The second semantics defines strongly well-supported answer sets which are free of circular justifications for all DL-programs. We show that the existing answer set semantics for DL-programs, such as the weak answer set semantics, the strong answer set semantics, and the FLP-based answer set semantics, satisfy neither the weak nor the strong well-supportedness condition, even for DL-programs without negative dl-atoms. This explains why their answer sets incur circular justifications. 1

Update summarization is to summarize a document collection B given that the users have already read another document collection A, which has time stamp prior to that of B. An important and challenging issue in update summarization is that contents in B already covered by A should be excluded from the update summary. In this paper, we propose a graph-based regularization framework MarginRank for update summarization. MarginRank extends the cost function of Zhou's Manifold Ranking with suppression terms, suppression of A on B, to fulfil the assumption that users have read A. MarginRank ranks sentences in B in a way that the top ranked sentences are most important and at the same time cover different contents from A. Experiments on the benchmark data sets TAC 2008 and 2009 show the effectiveness of the proposed method.

Novelty, coverage and balance are important requirements in topic-focused summarization, which to a large extent determine the quality of a summary. In this paper, we propose a novel method that incorporates these requirements into a sentence ranking probability model. It differs from the existing methods in that the novelty, coverage and balance requirements are all modeled w.r.t. a given topic, so that summaries are highly relevant to the topic and at the same time comply with topic-aware novelty, coverage and balance. Experimental results on the DUC 2005, 2006 and 2007 benchmark data sets demonstrate the effectiveness of our method.

In this paper, we propose the Interval-valued Matrix Factorization (IMF) framework. Matrix Factorization (MF) is a fundamental building block of data mining. MF techniques, such as Nonnegative Matrix Factorization (NMF) and Probabilistic Matrix Factorization (PMF), are widely used in applications of data mining. For example, NMF has shown its advantage in Face Analysis (FA) while PMF has been successfully applied to Collaborative Filtering (CF). In this paper, we analyze the data approximation in FA as well as CF applications and construct interval-valued matrices to capture these approximation phenomenons. We adapt basic NMF and PMF models to the interval-valued matrices and propose Interval-valued NMF (I-NMF) as well as Interval-valued PMF (I-PMF). We conduct extensive experiments to show that proposed I-NMF and I-PMF significantly outperform their single-valued counterparts in FA and CF applications.

Abstract Description Logic Programs (dl-programs) proposed by Eiter et al. constitute an elegant yet powerful formalism for the integration of answer set programming with description logics, for the Semantic Web. In this paper, we generalize the notions of completion and loop formulas of logic programs to description logic programs and show that the answer sets of a dl-program can be precisely captured by the models of its completion and loop formulas. Furthermore, we propose a new, alternative semantics for dl-programs, called the canonical answer set semantics, which is defined by the models of completion that satisfy what are called canonical loop formulas. A desirable property of canonical answer sets is that they are free of circular justifications. Some properties of canonical answer sets are also explored.

Temporally-ordered activity sequences are popular in many real-world domains. This paper presents an LDA-style topic model for sequences of temporal activities that captures three features of such sequences: 1) the counts of unique activities, 2) the Markov transition dependence and 3) the absolute or relative timestamp on each activity. In modeling the first two features we propose the concept of global transition probability and distinguish it with local transition probability used in previous work. In modeling the third feature, we employ a continuous time distribution to depict the time range of latent topics. The combination of the global transition probability and the temporal information helps to refine the mixture distribution over topics for temporal sequence analysis. We present results on the data of system call traces, showing better next activity prediction and sequence clustering.

Abstract We present a heuristic framework for attacking the undecidable termination problem of logic programs, as an alternative to current termination/nontermination proof approaches. We introduce an idea of termination prediction, which predicts termination of a logic program in case that neither a termination nor a non-termination proof is applicable. We establish a necessary and sufficient characterization of infinite (generalized) SLDNF-derivations with arbitrary (concrete or moded) queries, and develop an algorithm that predicts termination of general logic programs with arbitrary nonfloundering queries. We have implemented a termination prediction tool and obtained quite satisfactory experimental results. Except for five programs which break the experiment time limit, our prediction is 100% correct for all 296 benchmark programs of the Termination Competition 2007, of which 18 programs cannot be proved by any of the existing state-of-the-art analyzers like AProVE07, NTI, Polytool, and TALP.

Abstract This paper studies the stable model semantics of logic programs with (abstract) constraint atoms and their properties. We introduce a succinct abstract representation of these constraint atoms in which a constraint atom is represented compactly. We show two applications. First, under this representation of constraint atoms, we generalize the Gelfond–Lifschitz transformation and apply it to define stable models (also called answer sets) for logic programs with arbitrary constraint atoms. The resulting semantics turns out to coincide with the one defined by Son et al. (2007), which is based on a fixpoint approach. One advantage of our approach is that it can be applied, in a natural way, to define stable models for disjunctive logic programs with constraint atoms, which may appear in the disjunctive head as well as in the body of a rule. As a result, our approach to the stable model semantics for logic programs with constraint atoms generalizes a number of previous approaches. Second, we show that our abstract representation of constraint atoms provides a means to characterize dependencies of atoms in a program with constraint atoms, so that some standard characterizations and properties relying on these dependencies in the past for logic programs with ordinary atoms can be extended to logic programs with constraint atoms.

In this paper, we propose a new variant of latent Dirichlet allocation (LDA): Collective LDA (C-LDA), for multiple corpora modeling. C-LDA combines multiple corpora during learning such that it can transfer knowledge from one corpus to another; meanwhile it keeps a discriminative node which represents the corpus ID to constrain the learned topics in each corpus. Compared with LDA locally applied to the target corpus, C-LDA results in refined topic-word distribution, while compared with applying LDA globally and straightforwardly to the combined corpus, C-LDA keeps each topic only for one corpus. We demonstrate that C-LDA has improved performance with these advantages by experiments on several benchmark document data sets.

Ontology population is prone to cause inconsistency because the populating process is imprecise or the populated data may conflict with the original data. By assuming that the intensional part of the populated DL-based ontology is fixed and each removable ABox assertion is given a removal cost, we repair the ontology by deleting a subset of removable ABox assertions in which the sum of removal costs is minimum. We call such subset a minimum cost diagnosis. We show that, unless P=NP, the problem of finding a minimum cost diagnosis for a DL-Lite ontology is insolvable in PTIME w.r.t. data complexity. In spite of that, we present a feasible computational method for more general (i.e. SHIQ) ontologies. It transforms a SHIQ ontology to a set of disjoint propositional programs, thus reducing the original problem into a set of independent subproblems. Each such subproblem computes an optimal model and is solvable in logarithmic calls to a SAT solver. Experimental results show that the method can handle moderately complex ontologies with over thousands of ABox assertions, where all ABox assertions can be assumed removable.

Recursive loops in a logic program present a challenging problem to the PLP (Probabilistic Logic Programming) framework. On the one hand, they loop forever so that the PLP backward-chaining inferences would never stop. On the other hand, they may generate cyclic influences, which are disallowed in Bayesian networks. Therefore, in existing PLP approaches, logic programs with recursive loops are considered to be problematic and thus are excluded. In this article, we propose a novel solution to this problem by making use of recursive loops to build a stationary dynamic Bayesian network. We introduce a new PLP formalism, called a Bayesian knowledge base . It allows recursive loops and contains logic clauses of the form A ← A 1 ,…, A l , true , Context , Types , which naturally formulate the knowledge that the A i s have direct influences on A in the context Context under the type constraints Types . We use the well-founded model of a logic program to define the direct influence relation and apply SLG-resolution to compute the space of random variables together with their parental connections. This establishes a clear declarative semantics for a Bayesian knowledge base. We view a logic program with recursive loops as a special temporal model, where backward-chaining cycles of the form A ← … A ← … are interpreted as feedbacks. This extends existing PLP approaches, which mainly aim at (nontemporal) relational models.

Abstract Recently there has been a growing interest in research in tabling in the logic programming community because of its usefulness in a variety of application domains including program analysis, parsing, deductive databases, theorem proving, model checking, and logic-based probabilistic learning. The main idea of tabling is to memorize the answers to some subgoals and use the answers to resolve subsequent variant subgoals. Early resolution mechanisms proposed for tabling such as OLDT and SLG rely on suspension and resumption of subgoals to compute fixpoints. Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived on the basis of the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This article describes two strategies, namely, lazy and eager strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of interdependent subgoals as represented by a topmost looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this article, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e., sound and complete) and propose an optimization technique called early answer promotion to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.

We propose a new approach to clustering high dimensional data based on a novel notion of cluster cores, instead of on nearest neighbors. A cluster core is a fairly dense group with a maximal number of pairwise similar objects. It represents the core of a cluster, as all objects in a cluster are with a great degree attracted to it. As a result, building clusters from cluster cores achieves high accuracy. Other major characteristics of the approach include: (1) It uses a semantics-based similarity measure. (2) It does not incur the curse of dimensionality and is scalable linearly with the dimensionality of data. (3) It outperforms the well-known clustering algorithm, ROCK, with both lower time complexity and higher accuracy.

Semi-naive evaluation is an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers. The impact of this technique on top-down evaluation had been unknown. In this paper, we introduce semi-naive evaluation into linear tabling, a top-down resolution mechanism for tabled logic programs. We give the conditions for the technique to be safe and propose an optimization technique called early answer promotion to enhance its effectiveness. While semi-naive evaluation is not as effective in linear tabling as in bottom-up evaluation, it is worthwhile to be adopted. Our benchmarking shows that this technique gives significant speed-ups to some programs.

Density-based and grid-based clustering are two main clustering approaches. The former is famous for its capability of discovering clusters of various shapes and eliminating noises, while the latter is well known for its high speed. Combination of the two approaches seems to provide better clustering results. To the best of our knowledge, however, all existing algorithms that combine density-based clustering and grid-based clustering take cells as atomic units, in the sense that either all objects in a cell belong to a cluster or no object in the cell belong to any cluster. This requires the cells to be small enough to ensure the fine resolution of results. In high-dimensional spaces, however, the number of cells can be very large when cells are small, which would make the clustering process extremely costly. On the other hand, the number of neighbors of a cell grows exponentially with the dimensionality of datasets, which makes the complexity increase further. In this paper, we present a new approach that takes objects (or points) as the atomic units, so that the restriction of cell size can be relaxed without degrading the resolution of clustering results. In addition, a concept of ith-order neighbors is introduced to avoid considering the exponential number of neighboring cells. By considering only low-order neighbors, our algorithm is very efficient while losing only a little bit of accuracy. Experiments on synthetic and public data show that our algorithm can cluster high-dimensional data effectively and efficiently.

Traditional association rule mining algorithms only generate a large number of highly frequent rules, but these rules do not provide useful answers for what the high utility rules are. We develop a novel idea of top-K objective-directed data mining, which focuses on mining the top-K high utility closed patterns that directly support a given business objective. To association mining, we add the concept of utility to capture highly desirable statistical patterns and present a level-wise item-set mining algorithm. With both positive and negative utilities, the antimonotone pruning strategy in Apriori algorithm no longer holds. In response, we develop a new pruning strategy based on utilities that allow pruning of low utility itemsets to be done by means of a weaker but antimonotonic condition. Our experimental results show that our algorithm does not require a user specified minimum utility and hence is effective in practice.

We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level mappings, models/interargument relations, and the like. We propose a dynamic approach that employs some key dynamic features of an infinite (generalized) SLDNF-derivation, such as repetition of selected subgoals and recursive increase in term size. We also introduce a new formulation of SLDNF-trees, called generalized SLDNF-trees. Generalized SLDNF-trees deal with negative subgoals in the same way as Prolog and exist for any general logic programs.

The necessity of developing methods for discovering association patterns to increase business utility of an enterprise has long been recognized in the data mining community. This requires modeling specific association patterns that are both statistically (based on support and confidence) and semantically (based on objective utility) related to a given objective that a user wants to achieve or is interested in. However, no such general model has been reported in the literature. Traditional association mining focuses on deriving correlations among a set of items and their association rules; diaper /spl rarr/ beer only tells us that a pattern like {diaper} is statistically related to an item like beer. In this paper we present a new approach, called objective-oriented utility-based association (OOA) mining, to modeling such association patterns that are explicitly related to a user's objective and its utility. Due to its focus on a user's objective and the use of objective utility as key semantic information to measure the usefulness of association patterns, OOA mining differs significantly from existing approaches such as existing constraint-based association mining. We formally define OOA mining and develop an algorithm for mining OOA rules. The algorithm is an enhancement of a priori with specific mechanisms for handling objective utility. We prove that the utility constraint is neither monotone nor anti-monotone, succinct or convertible and present a novel pruning strategy based on the utility constraint to improve the efficiency of OOA mining.