Search

As concerns about health continue to grow, more and more works are being done in the field of food computing. One of the basic topics in food computing is how to extract important information from food and analysis it from a picture. However, food recognition poses some challenges. One challenge is that the type of food is closely related to its ingredients. Another challenge is that in Chinese dietary habits, a single meal typically includes multiple dishes. But existing food image datasets only contain single-food pictures. To address these challenges, we propose our model, Recognize After Early Fusion (RAEF): the Chinese food recognition based on the alignment of image and ingredients. We use a Vision Transformer as the backbone of our model and use an early fusion model to combine visual and ingredient features. Because there are no suitable datasets for multi-label food recognition models, we propose a new Chinese food dataset named Chinsefood-130. The dataset is in password: mr2b. After conducting experiments, we found that RAEF has great performance in both food and ingredient recognition. Compared to the performance of ViT, RAEF shows an F1 score improvement of 10% on food recognition and 12% on ingredient recognition. [ABSTRACT FROM AUTHOR]

Floorplanning is a crucial part of very large-scale integration (VLSI) physical design flow. It primarily determines the position of the blocks on a chip by considering the area, the total wirelength, etc., in light of several real-world limitations such as delay, price, and chip performance. Adopting B*-tree representation, this paper proposes a novel dual-population adaptive hybrid memetic algorithm called DPAHMA to handle the VLSI floorplanning problem effectively by optimizing the chip area and the total wirelength. Three main ideas are presented in this paper, including new definitions of crossover and mutation operators based on B*-tree encoding that overcome the shortcomings of the existing method, such as overly complicated operations on binary trees and a lack of diversity; a dynamic self-adjusting objective function, namely WeightDS, which is able to find solutions more suitable for the user-specified weight; and a main-auxiliary population mechanism by which a candidate population is introduced to assist the normal population in the global search phase. To make full use of the information obtained by the local search method, the candidate population keeps its high-quality solutions. The individuals from the candidate population crossover with the individuals from the normal population before the end of each iteration to obtain higher-quality solutions as much as possible. Experimental results for MCNC and GSRC benchmarks show that DPAHMA obtains floorplans effectively with better area and total wirelength than those of the state-of-the-art floorplanners. [ABSTRACT FROM AUTHOR]

Hardware and software partitioning (HW/SW) is a crucial step in the co‐design of embedded systems, which is a typical combinatorial optimisation problem. In practice, HW/SW instances would be of large scale, so it is of significant importance to design effective heuristic algorithms to obtain a high‐quality partitioning scheme. Different from previous heuristics, the HW/SW problem is treated as the minimum weight dominating set (MWDS) problem in this letter, and the mature local search framework for solving the MWDS problem is introduced to solve the HW/SW problem. In addition, two suitable vertex selection rules based on scoring function and tabu are proposed. Combined with the introduced local search framework, an efficient local search algorithm named HSLS is obtained. 96 classic benchmark instances are used to evaluate the performance of the HSLS algorithm, and the four latest evolutionary algorithms designed for the HW/SW problem are used as comparison algorithms, which are genetic algorithm, binary particle swarm optimisation, differential evolution, and group theory‐based optimisation algorithm. The experimental results show that the HSLS algorithm is far superior to the four comparison algorithms in terms of the optimal solution and obtains optimal solution on 78 benchmark instances, the four comparison algorithms obtain 43, 29, 42, and 41 optimal solutions respectively. [ABSTRACT FROM AUTHOR]

In the initial phase of production improvement for new technology, a fault chip may contain multiple defects. Owing to the interaction between defects, the state-of-the-art defect diagnosis procedure based on the simulation of single-modelled faults may generate a large number of candidate faults. Early methods based on test scores removed the correct candidate faults when narrowing the set of candidate faults, which caused a drop in diagnostic accuracy. This Letter proposes a new method combined with test scores to make better use of diagnostic information to reduce the number of candidate faults and improve diagnostic accuracy. The approach computes a score to every test by using fault-free output responses of a circuit, which can estimate its ability of fault identification. This results in a set of candidate faults with a reduced number of redundant faults and an increased number of real faults. Thus, the diagnosis resolution and precision are improved. The method can reduce the running time of the procedure for it uses the fault-free information to calculate the test scores offline. The experimental results on benchmark circuits demonstrate the efficacy of the proposed method. [ABSTRACT FROM AUTHOR]

Diagnosis is an essential step to improve the yield in semiconductor manufacturing industry. It is performed on a failing chip to determine the location of defects. However, the defect diagnosis procedure may obtain too much candidate faults which lead to difficulties in next physical failure analysis. Recently, the methods based on test score to reduce candidate fault set are proved to be effective. The previous test score diagnosis method based on fault free information computes a score for each test which implies the fault identification ability. This letter proposes a novel fault recognition based test score for diagnosis which considers the fault identification capability of tests more comprehensively to improve the original method. More information provided by unique responses and faults detected of a test is added to evaluate the fault recognition for calculating a test score. Then the novel test score which takes more advantages of diagnostic information is applied to adjusting the fault score and reducing the candidate set. The experimental results show that the novel approach reaches smaller fault candidate set than the previous method and increases the diagnostic resolution and precision, and thus provides an effective improvement on the accuracy of diagnosis. [ABSTRACT FROM AUTHOR]

The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances. [ABSTRACT FROM AUTHOR]

Distant supervision for neural relation extraction is an efficient approach to extracting massive relations with reference to plain texts. However, the existing neural methods fail to capture the critical words in sentence encoding and meanwhile lack useful sentence information for some positive training instances. To address the above issues, we propose a novel neural relation extraction model. First, we develop a word-level attention mechanism to distinguish the importance of each individual word in a sentence, increasing the attention weights for those critical words. Second, we investigate the semantic information from word embeddings of target entities, which can be developed as a supplementary feature for the extractor. Experimental results show that our model outperforms previous state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Because of the complexity of the failure diagnosis for large-scale discrete event systems (DESs), DESs with decentralized information have received a lot of attention. DESs with communication events are defined as distributed DESs. Stochastic discrete event systems (SDESs) are DESs with a probabilistic structure. A-diagnosability is an important property in failure diagnosis of SDES. In this paper, we investigate A-diagnosability in distributed SDESs. We define a local model and global model. Moreover, we construct a synchronized stochastic diagnoser to check A-diagnosability in distributed SDESs. We also propose a necessary and sufficient condition for a distributed SDES to be A-diagnosable. Some examples are described to illustrate our algorithms. [ABSTRACT FROM AUTHOR]

Many problems in real life can be transformed into combinatorial optimization problems. As an important heuristic, the local search algorithm has achieved outstanding performance in many classical combinatorial optimization problems. In this study, an efficient local search algorithm named KPLS is developed for a variant of the knapsack problem. Two novel ideas are proposed to help the KPLS algorithm achieve excellent performance. First, three scoring functions are designed to help the algorithm search the neighborhood space of the current solution accurately. Second, the hybrid perturbation strategy achieves a balance between greediness and randomness, which effectively facilitates the algorithm to escape from the local optimum. Eighty classic benchmark instances are adopted to evaluate the KPLS algorithm. The experimental results show that the KPLS algorithm outperforms the state-of-the-art algorithms in both the optimal solution and the average solution for most benchmark instances. [ABSTRACT FROM AUTHOR]

Fault diagnosis plays an important role in the prevention of harmful events in discrete event systems (DESs). Stochastic DES (SDES) is a more precise formulation of DES. In this paper, a novel approach that uses probabilistic logic to diagnose SDES is investigated. SDES is formalized as a set of probabilistic logical formulas. Moreover, a logical diagnoser is presented. Fault diagnosis of SDES has two properties: A-diagnosability and AA-diagnosability. On the basis of resolution principle, an algorithm is proposed to test A-diagnosability and AA-diagnosability of the SDES. Experimental results demonstrate that our algorithm improves the accuracy and efficiency of verifying diagnosability of SDES. [ABSTRACT FROM AUTHOR]

Deriving all minimal hitting sets (MHSes) for a family of conflict sets is a classical problem in model-based diagnosis. A technique for distributed MHSes based on the join relation of elements is proposed. Then, a strategy for deriving all distributed MHSes is presented. If the family of sets is decomposed into a number of equivalence classes based on the join relation, then parallel computation of MHSes for each distribution can be applied. Moreover, an incremental, distributed approach is introduced. When a new conflict set is added, only related distributed MHSes are chosen to incrementally update the final result. From a theoretical point of view, the complexity of the distributed algorithm is \boldsymbol O(2^num/k) , while the complexity of the corresponding centralized algorithm is \boldsymbol O(2^num) , with \boldsymbol k and num being the number of equivalence classes and the number of basic elements in all the conflict sets, respectively. Furthermore, compared with the corresponding centralized approach, a large number of set-containment checks are avoided by the incremental, distributed approach. Experimental results, including both numerous artificial examples and typical International Symposium on Circuits and Systems-85 benchmark circuit conflict set examples, offer evidence that, compared with centralized methods, the efficiency for deriving all MHSes in a distributed (incremental) way is considerably improved. [ABSTRACT FROM AUTHOR]

Backbones of a propositional theory are those literals, whose assignments are always true in every satisfying assignment, and have been applied for characterising the hardness of decision and optimisation problems. A new strategy called variable quality checking (VQC) is proposed for backbone computation. The VQC strategy to check the variable quality is used to obtain from the level information of variables when a Davis‐Putnam‐Logemann‐Loveland‐based satisfiablity problem solver returns satisfiable, and then decide which variable is the next variable to be computed, i.e. to select the most likely or unlikely backbone variable, whereas the previous algorithms randomly select a variable to compute. Furthermore, we use the VQC strategy to improve an efficient backbone algorithm called OTPV (one test per variable) and design a new algorithm for backbone computation, called BVQC (backbone with the VQC). The VQC strategy can also improve the performance of state‐of‐the‐art backbone algorithm core‐based with chunking, which calls OTPV to test whether the remaining literals are in the backbone or not. Experimental results show that BVQC significantly outperforms OTPV and gains a 1.30 times on average speed‐up, even up to one order of magnitude for some instances. [ABSTRACT FROM AUTHOR]

Model-based diagnosis of discrete event systems (DESs) has attracted more and more attention in recent years. Online diagnosis based on actually emitted sequences of observations is very important for dynamic systems in practice. However, the observations are often uncertain. Especially, the received observation sequences may not be the actually emitted ones completely. In this paper, we use directed acyclic graphs (DAGs) for modeling the partial emission orders of received observations. Furthermore, combining the concept Two restricted Successive Temporal Windows proposed by Zhao and Ouyang [AI Commun. 21(4) (2008), 249-262], we present a novel method to online update the global emitted observation sequence DAG gradually. Experimental results show that we can reason out the emitted observation sequences by this approach effectively. [ABSTRACT FROM AUTHOR]

Abstract: A novel self-adaptive differential evolution (SADE) algorithm is proposed in this paper. SADE adjusts the mutation rate F and the crossover rate adaptively, taking account of the different distribution of population. In order to balance an individual’s exploration and exploitation capability for different evolving phases, and are equal to two different self-adjusted nonlinear functions. Attention is concentrated on varying  and  dynamically with each generation evolution. SADE maintains the diversity of population and improves the global convergence ability. It also improves the efficiency and success rate and avoids the premature convergence. Simulation and comparisons based on test-sets of CSPs demonstrate the effectiveness, efficiency and robustness of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: Clustering is a popular data analysis and data mining technique. In this paper, an artificial bee colony clustering algorithm is presented to optimally partition N objects into K clusters. The Deb’s rules are used to direct the search direction of each candidate. This algorithm has been tested on several well-known real datasets and compared with other popular heuristics algorithm in clustering, such as GA, SA, TS, ACO and the recently proposed K–NM–PSO algorithm. The computational simulations reveal very encouraging results in terms of the quality of solution and the processing time required. [Copyright &y& Elsevier]

Recently, model-based diagnosis of discrete event systems has attracted more and more attention. Incremental diagnosis is essential for on-line diagnosis and the diagnosis is usually performed on-line. However, the observations are often uncertain. To address this problem, a new concept of two restricted successive temporal windows is proposed. Thereafter, an approach is given to support on-line incremental model-based diagnosis of discrete event systems with uncertain observations. All the observation sequences emitted by the previous window can be produced if the second temporal window is long enough (bigger than the maximal delay of transmission). In this way, the global emitted observation sequences can be inferred as well. The proposed approach is sound, complete, timely and universal. In particular, it is well suited for on-line diagnosis of discrete event systems when the received observations are too dense to find, in time, so-called “sound windows” by traditional approaches. [ABSTRACT FROM AUTHOR]

In model-based diagnosis, the candidate diagnostic results are generally characterized by all minimal hitting sets for the collection of all conflict sets. In this paper, a new method is proposed to judge a hitting set by the number of conflict sets corresponding to components, and the computing procedure is formalized by combining revised SE-tree (set enumeration tree) with closed nodes to generate all minimal hitting sets. Results show that because closed nodes are added into SE-tree, the search efficiency is highly improved. Furthermore, the proposed method is easy to be understood and implemented. Compared with other effective algorithms with completeness in some experimental tests, the diagnosis efficiency of our proposed method is higher, particularly for single- and double-fault diagnosis. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an improved model-based reasoning method to test circuit faults. The testing procedure is applicable even when the target system contains multiple faulty modes. Using our method, the observation could be planned appropriately to guarantee correct solutions to be in the restricted candidate space. The existent consistency-checking method and abductive reasoning method are special cases of our method. The relationship between the testing procedure and the corresponding prime implication is analyzed for algorithmic implementation. [Copyright &y& Elsevier]

Examines the methods for the computation of kernel consistency-based and kernel abductive diagnoses. Characterization of kernel model-based diagnosis based on the general causal theory; Relationship between the diagnostic procedure and the prime implicants/implicates; Drawbacks of traditional diagnostic methods.

Relation extraction (RE) is a fundamental task with various real-world applications. Although significant progress has been achieved in this research field, it is still limited to single-fact extraction. In practice, however, people tend to describe multiple relations in a single sentence. Apparently, multi-fact extraction is more reasonable yet challenging due to the mixture of diverse information. To address this issue, we introduce a novel syntax-based model for multi-fact extraction. Specifically, we propose a relational-expressiveness-based pruning strategy to refine the dependency parsing tree of each sentence, and then incorporate the customized and simplified syntax information into sentence encoding via Graph Convolutional Networks. Besides, distance embeddings are developed in our model to inform the extractor of the status of each word regarding different entity pairs in a sentence based on its shortest dependency path to the entities of interest. In addition, we explore fine-grained pooling strategy to integrate various evidences for the relation extractor to make accurate predictions. We conduct extensive experiments on the publicly-available datasets, and the experimental results verify the superiority of our model for multi-fact extraction in terms of both effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

In this paper, pattern diagnosis problem in stochastic discrete event system (SDES) is investigated. In a system, an abnormal state may be caused by the occurrence of several normal events. This kind of fault is called fault pattern. The diagnosis problem of fault pattern is defined as pattern diagnosis. Based on the notions of A-diagnosability and AA-diagnosability in SDES, the definitions of PA-diagnosability and PAA-diagnosability for pattern diagnosability in SDES are presented in this paper. In addition, a necessary and sufficient condition for an SDES to be PA-diagnosable is proposed. The goal of this paper is diagnosing fault pattern in the real systems. Three-Tank Water Level Control System and Heating, Ventilation, and Air-conditioning System are described to illustrate our algorithm. Experimental results demonstrate that pattern diagnosability in SDES is more accurate than that in DES. • Presenting the definition of pattern diagnosability in stochastic discrete event system. • Proposing a stochastic pattern according to the fault pattern of the stochastic discrete event system. • Constructing a stochastic pattern diagnoser. • Verifying the pattern diagnosability of stochastic discrete event system. • Using the method to Three-Tank Water Level Control System and Heating, Ventilation, and Air-conditioning System. [ABSTRACT FROM AUTHOR]

For many high-tech fields such as space exploration, nuclear technology, and smart automobiles, it is vital to timely find faulty components of man-made devices to ensure safety. However, there is nearly no enough diagnostic experience accumulated in these new devices, and thus, it is hardly suitable to only apply the traditional expert/experience-based fault diagnosis approach. Thus, model-based diagnosis was proposed for efficient detection of faulty components; this approach explores the behavioral and structural information of the device to be diagnosed, and no experience is required. In model-based diagnosis, for a device to be diagnosed, minimal conflict sets of components are first generated, and all minimal hitting-sets for them will be derived as candidate diagnoses. Therefore, it is vital to efficiently generate all minimal hitting-sets to find the final diagnosis. Unfortunately, it is proven to be NP-hard when deriving all minimal hitting-sets for given minimal conflict sets. To improve the computing efficiency, in this article, we propose a novel approach called TreeMerge, which considers a special type of tree structure of minimal conflict sets of large sizes since structural information usually plays an important role in solving complex problems. Theoretically, compared with other algorithms, the time complexity of the new algorithm is greatly reduced, as the time complexity of the new algorithm becomes linear rather than quadratic. Furthermore, experimental results on multiple synthetic and benchmark examples show that the proposed TreeMerge algorithm is more efficient than many other state-of-the-art methods, with a reduction of several orders of magnitude runtime (seconds). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a novel method is proposed for judging whether a component set is a consistency-based diagnostic set, using SAT solvers. Firstly, the model of the system to be diagnosed and all the observations are described with conjunctive normal forms (CNF). Then, all the related clauses in the CNF files to the components other than the considered ones are extracted, to be used for satisfiability checking by SAT solvers. Next, all the minimal consistency-based diagnostic sets are derived by the CSSE-tree or by other similar algorithms. We have implemented four related algorithms, by calling the gold medal SAT solver in SAT07 competition – RSAT. Experimental results show that all the minimal consistency-based diagnostic sets can be quickly computed. Especially our CSSE-tree has the best efficiency for the single- or double-fault diagnosis. [Copyright &y& Elsevier]

The calculation of minimal incoherence-preserving sub-TBox (MIPS) is an important task in incoherent ontology debugging. Existing approaches to this task are inefficient when debugging large incoherent ontology with a lot of unsatisfiable concepts. To resolve the problem, we first extract a clash module from the ontology and then identify the root unsatisfiable concepts from the clash module. Afterward, the minimal unsatisfiability-preserving sub-TBox (MUPS) of each root unsatisfiable concept can be calculated on the basis of the clash module. We have proved that the MIPS of an incoherent ontology is equal to the union of the MUPSes of the root unsatisfiable concepts. Our approach can successfully avoid calculating a considerable number of MUPSes irrelevant to the MIPS. Experiments with a variety of test ontologies show that the proposed approach of calculating MIPS is efficient and practical. [ABSTRACT FROM AUTHOR]

The set packing problem (SPP) is a significant NP-hard combinatorial optimization problem with extensive applications. In this paper, we encode the set packing problem as the maximum weighted independent set (MWIS) problem and solve the encoded problem with an efficient algorithm designed to the MWIS problem. We compare the independent set-based method with the state-of-the-art algorithms for the set packing problem on the 64 standard benchmark instances. The experimental results show that the independent set-based method is superior to the existing algorithms in terms of the quality of the solutions and running time obtained the solutions. [ABSTRACT FROM AUTHOR]

2-D electromagnetic model with a line source uses Preconditioned Conjugate Gradient to solve the stiffness matrix and Herrmann's pseudo-delta function to simulate the neighborhood of the singular source. We employ this Finite Element Method (FEM) on Fermi-GPU, which is the third generation GPU for the general computing purpose. Our algorithm takes advantage of the GPU's particular characteristics of Single Instruction Multiple Thread (SIMT) architecture and runs entirely on the GPU to minimize the transfer time between CPU and GPU. Meanwhile, we design a reasonable pre-conditioner (Diagonal Pre-conditioner) on the GPU and inject a mixed scheme into our algorithm for obtaining the good performance. In the numerical experiments, the correctness of the algorithm is acknowledged, and it achieves high performance by outperforming CPU solvers over hundreds of times. Indeed, it allows finer mesh generation so as to obtain more accurate resolutions and advance the ability of data interpretation of geophysical prospecting. [ABSTRACT FROM AUTHOR]

The minimum connected dominating set (MCDS) problem is a very significant NP-hard combinatorial optimization problem, and it has been used in many fields such as wireless sensor networks and ad hoc networks. In this paper, we propose a novel multi-start local search algorithm (MSLS) to tackle the minimum connected dominating set problem. Firstly, we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum. Secondly, we use the configuration checking (CC) mechanism to avoid the cycling problem. Then, we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism. Finally, we propose a multi-start local search framework based on these mechanisms. We compare the algorithm MSLS with other compared algorithms on extensive instances. The results of experiment show that MSLS is superior to other algorithms in solution quality and time efficiency on most instances. [ABSTRACT FROM AUTHOR]