Search

We prove that the reachability problem for two-dimensional vector addition systems with states is NL-complete or PSPACE-complete, depending on whether the numbers in the input are encoded in unary or binary. As a key underlying technical result, we show that, if a configuration is reachable, then there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This, in turn, enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded.

Aiming at exploiting the discriminative deep features and encoding the high-level structures, this letter presents a deep-features-based high-order triple discriminative random field model, abbreviated as DF-HoTDF, for nonstationary polarimetric synthetic aperture radar (PolSAR) image classification. First, the DF-HoTDF model extracts the discriminative deep features by a graph-based complex-valued 3-D convolutional neural network (CV-3-D-CNN) and then constructs the unary potential by a negative log function. Second, it introduces an auxiliary field $u$ to explicitly regulate the nonstationary label patterns of the PolSAR image and then constructs a pairwise potential guided by $u$ to capture greater pairwise label interactions. Third, it defines a high-order potential on high-order cliques to encode high-level structures. Finally, under the discriminative model framework, the DF-HoTDF model has a weighted fusion of the unary potential, the pairwise potential, and the high-order potential. Then, with the DF-HoTDF model, we iteratively optimize the class label and the stationary maps until they converge. The experimental results demonstrate that the proposed DF-HoTDF model is of superior performances in nonstationary PolSAR image classification and that it can provide better label consistency in homogeneous region and better target structures and edge locations in heterogeneous region.

For a completely distributive De Morgan algebra L, we develop a general framework of L-fuzzy rough sets. Said precisely, we introduce a pair of L-fuzzy approximation operators, called upper and lower L-fuzzifying approximation operators derived from general L-fuzzifying neighborhood systems. It is shown that the proposed approximation operators are a common extension of the L-fuzzifying approximation operators derived from L-fuzzy relations (INS 2019) and the approximation operators derived from general neighborhood systems (KBS 2014). Furthermore, we investigate the unary, serial, reflexive, transitive and symmetric conditions in general L-fuzzifying neighborhood systems, and then study the associated approximation operators from both a constructive method and an axiomatic method. Particularly, for transitivity (resp., symmetry), we give two interpretations, one is an appropriate generalization of transitivity (resp., symmetry) for L-fuzzy relations, and the other is a suitable extension of transitivity (resp., symmetry) for general neighborhood systems. In addition, for some special L-fuzzifying approximation operators, we use single axiom to characterize them, respectively. At last, the proposed approximation operators are applied in the research of incomplete information system, and a three-way decision model based on them is established. To exhibit the effectiveness of the model, a practical example is presented.

Disease gene prediction is an essential issue in biomedical research. In the early days, annotation-based approaches were proposed for this problem. With the development of high-throughput technologies, interaction data between genes/proteins have grown quickly and covered almost genome and proteome; thus, network-based methods for the problem become prominent. In parallel, machine learning techniques, which formulate the problem as a classification, have also been proposed. Here, we firstly show a roadmap of the machine learning-based methods for the disease gene prediction. In the beginning, the problem was usually approached using a binary classification, where positive and negative training sample sets are comprised of disease genes and non-disease genes, respectively. The disease genes are ones known to be associated with diseases; meanwhile, non-disease genes were randomly selected from those not yet known to be associated with diseases. However, the later may contain unknown disease genes. To overcome this uncertainty of defining the non-disease genes, more realistic approaches have been proposed for the problem, such as unary and semi-supervised classification. Recently, more advanced methods, including ensemble learning, matrix factorization and deep learning, have been proposed for the problem. Secondly, 12 representative machine learning-based methods for the disease gene prediction were examined and compared in terms of prediction performance and running time. Finally, their advantages, disadvantages, interpretability and trust were also analyzed and discussed.

We consider the competitive multi-agent scheduling problem on a single machine, where each agent’s cost function is to minimize its total weighted late work. The aim is to find the Pareto-optimal frontier, i.e., the set of all Pareto-optimal points. When the number of agents is arbitrary, the decision problem is shown to be unary $$\mathcal {NP}$$ -complete even if all jobs have the unit weights. When the number of agents is two, the decision problems are shown to be binary $$\mathcal {NP}$$ -complete for the case in which all jobs have the common due date and the case in which all jobs have the unit processing times. When the number of agents is a fixed constant, a pseudo-polynomial dynamic programming algorithm and a $$(1+\epsilon )$$ -approximate Pareto-optimal frontier are designed to solve it.

This paper describes a unified global constraint to model scheduling problems with unary resources, i.e., each resource can process only a single activity at a time. In addition, the constraint enforces sequence-dependent transition times between activities. It often happens that activities are grouped into families with zero transition times within a family. Moreover, some of the activities might be optional from the resource viewpoint (typically in the case of alternative resources). The global constraint unifies reasoning with both optional activities and families of activities. The scalable filtering algorithms we discuss keep a low time complexity of $$\mathcal {O}(n \cdot \log (n) \cdot \log (f))$$ , where n is the number of tasks on the resource and f is the number of families. This results from the fact that we extend the $$\varTheta $$ -tree data structure used for the Unary Resource constraint without transition times. Our experiments demonstrate that our global constraint strengthens the pruning of domains as compared with existing approaches, leading to important speedups. Moreover, our low time complexity allows maintaining a small overhead, even for large instances. These conclusions are particularly true when optional activities are present in the problem.

In this paper, we study monotone set functions defined as the composition of an additive measure with a strictly increasing function. This function is a unary operator in continuous-valued logic, called the tau function, and it is a generator function-based parametric mapping. We provide a necessary and sufficient condition for the equality of two tau functions that are induced by different generator functions. Using the tau function and its properties, we introduce a new monotone measure that we call the tau-additive measure. This measure is computationally simple and it can be viewed as an upper or lower probability depending on the parameter settings of the tau function. We present the parameter-dependent submodularity and supermodularity of the tau-additive measure and show how this measure can be constructed from a set function on a finite set. This procedure is analogous to how the well-known lambda-additive measure can be constructed, but our method is computationally simpler. We demonstrate that the tau-additive measure can be used to approximate the lambda-additive measure. Lastly, exploiting these theoretical results, we present an application in the area of human resource management.

Unification is a central operation in constructing a range of computational logic systems based on first-order and higher-order logics. First-order unification has several properties that guide its incorporation in such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-calledpatternsubset of higher-order unification was designed to be a small extension to first-order unification that respects the laws governingλ-binding (i.e., the equalities forα,β, andη-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been used in numerous implemented systems and in various theoretical settings, it is too weak for many applications. This paper defines an extension of pattern unification that should make it more generally applicable, especially in proof assistants that allow for higher-order functions. This extension’s main idea is that the arguments to a higher-order, free variable can be more than just distinct bound variables. In particular, such arguments can be terms constructed from (sufficient numbers of) such bound variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.

Event class is an abstract event that represents a set of events with some common features. There are inherent relations among event classes. Event classes and their relations are the important parts of event knowledge base. We gave a novel framework to represent event class semantic by marriage Neo-Davidsonian event semantic and 6-element event class model. The framework treated the predicate of event class as unary predicate with event class argument ec only. It connected the predicate and the other elements of event class with connecting symbol ⁁. And the framework can’t only represent the taxonomic relations among event classes, but also respectively represent non-taxonomic relations via the connecting symbols ⊄, ⊳, →, ∥ and ⊒. The representation examples indicate the novel framework can represent event classes semantic and different kinds of relations among event classes.

We revisit the classical single-machine scheduling problem to minimize total tardiness with deadlines. The problem is binary NP-hard even without the deadline restrictions. It was reported early in Koulamas and Kyparisis (Eur J Oper Res 133:447–453, 2001) that the exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) of the problem is still open. We show that this problem is unary NP-hard.

In a recent paper [12] we have shown that aggregation functions on a bounded lattice L form a clone, i.e., the set of functions closed under projections and composition of functions. Moreover, for any finite lattice L we gave a finite set of unary and binary aggregation functions on L from which the aggregation clone is generated. In this paper, a general method for constructing generating sets of the aggregation clone on L is presented. Our approach is based on extending of L-valued capacities leading to so-called full systems of aggregation functions. Several full systems on L are presented (including singleton ones) and their arities are discussed.

There are two problems in SAR image change detection when using difference images (DIs), i.e., 1) the subtraction operation results in serious loss of semantic information in DIs; and 2) the boundary of DI is uncertain. We propose a change detection method based on Neural-CRF structure. Firstly, Transformer-UNet (TR-UNet) is designed to provide the unary potential for CRF. The TR-Attention module improves the semantic expression ability of UNet by introducing the multi-head attention mechanism of TR. Secondly, a cascade CRF as Recurrent Neural Network, named as C-CRF-RNN, is proposed to update the unary potential and pairwise potential simultaneously. This improves the ability of CRF-RNN to refine pixel-level label prediction. Experiments show that the proposed method consistently outperforms the state-of-the-art methods on two benchmarks including berne data and ottawa data.

Immunofixation Electrophoresis (IFE) analysis is of great importance to the diagnosis of Multiple Myeloma, which is among the top-9 cancer killers in the United States, but has rarely been studied in the context of deep learning. Two possible reasons are: 1) the recognition of IFE patterns is dependent on the co-location of bands that forms a binary relation, different from the unary relation (visual features to label) that deep learning is good at modeling; 2) deep classification models may perform with high accuracy for IFE recognition but is not able to provide firm evidence (where the co-location patterns are) for its predictions, rendering difficulty for technicians to validate the results. We propose to address these issues with collocative learning, in which a collocative tensor has been constructed to transform the binary relations into unary relations that are compatible with conventional deep networks, and a location-label-free method that utilizes the Grad-CAM saliency map for evidence backtracking has been proposed for accurate localization. In addition, we have proposed Coached Attention Gates that can regulate the inference of the learning to be more consistent with human logic and thus support the evidence backtracking. The experimental results show that the proposed method has obtained a performance gain over its base model ResNet18 by 741.30% in IoU and also outperformed popular deep networks of DenseNet, CBAM, and Inception-v3.

User feedback such as clicks, likes and follows is widely considered positive signal, as users infer their preference through these signals. However, a click feedback that is intended for a purchase indicates that the user's interest level is greater than that of a user who clicks just to view a page. Thus, compared with the unary positive feedback, some other types of user feedback are considered more reliable because of their ability to indicate the different preference levels of users. Some recommender systems focus on using such multiple-level positive feedback to develop model-based methods. In this paper, we take them into account to implement a nearest-neighbor method that demonstrates competitive performance for session-based recommendation. Herein, we present experimental evaluations on different domain datasets to demonstrate the benefits of our proposed method. Our results show that incorporating such multiple-level preferences of users with the neighbor-based model leads to an improvement in performance for session-based recommendation.

Online multi-object tracking (MOT) is an active research topic in the domain of computer vision. Although many previously proposed algorithms have exhibited decent results, the issue of tracklet inactivation has not been sufficiently studied. Simple strategies such as using a fixed threshold on classification scores are adopted, yielding undesirable tracking mistakes and limiting the overall performance. In this paper, a conditional random field (CRF) based framework is put forward to tackle the tracklet inactivation issue in online MOT problems. A discrete CRF which exploits the intra-frame relationship between tracking hypotheses is developed to improve the robustness of tracklet inactivation. Separate sets of feature functions are designed for the unary and binary terms in the CRF, which take into account various tracking challenges in practical scenarios. To handle the problem of varying CRF nodes in the MOT context, two strategies named as hypothesis filtering and dummy nodes are employed. In the proposed framework, the inference stage is conducted by using the loopy belief propagation algorithm, and the CRF parameters are determined by utilizing the maximum likelihood estimation method followed by slight manual adjustment. Experimental results show that the tracker combined with the CRF-based framework outperforms the baseline on the MOT16 and MOT17 benchmarks. The extensibility of the proposed framework is further validated by an extensive experiment., 13 pages, 8 figures. This work has been accepted by IEEE Transactions on Multimedia. (DOI: 10.1109/TMM.2021.3062489)

In this paper, we study operator dependent modifiers and we interpret the dual pair of modal operators based on an algebraic definition. It is a known fact that the substantiating and weakening modifier operators can be induced by repeating the arguments of conjunctive and disjunctive operators. We provide the conditions for which these modifier operators satisfy the requirements for a dual pair of necessity and possibility operators. Next, the necessary and sufficient condition for the distributivity of unary operators over conjunctive and disjunctive operators is presented. This also means that setting the distributivity as a requirement results in a unary operator that is identical to the modal operators mentioned above. Using this property, we establish an important connection between modal operators and linguistic hedges. Previously, we demonstrated that the unary operators induced by compositions of two strong negations satisfy the requirements for a dual pair of modal operators. Here, we view the negation operator as a modifier operator. Then, it is shown that (1) the strong negations, (2) the substantiating and weakening modifier operators, modal operators and linguistic hedges mentioned above, and (3) the unary operators, which are distributive over conjunctive and disjunctive operators, may be viewed as special cases of a unified unary operator class.

Detecting anatomical landmarks in medical images plays an essential role in understanding the anatomy and planning automated processing. In recent years, a variety of deep neural network methods have been developed to detect landmarks automatically. However, all of those methods are unary in the sense that a highly specialized network is trained for a single task say associated with a particular anatomical region. In this work, for the first time, we investigate the idea of “You Only Learn Once (YOLO)” and develop a universal anatomical landmark detection model to realize multiple landmark detection tasks with end-to-end training based on mixed datasets. The model consists of a local network and a global network: The local network is built upon the idea of universal U-Net to learn multi-domain local features and the global network is a parallelly-duplicated sequential of dilated convolutions that extract global features to further disambiguate the landmark locations. It is worth mentioning that the new model design requires much fewer parameters than models with standard convolutions to train. We evaluate our YOLO model on three X-ray datasets of 1,588 images on the head, hand, and chest, collectively contributing 62 landmarks. The experimental results show that our proposed universal model behaves largely better than any previous models trained on multiple datasets. It even beats the performance of the model that is trained separately for every single dataset. Our code is available at https://github.com/ICT-MIRACLE-lab/YOLO_Universal_Anatomical_Landmark_Detection.

Ontologies are an expressive power used as a crucial element to enrich knowledge graphs by their rich data and ontological concepts that are often necessary for logical inference. Recently, ontology embedding has gained increasing attention in real-world ontologies for its ability to learn sub-sumption axioms, unary and binary assertions in these ontologies, while maintaining some syntactic, semantic properties and deductive closures. In general, learning methods assume an ontology to be complete while there are different situations in which it can be excepted to be uncertain, for example when they are provided by human annotators in classification, or even missing. However, embedding such uncertain ontologies is typically ignored. In this paper, we propose a novel embedding approach, UOE, which can embed uncertain lightweight ontology encoded in DL-lite in order to better capture the relationships between the uncertainty and the ontologies in the semantic space. Experimental results show that our model can robustly learn representations of uncertain ontologies when evaluated on publicly available datasets used on machine learning benchmarks.

This work deals with the problem of semantic optimization of the central class of conjunctive queries (CQs). Since CQ evaluation is NP-complete, a long line of research has focussed on identifying fragments of CQs that can be efficiently evaluated. One of the most general restrictions corresponds to generalized hypetreewidth bounded by a fixed constant k ≥ 1; the associated fragment is denoted GHW k . A CQ is semantically in GHW k if it is equivalent to a CQ in GHW k . The problem of checking whether a CQ is semantically in GHW k has been studied in the constraint-free case, and it has been shown to be NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (TGDs) that can express, e.g., inclusion dependencies, or equality-generating dependencies (EGDs) that capture, e.g., key dependencies, a CQ may turn out to be semantically in GHW k under the constraints, while not being semantically in GHW k without the constraints. This opens avenues to new query optimization techniques. In this article, we initiate and develop the theory of semantic optimization of CQs under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically in GHW k , for a fixed k ≥ 1, under the constraints, or, in other words, is the query equivalent to one that belongs to GHW k over all those databases that satisfy the constraints? We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not a sufficient condition for the decidability of the problem in question. In particular, we show that checking whether a CQ is semantically in GHW 1 is undecidable in the presence of full TGDs (i.e., Datalog rules) or EGDs. In view of the above negative results, we focus on the main classes of TGDs for which CQ containment is decidable and that do not capture the class of full TGDs, i.e., guarded, non-recursive, and sticky sets of TGDs, and show that the problem in question is decidable, while its complexity coincides with the complexity of CQ containment. We also consider key dependencies over unary and binary relations, and we show that the problem in question is decidable in elementary time. Furthermore, we investigate whether being semantically in GHW k alleviates the cost of query evaluation. Finally, in case a CQ is not semantically in GHW k , we discuss how it can be approximated via a CQ that falls in GHW k in an optimal way. Such approximations might help finding “quick” answers to the input query when exact evaluation is intractable.

International audience; We study a variant of the Multi-Agent Path Finding (MAPF) problem in which the group of agents are required to stay connected with a supervising base station throughout the execution. In addition, we consider the problem of covering an area with the same connectivity constraint. We show that both problems are PSPACE-complete on directed and undirected topological graphs while checking the existence of a bounded plan is NP-complete when the bound is given in unary (and PSPACE-hard when the encoding is in binary). Moreover, we identify a realistic class of topo-logical graphs on which the decision problem falls in NLOGSPACE although the bounded versions remain NP-complete for unary encoding.

In covering-based rough sets, many basic issues are related to minimal and maximal descriptions. For a covering approximation space with a large cardinal, it would be tedious and complicated to use set representations to solve the issues about minimal and maximal descriptions. Therefore it is necessary to study matrix representations by which calculations will become algorithmic and can be easily implemented by computers. In this paper, we use matrix approaches to investigate some issues about minimal and maximal descriptions in covering-based rough sets. Firstly, several new matrices and matrix operations are defined by which one can compute the minimal description and the approximation operator about the minimal description. Inspired by this result, a matrix method is presented to judge whether a covering is unary. Secondly, the maximal description and the approximation operator about the maximal description are also computed by these new matrices and matrix operations. Finally, based on the above results, we propose a matrix method to efficiently compute reductions of coverings. Moreover, we propose two types of reducts of covering information systems via minimal and maximal descriptions respectively, and we use matrix approaches to compute them. In a word, these results show an interesting view to investigate the combination between matrices and covering-based rough sets.

This paper studies operations on possibilistic belief structures, which are constructed by basic possibility assignments, or equivalently, maxitive belief structures, as a framework for modeling imprecise possibility distributions. Different from Dempster–Shafer structures, it is shown that there is no one-to-one correspondence between basic possibility assignments and their induced upper and lower possibilities. The operations on the set of basic possibility assignments might not induce the operations on their upper and lower possibilities. An operation on basic possibility assignments is called proper if it is also the operation on their upper and lower possibilities. We introduce set operations and point operations on basic possibility assignments. Set operations include intersection, union, complement, difference, projection, marginalization, cylindrical extension, vacuous extension and Cartesian product operations. Point operations include all binary and unary operations. We show that all point operations are proper. For set operations, it is shown that union, projection, marginalization, cylindrical extension, vacuous extension and Cartesian product operations are proper, while intersection, complement and difference operations are not proper. In addition, we study construction of compatible possibility distributions and show that the lower possibility of a basic possibility assignment can be represented by the infinimum of compatible possibility distributions. We also show that the local computation technique can be applied to the computation problem of possibilistic belief structures.

Recurrent neural networks (RNNs) are now widely used on sequence generation tasks due to their ability to learn long-range dependencies and to generate sequences of arbitrary length. However, their left-to-right generation procedure only allows a limited control from a potential user which makes them unsuitable for interactive and creative usages such as interactive music generation. This article introduces a novel architecture called anticipation-RNN which possesses the assets of the RNN-based generative models while allowing to enforce user-defined unary constraints. We demonstrate its efficiency on the task of generating melodies satisfying unary constraints in the style of the soprano parts of the J.S. Bach chorale harmonizations. Sampling using the anticipation-RNN is of the same order of complexity than sampling from the traditional RNN model. This fast and interactive generation of musical sequences opens ways to devise real-time systems that could be used for creative purposes.

Purpose Typical feature-matching algorithms use only unary constraints on appearances to build correspondences where little structure information is used. Ignoring structure information makes them sensitive to various environmental perturbations. The purpose of this paper is to propose a novel graph-based method that aims to improve matching accuracy by fully exploiting the structure information. Design/methodology/approach Instead of viewing a frame as a simple collection of keypoints, the proposed approach organizes a frame as a graph by treating each keypoint as a vertex, where structure information is integrated in edges between vertices. Subsequently, the matching process of finding keypoint correspondence is formulated in a graph matching manner. Findings The authors compare it with several state-of-the-art visual simultaneous localization and mapping algorithms on three datasets. Experimental results reveal that the ORB-G algorithm provides more accurate and robust trajectories in general. Originality/value Instead of viewing a frame as a simple collection of keypoints, the proposed approach organizes a frame as a graph by treating each keypoint as a vertex, where structure information is integrated in edges between vertices. Subsequently, the matching process of finding keypoint correspondence is formulated in a graph matching manner.

The multi-covering rough sets (MCRSs) are a popular aspect of rough sets. It is easy to see that classical rough sets, covering rough sets (CRSs) and multi-granulation rough sets (MGRSs) are all the special cases of the MCRSs. Recently, the algebraic theory of these rough set models mentioned above have been researched in detail. However, the algebraic theory of MCRSs has not been studied until now. It is necessary for researchers to explore the algebraic theory of MCRSs. In this paper, we focus on the operation and algebraic theories of two types of MCRS models. First, the properties of the two types of multi-covering set approximations are discussed. Especially, the properties of multi-covering approximation operators based on the unary coverings are deeply researched. Second, the operation properties with respect to intersection and union of MCRSs are researched. Meanwhile, to compute the intersection and union of MCRSs, several algorithms are constructed. Finally, on the basis of the operation properties of MCRSs, many meaningful algebraic properties of MCRSs are deeply studied.

Commutativity is an important property in two-step information merging procedure. It is shown that the result obtained from the procedure should not depend on the order in which signal steps are performed. In the case of a bisymmetric aggregation operator with the neutral element, Saminger et al. have provided a full characterization of commutative n-ary operator by means of unary distributive functions. Further, characterizations of these unary distributive functions can be viewed as resolving a kind of the Cauchy-like equations f ( x ⊕ y ) = f ( x ) ⊕ f ( y ) , where f : [ 0 , 1 ] → [ 0 , 1 ] is a monotone function, ⊕ is a bisymmetric aggregation operator with the neutral element. In this paper, we are still devoted to investigating and fully characterizing the Cauchy-like equation f ( U ( x , y ) ) = U ( f ( x ) , f ( y ) ) , where f : [ 0 , 1 ] → [ 0 , 1 ] is an unknown function but not necessarily monotone, U is a uninorm continuous in ( 0 , 1 ) 2 . These results show the key technology is how to find a transformation from this equation into several known cases. Moreover, this equation has completely different and non-monotone solutions in comparison with the obtained results.

Objective The Arden Syntax for Medical Logic Systems is a standard for encoding and sharing medical knowledge in the form of Medical Logic Modules. To improve accessibility for clinicians, the originators of the standard deliberately designed Arden Syntax expressions to resemble natural language, and parentheses around operands are not generally required. For certain patterns of nested expressions, however, the use of parentheses is mandatory, otherwise they are not accepted by an Arden Syntax environment. In this study, we refer to such patterns as anomalies. The purpose of this paper is to investigate the extent and the circumstances of such anomalies, and to outline a solution based on an alternative grammar encoding approach. Methods To analyze the distribution of anomalies in nested expressions, we developed two custom-made complementary utilities. The first utility, termed parser, checks a single expression pattern against the specification-compliant grammar for syntactic correctness. The second utility, termed composer, automatically creates an extensive amount of expression patterns by permuting and nesting operators without the use of parentheses, and stores these together with the expected syntactic correctness. By means of these utilities we conducted a comprehensive analysis of anomalies by comparing the expected correctness with the actual correctness. Any detected anomalies are stored into a set of files, grouped by the respective top-level operator, for a subsequent analysis. Results The composer utility nested 165 unary, binary, or ternary operators of Arden Syntax version 2.8 to a depth of two, resulting in a set of 76,533 expression patterns, of which 18,978 (24.8%) have been identified as anomalies. An automated assessment of their practical relevance for medical knowledge encoding is infeasible. Manual screening of selected samples indicated that only a small proportion of the detected anomalies would be relevant. The cause of the anomalies lies in the encoding of the grammar. A change of the basic encoding approach with some additional customizations eliminates the anomalies. A working expression parser is included in the supplementary material. Conclusion Arden Syntax expressions are affected by anomalies. Since only a small proportion of them have practical relevance and they cannot cause false calculations or clinical decisions, their practical impact is likely limited. However, they may be potential points of confusion for knowledge engineers. An alternative expression grammar, based on a different encoding approach, would not only eliminate the anomalies, but could considerably facilitate both maintenance and further development of the standard.

Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an interesting research direction with important applications, c ...

In a recent paper we proposed the study of aggregation functions on lattices via clone theory approach. Observing that aggregation functions on lattices just correspond to $0,1$-monotone clones, we have shown that all aggregation functions on a finite lattice $L$ can be obtained as usual composition of lattice operations $\wedge,\vee$, and certain unary and binary aggregation functions. The aim of this paper is to present a generating set for the class of intermediate (or, equivalently, idempotent) aggregation functions. This set consists of lattice operations and certain ternary idempotent aggregation functions., Comment: 18 pages

The main aim of this article is to extend our representation results on tense MV-algebras into a partial mapping setting. Tense MV-algebras are just MV-algebras with new unary operations G and H which express a universal time quantifiers and they were introduced by D. Diaconescu and G. Georgescu. (C) 2017 Elsevier B.V. All rights reserved.

A propositional conditional of the form ( B | A ) , representing the default rule “If A , then usually B ”, goes beyond the limits of classical logic, and the semantics of a knowledge base consisting of such conditionals must take into account the three-valued nature of conditionals. Ordinal conditional functions (OCF), also called ranking functions, assign a degree of implausibility to possible worlds and provide a convenient semantic framework for conditionals. To each consistent knowledge base R , system Z associates a unique minimal OCF accepting R , enabling inductive reasoning from this model. In this article, we present an approach of transforming the ideas of the popular system Z to the first-order case. We develop system Z FO that considers first-order conditionals of the form ( B ( x ) | A ( x ) ) . The notion of tolerance used in system Z is extended to the notion of tolerance pairs, taking also a partition of the domain elements into account. We show that each tolerance pair induces a system Z-like ranking function, and we provide an algorithm systematically generating all tolerance pairs. We introduce the notion of minimal tolerance pairs and a corresponding refinement of the algorithm computing all minimal tolerance pairs. An inference relation based on minimal tolerance pairs is presented, and it is shown that system Z FO properly generalizes the basic ideas underlying system Z.

In this paper, we study the ordered *-semigroups in terms of fuzzy subsets in detail and define a unary operation *on the set of all the fuzzy subsets of an ordered *-semigroup S, which is a key notion to introduce the concepts of prime, weakly prime and semiprime fuzzy ideals of S. Furthermore, we establish the relationships among these three types of fuzzy ideals and give some characterizations of intra-regular ordered *-semigroups in terms of fuzzy ideals. Finally, we define and study the fuzzy filters of an ordered *-semigroup. In particular, we discuss the relationships between the filters and the fuzzy filters in ordered *-semigroups.

© 1992-2012 IEEE. Variations of target appearances due to illumination changes, heavy occlusions, and target deformations are the major factors for tracking drift. In this paper, we show that the tracking drift can be effectively corrected by exploiting the relationship between the current tracker and its historical tracker snapshots. Here, a multi-expert framework is established by the current tracker and its historical trained tracker snapshots. The proposed scheme is formulated into a unified discrete graph optimization framework, whose nodes are modeled by the hypotheses of the multiple experts. Furthermore, an exact solution of the discrete graph exists giving the object state estimation at each time step. With the unary and binary compatibility graph scores defined properly, the proposed framework corrects the tracker drift via selecting the best expert hypothesis, which implicitly analyzes the recent performance of the multi-expert by only evaluating graph scores at the current frame. Three base trackers are integrated into the proposed framework to validate its effectiveness. We first integrate the online SVM on a budget algorithm into the framework with significant improvement. Then, the regression correlation filters with hand-crafted features and deep convolutional neural network features are introduced, respectively, to further boost the tracking performance. The proposed three trackers are extensively evaluated on three data sets: TB-50, TB-100, and VOT2015. The experimental results demonstrate the excellent performance of the proposed approaches against the state-of-the-art methods.

Collins & Postal (2014) argue that English NPIs have two distinct syntactic structures: a unary NEG structure and a binary NEG structure. They suggest that this distinction is generally valid for natural languages. This formal difference was taken to reconstruct the common distinction in NPI studies between strong and weak NPIs. The present analysis of Ewe NPIs seeks to provide cross-linguistic support for this dual conception of NPIs by showing that the ke-NPIs in this language are all properly analyzed exclusively as unary NEG structures.

By weakening the neutral element condition of semiuninorms, we introduce a new concept called weak-neutral semiuninorms (shortly, wn-semiuninorms). After analyzing their structure, several classes of wn-semiuninorms are presented and discussed. Particularly, based on a kind of monotone unary functions which are not necessarily continuous and strictly monotone, we introduce representable wn-semiuninorms and discuss some of their properties in detail. We show that there is no idempotent proper wn-semiuninorm. Each representable wn-semiuninorm is Archimidean but not strictly monotone, and its additive generator is unique up to a positive multiplicative constant under some conditions. In the discussion about the representable wn-semiuninorms, we also characterize the solutions to a class of Cauchy functional equations on a restricted domain.

This paper provides a comparison between methods used to represent unary, binary and n-ary relations in the relational database (RDB) and object-oriented database (OODB) models and the association-oriented database (AODB) model proposed in terms of their unambiguity. We have elaborated upon the RDB, OODB and AODB models perceived from the perspective of the categories applied to define them. What has been discussed is a number of solutions assuming the form of schemes for the AODB model. We substantiate that those solutions have unequivocally met the conditions of relations of any chosen arity and multiplicity, at the same time keeping the notation concise, unambiguous and considerably expressive.

First-order expressive capabilities allow Bayesian networks (BNs) to model problem domains where the number of entities, their attributes, and their relationships can vary significantly between model instantiations. First-order BNs are well-suited for capturing knowledge representation dependencies, but literature on design patterns specific to first-order BNs is few and scattered. To identify useful patterns, we investigated the range of dependency models between combinations of random variables (RVs) that represent unary attributes, functional relationships, and binary predicate relationships. We found eight major patterns, grouped into three categories, that cover a significant number of first-order BN situations. Selection behavior occurs in six patterns, where a relationship/attribute identifies which entities in a second relationship/attribute are applicable. In other cases, certain kinds of embedded dependencies based on semantic meaning are exploited. A significant contribution of our patterns is that they describe various behaviors used to establish the RV’s local probability distribution. Taken together, the patterns form a modeling framework that provides significant insight into first-order expressive BNs and can reduce efforts in developing such models. To the best of our knowledge, there are no comprehensive published accounts of such patterns.

This paper is about learning word representations using grammatical type information. We use the syntactic types of Combinatory Categorial Grammar to develop multilinear representations, i.e. maps with n arguments, for words with different functional types. The multilinear maps of words compose with each other to form sentence representations. We extend the skipgram algorithm from vectors to multi- linear maps to learn these representations and instantiate it on unary and binary maps for transitive verbs. These are evaluated on verb and sentence similarity and disambiguation tasks and a subset of the SICK relatedness dataset. Our model performs better than previous type- driven models and is competitive with state of the art representation learning methods such as BERT and neural sentence encoders.

We address a salient issue arising in Glockner's two-step methodology for modeling vague quantifiers: the design of quantifier fuzzification mechanisms (QFMs). These are mechanisms to turn formal models of vague quantifiers operating only on crisp arguments (semi-fuzzy quantifiers) into vague quantifiers accepting vague arguments as well (fully-fuzzy quantifiers). We critically examine desiderata formulated by Glockner for QFMs and also point out that previous approaches to quantifier fuzzification largely ignored the question whether the resulting quantifiers can be expressed in suitable extensions of t-norm based fuzzy logics, in particular in Lukasiewicz logic. We also introduce a new family of QFMs, and assess it fares with respect to the mentioned desiderata. We exclusively focus on unary quantifiers, in order to circumvent interference with vagueness related problems arising for all truth functional accounts of quantifiers that refer to more than one argument formula. (C) 2020 Elsevier B.V. All rights reserved.

Weakly-supervised semantic segmentation is a challenging task as no pixel-wise label information is provided for training. Recent methods have exploited classification networks to localize objects by selecting regions with strong response. While such response map provides sparse information, however, there exist strong pairwise relations between pixels in natural images, which can be utilized to propagate the sparse map to a much denser one. In this paper, we propose an iterative algorithm to learn such pairwise relations, which consists of two branches, a unary segmentation network which learns the label probabilities for each pixel, and a pairwise affinity network which learns affinity matrix and refines the probability map generated from the unary network. The refined results by the pairwise network are then used as supervision to train the unary network, and the procedures are conducted iteratively to obtain better segmentation progressively. To learn reliable pixel affinity without accurate annotation, we also propose to mine confident regions. We show that iteratively training this framework is equivalent to optimizing an energy function with convergence to a local minimum. Experimental results on the PASCAL VOC 2012 and COCO datasets demonstrate that the proposed algorithm performs favorably against the state-of-the-art methods., Comment: IJCV 2020

Conventional algorithms for apparent age estimation make a strong assumption that the wisdom of crowds (i.e. the mean value of inconsistently annotated age labels) is superior to any individual. In this paper, we go beyond such an assumption and instead of averaging to remove label uncertainty we cope with label uncertainty in training by introducing a new concept of uncertainty coding. Uncertainty coding encodes multiple unary apparent age labels into a binary vector indicating age range (uncertainty) in the target space. We traverse through convolutional features and architecture to learn deep uncertainty mapping, whose predicted codes as mid-level features are fed into the second layer regressor that outputs a target prediction. We conduct experiments on the ChaLearn and FG-NET benchmarks to demonstrate superior performance of the proposed deep uncertainty coding to the state-of-the-arts.

In his 1974 paper “Popper’s qualitative theory of verisimilitude” published in the British Journal for the Philosophy of Science David Miller gave his so called ‘Weather Example’ to argue that the Hamming distance between constituents is flawed as a measure of proximity to truth since the former is not, unlike the latter, translation invariant. In this present paper we generalise David Miller’s Weather Example in both the unary and polyadic cases, characterising precisely which permutations of constituents/atoms can be effected by translations. In turn this suggests a meta-principle of the rational assignment of subjective probabilities, that rational principles should be preserved under translations, which we formalise and give a particular characterisation of in the context of Unary Pure Inductive Logic.

With the rapid growth of various types of multimodal data, cross-modal deep hashing has received broad attention for solving cross-modal retrieval problems efficiently. Most cross-modal hashing methods follow the traditional supervised hashing framework in which the $O(n^2)$ data pairs and $O(n^3)$ data triplets are generated for training, but the training procedure is less efficient because the complexity is high for large-scale dataset. To address these issues, we propose a novel and efficient cross-modal hashing algorithm in which the unary loss is introduced. First of all, We introduce the Cross-Modal Unary Loss (CMUL) with $O(n)$ complexity to bridge the traditional triplet loss and classification-based unary loss. A more accurate bound of the triplet loss for structured multilabel data is also proposed in CMUL. Second, we propose the novel Joint Cluster Cross-Modal Hashing (JCCH) algorithm for efficient hash learning, in which the CMUL is involved. The resultant hashcodes form several clusters in which the hashcodes in the same cluster share similar semantic information, and the heterogeneity gap on different modalities is diminished by sharing the clusters. The proposed algorithm is able to be applied to various types of data, and experiments on large-scale datasets show that the proposed method is superior over or comparable with state-of-the-art cross-modal hashing methods, and training with the proposed method is more efficient than others.

A new deep architecture MSPN is proposed for image segmentation.Multiscale unary potentials are used to model image spatial layouts.A superpixel-based refinement method is used to improve the parsing results. Semantic image segmentation is challenging due to the large intra-class variations and the complex spatial layouts inside natural scenes. This paper investigates this problem by designing a new deep architecture, called multiscale sum-product network (MSPN), which utilizes multiscale unary potentials as the inputs and models the spatial layouts of image content in a hierarchical manner. That is, the proposed MSPN models the joint distribution of multiscale unary potentials and object classes instead of single unary potentials in popular settings. Besides, MSPN characterizes scene spatial layouts in a fine-to-coarse manner to enforce the consistency in labeling. Multiscale unary potentials at different scales can thus help overcome semantic ambiguities caused by only evaluating single local regions, while long-range spatial correlations can further refine image labeling. In addition, higher orders are able to pose the constraints among labels. By this way, multi-scale unary potentials, long-range spatial correlations, higher-order priors are well modeled under the uniform framework in MSPN. We conduct experiments on two challenging benchmarks consisting of the MSRC-21 dataset and the SIFT FLOW dataset. The results demonstrate the superior performance of our method comparing with the previous graphical models for understanding scene images.

Current and near-term implantable prosthetic vision systems offer the potential to restore some visual function, but suffer from limited resolution and dynamic range of induced visual percepts. This can make navigating complex environments difficult for users. We introduce semantic labeling as a technique to improve navigation outcomes for prosthetic vision users. We produce a novel egocentric vision dataset to demonstrate how semantic labeling can be applied to this problem. We also improve the speed of semantic labeling with sparse computation of unary potentials, enabling its use in real-time wearable assistive devices. We use simulated prosthetic vision to demonstrate the results of our technique. Our approach allows a prosthetic vision system to selectively highlight specific classes of objects in the user’s field of view, improving the user’s situational awareness.

A modification of the conventional bag of words model that can take into account the structural features of text documents in their classification (categorization) using machine learning techniques is studied. It is proposed to describe these features by relations on the set of certain lexemes and use the relation names, along with the lexeme names, as features. This is a distinction from the conventional model in which only unary relations are used. The effectiveness of the proposed machine learning techniques is analyzed using computer experiments on the class of the Reuters-21578 collection with eight known classifiers. It is shown that it is reasonable to apply the proposed models to classify documents using simple classifiers.

We propose a novel unary spiking circuit for a serial multiplier with variable dendritic delays. Serial multipliers commonly use the soma model for the arithmetic operation. The structure of the serial multiplier and the efficient implementation of the dendritic delays on customized neuromorphic hardware are the major contributions of this work. The design of the multiplier was inspired by the biological processes of dendrites, which use feedback connections and dendritic growth to synchronize the neural processing performed by the soma. The multiplier eliminates complex rules by adopting the soma model with dendritic connectivity configurations, increasing the processing speed compared with previously reported solutions based on Spiking Neural Networks.

For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NP-hard. But the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) is a long- standing open problem. We show in this paper that the problem is unary NP-hard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NP-hard. As a consequence, some multi-agent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NP-hard.

Within the framework of (Unary) Pure Inductive Logic we investigate four possible formulations of a probabilistic principle of analogy based on a template considered by Paul Bartha in the Stanford Encyclopedia of Philosophy [1] and give some characterizations of the probability functions which satisfy them. In addition we investigate an alternative interpretation of analogical support, also considered by Bartha, based not on the enhancement of probability but on the creation of possibility.