OpenRaiser/Intern-Atlas huggingface dataset:
HEp-2 Cell Classification via Fusing Texture and Shape Information
Venue: arXiv cs.CV 2015
Year: 2015

Indirect Immunofluorescence (IIF) HEp-2 cell image is an effective evidence for diagnosis of autoimmune diseases. Recently computer-aided diagnosis of autoimmune diseases by IIF HEp-2 cell classification has attracted great attention. However the HEp-2 cell classification task is quite challenging due to large intra-class variation and small between-class variation. In this paper we propose an effective and efficient approach for the automatic classification of IIF HEp-2 cell image by fusing multi-resolution texture information and richer shape information. To be specific, we propose to: a) capture the multi-resolution texture information by a novel Pairwise Rotation Invariant Co-occurrence of Local Gabor Binary Pattern (PRICoLGBP) descriptor, b) depict the richer shape information by using an Improved Fisher Vector (IFV) model with RootSIFT features which are sampled from large image patches in multiple scales, and c) combine them properly. We evaluate systematically the proposed approach on the IEEE International Conference on Pattern Recognition (ICPR) 2012, IEEE International Conference on Image Processing (ICIP) 2013 and ICPR 2014 contest data sets. The experimental results for the proposed methods significantly outperform the winners of ICPR 2012 and ICIP 2013 contest, and achieve comparable performance with the winner of the newly released ICPR 2014 contest.
Type Classes for Lightweight Substructural Types
Venue: arXiv cs.PL 2015
Year: 2015

Linear and substructural types are powerful tools, but adding them to standard functional programming languages often means introducing extra annotations and typing machinery. We propose a lightweight substructural type system design that recasts the structural rules of weakening and contraction as type classes; we demonstrate this design in a prototype language, Clamp. Clamp supports polymorphic substructural types as well as an expressive system of mutable references. At the same time, it adds little additional overhead to a standard Damas-Hindley-Milner type system enriched with type classes. We have established type safety for the core model and implemented a type checker with type inference in Haskell.
Cryptanalysis of A Secure Remote User Authentication Scheme Using Smart Cards
Venue: arXiv cs.CR 2015
Year: 2015

Smart card based authentication schemes are used in various fields like e-banking, e-commerce, wireless sensor networks, medical system and so on to authenticate the both remote user and the application server during the communication via internet. Recently, Karuppiah and Saravanan proposed an authentication scheme which is based on password and one-way cryptographic hash function. They have used a secure identity mechanism i.e., users' and server's identity are not public. Thus, the user and the server do not send their identity directly to each other during communications. In this paper, we have found out that their scheme does not overcome the reply attack and also there is a fault in the login phase, which makes their scheme is not perfect for practical use.
Optimal non-adaptive solutions for the counterfeit coin problem
Venue: arXiv cs.DM 2015
Year: 2015

We give optimal solutions to all versions of the popular counterfeit coin problem obtained by varying whether (i) we know if the counterfeit coin is heavier or lighter than the genuine ones, (ii) we know if the counterfeit coin exists, (iii) we have access to additional genuine coins, and (iv) we need to determine if the counterfeit coin is heavier or lighter than the genuine ones. Moreover, our solutions are non-adaptive.
Block-Level Unitary Query: Incorporating Orthogonal-like Space-time Code with Query Diversity for MIMO Backscatter RFID
Venue: arXiv cs.IT 2015
Year: 2015

Because of the emerging field of Internet of Things (IoT), future backscatter RFID is required to be more reliable and data intensive. Motivated by this, orthogonal space-time block code (OSTBC), which is very successful in mobile communications for its low complexity and high performance, has already been investigated for backscatter RFID. On the other hand, a recently proposed scheme called unitary query was shown to be able to considerably improve the reliability of backscatter radio by exploiting query diversity. Therefore incorporating the classical OSTBC (at the tag end) with the recently proposed unitary query (at the query end) seems to be promising. However, in this paper, we show that simple, direct employment of OSTBC together with unitary query incurs a linear decoding problem and eventually leads to a severe performance degradation. As a re-design of the recently proposed unitary query and the classical OSTBC specifically for MIMO backscatter RFID, we present a BUTQ-mOSTBC design pair idea by proposing the block-level unitary query (BUTQ) at the query end and the corresponding modified OSTBC (mOSTBC) at the tag end. The proposed BUTQ-mOSTBC can resolve the linear decoding problem, keep the simplicity and high performance properties of the classical OSTBC, and achieve the query diversity for the $M \times L \times N$ MIMO backscatter RFID channel.
Context Tricks for Cheap Semantic Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Accurate semantic labeling of image pixels is difficult because intra-class variability is often greater than inter-class variability. In turn, fast semantic segmentation is hard because accurate models are usually too complicated to also run quickly at test-time. Our experience with building and running semantic segmentation systems has also shown a reasonably obvious bottleneck on model complexity, imposed by small training datasets. We therefore propose two simple complementary strategies that leverage context to give better semantic segmentation, while scaling up or down to train on different-sized datasets. As easy modifications for existing semantic segmentation algorithms, we introduce Decorrelated Semantic Texton Forests, and the Context Sensitive Image Level Prior. The proposed modifications are tested using a Semantic Texton Forest (STF) system, and the modifications are validated on two standard benchmark datasets, MSRC-21 and PascalVOC-2010. In Python based comparisons, our system is insignificantly slower than STF at test-time, yet produces superior semantic segmentations overall, with just push-button training.
Design of a Framework to Facilitate Decisions Using Information Fusion
Venue: arXiv cs.AI 2015
Year: 2015

Information fusion is an advanced research area which can assist decision makers in enhancing their decisions. This paper aims at designing a new multi-layer framework that can support the process of performing decisions from the obtained beliefs using information fusion. Since it is not an easy task to cross the gap between computed beliefs of certain hypothesis and decisions, the proposed framework consists of the following layers in order to provide a suitable architecture (ordered bottom up): 1. A layer for combination of basic belief assignments using an information fusion approach. Such approach exploits Dezert-Smarandache Theory, DSmT, and proportional conflict redistribution to provide more realistic final beliefs. 2. A layer for computation of pignistic probability of the underlying propositions from the corresponding final beliefs. 3. A layer for performing probabilistic reasoning using a Bayesian network that can obtain the probable reason of a proposition from its pignistic probability. 4. Ranking the system decisions is ultimately used to support decision making. A case study has been accomplished at various operational conditions in order to prove the concept, in addition it pointed out that: 1. The use of DSmT for information fusion yields not only more realistic beliefs but also reliable pignistic probabilities for the underlying propositions. 2. Exploiting the pignistic probability for the integration of the information fusion with the Bayesian network provides probabilistic inference and enable decision making on the basis of both belief based probabilities for the underlying propositions and Bayesian based probabilities for the corresponding reasons. A comparative study of the proposed framework with respect to other information fusion systems confirms its superiority to support decision making.
Real time clustering of time series using triangular potentials
Venue: arXiv cs.LG 2015
Year: 2015

Motivated by the problem of computing investment portfolio weightings we investigate various methods of clustering as alternatives to traditional mean-variance approaches. Such methods can have significant benefits from a practical point of view since they remove the need to invert a sample covariance matrix, which can suffer from estimation error and will almost certainly be non-stationary. The general idea is to find groups of assets which share similar return characteristics over time and treat each group as a single composite asset. We then apply inverse volatility weightings to these new composite assets. In the course of our investigation we devise a method of clustering based on triangular potentials and we present associated theoretical results as well as various examples based on synthetic data.
Emergent Behavior in Cybersecurity
Venue: arXiv cs.CR 2015
Year: 2015

We argue that emergent behavior is inherent to cybersecurity.
Query Expansion Strategy based on Pseudo Relevance Feedback and Term Weight Scheme for Monolingual Retrieval
Venue: arXiv cs.IR 2015
Year: 2015

Query Expansion using Pseudo Relevance Feedback is a useful and a popular technique for reformulating the query. In our proposed query expansion method, we assume that relevant information can be found within a document near the central idea. The document is normally divided into sections, paragraphs and lines. The proposed method tries to extract keywords that are closer to the central theme of the document. The expansion terms are obtained by equi-frequency partition of the documents obtained from pseudo relevance feedback and by using tf-idf scores. The idf factor is calculated for number of partitions in documents. The group of words for query expansion is selected using the following approaches: the highest score, average score and a group of words that has maximum number of keywords. As each query behaved differently for different methods, the effect of these methods in selecting the words for query expansion is investigated. From this initial study, we extend the experiment to develop a rule-based statistical model that automatically selects the best group of words incorporating the tf-idf scoring and the 3 approaches explained here, in the future. The experiments were performed on FIRE 2011 Adhoc Hindi and English test collections on 50 queries each, using Terrier as retrieval engine.
IAT - Image Annotation Tool: Manual
Venue: arXiv cs.CV 2015
Year: 2015

The annotation of image and video data of large datasets is a fundamental task in multimedia information retrieval and computer vision applications. In order to support the users during the image and video annotation process, several software tools have been developed to provide them with a graphical environment which helps drawing object contours, handling tracking information and specifying object metadata. Here we introduce a preliminary version of the image annotation tools developed at the Imaging and Vision Laboratory.
Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
Venue: arXiv cs.AI 2015
Year: 2015

Recent years have seen the development of methods for multiagent planning under uncertainty that scale to tens or even hundreds of agents. However, most of these methods either make restrictive assumptions on the problem domain, or provide approximate solutions without any guarantees on quality. Methods in the former category typically build on heuristic search using upper bounds on the value function. Unfortunately, no techniques exist to compute such upper bounds for problems with non-factored value functions. To allow for meaningful benchmarking through measurable quality guarantees on a very general class of problems, this paper introduces a family of influence-optimistic upper bounds for factored decentralized partially observable Markov decision processes (Dec-POMDPs) that do not have factored value functions. Intuitively, we derive bounds on very large multiagent planning problems by subdividing them in sub-problems, and at each of these sub-problems making optimistic assumptions with respect to the influence that will be exerted by the rest of the system. We numerically compare the different upper bounds and demonstrate how we can achieve a non-trivial guarantee that a heuristic solution for problems with hundreds of agents is close to optimal. Furthermore, we provide evidence that the upper bounds may improve the effectiveness of heuristic influence search, and discuss further potential applications to multiagent planning.
Lower Bounds for the Graph Homomorphism Problem
Venue: arXiv cs.DS 2015
Year: 2015

The graph homomorphism problem (HOM) asks whether the vertices of a given $n$-vertex graph $G$ can be mapped to the vertices of a given $h$-vertex graph $H$ such that each edge of $G$ is mapped to an edge of $H$. The problem generalizes the graph coloring problem and at the same time can be viewed as a special case of the $2$-CSP problem. In this paper, we prove several lower bound for HOM under the Exponential Time Hypothesis (ETH) assumption. The main result is a lower bound $2^{Ω\left( \frac{n \log h}{\log \log h}\right)}$. This rules out the existence of a single-exponential algorithm and shows that the trivial upper bound $2^{{\mathcal O}(n\log{h})}$ is almost asymptotically tight. We also investigate what properties of graphs $G$ and $H$ make it difficult to solve HOM$(G,H)$. An easy observation is that an ${\mathcal O}(h^n)$ upper bound can be improved to ${\mathcal O}(h^{\operatorname{vc}(G)})$ where $\operatorname{vc}(G)$ is the minimum size of a vertex cover of $G$. The second lower bound $h^{Ω(\operatorname{vc}(G))}$ shows that the upper bound is asymptotically tight. As to the properties of the "right-hand side" graph $H$, it is known that HOM$(G,H)$ can be solved in time $(f(Δ(H)))^n$ and $(f(\operatorname{tw}(H)))^n$ where $Δ(H)$ is the maximum degree of $H$ and $\operatorname{tw}(H)$ is the treewidth of $H$. This gives single-exponential algorithms for graphs of bounded maximum degree or bounded treewidth. Since the chromatic number $χ(H)$ does not exceed $\operatorname{tw}(H)$ and $Δ(H)+1$, it is natural to ask whether similar upper bounds with respect to $χ(H)$ can be obtained. We provide a negative answer to this question by establishing a lower bound $(f(χ(H)))^n$ for any function $f$. We also observe that similar lower bounds can be obtained for locally injective homomorphisms.
NRCL - A Model Building Approach to the Bernays-Schönfinkel Fragment (Full Paper)
Venue: arXiv cs.LO 2015
Year: 2015

We combine constrained literals for model representation with key concepts from first-order superposition and propositional conflict-driven clause learning (CDCL) to create the new calculus Non-Redundant Clause Learning (NRCL) deciding the Bernays-Schönfinkel fragment. Our calculus uses first-order literals constrained by disequations between tuples of terms for compact model representation. From superposition, NRCL inherits the abstract redundancy criterion and the monotone model operator. CDCL adds the dynamic, conflict-driven search for an atom ordering inducing a model. As a result, in NRCL a false clause can be found effectively modulo the current model candidate. It guides the derivation of a first-order ordered resolvent that is never redundant. Similar to 1UIP-learning in CDCL, the learned resolvent induces backtracking and, by blocking the previous conflict state via propagation, it enforces progress towards finding a model or a refutation. The non-redundancy result also implies that only finitely many clauses can be generated by NRCL on the Bernays-Schönfinkel fragment, which serves as an argument for termination.
A Secret Common Information Duality for Tripartite Noisy Correlations
Venue: arXiv cs.IT 2015
Year: 2015

We explore the duality between the simulation and extraction of secret correlations in light of a similar well-known operational duality between the two notions of common information due to Wyner, and Gács and Körner. For the inverse problem of simulating a tripartite noisy correlation from noiseless secret key and unlimited public communication, we show that Winter's (2005) result for the key cost in terms of a conditional version of Wyner's common information can be simply reexpressed in terms of the existence of a bipartite protocol monotone. For the forward problem of key distillation from noisy correlations, we construct simple distributions for which the conditional Gács and Körner common information achieves a tight bound on the secret key rate. We conjecture that this holds in general for non-communicative key agreement models. We also comment on the interconvertibility of secret correlations under local operations and public communication.
Randomized Assignment of Jobs to Servers in Heterogeneous Clusters of Shared Servers for Low Delay
Venue: arXiv cs.DC 2015
Year: 2015

We consider the job assignment problem in a multi-server system consisting of $N$ parallel processor sharing servers, categorized into $M$ ($\ll N$) different types according to their processing capacity or speed. Jobs of random sizes arrive at the system according to a Poisson process with rate $N λ$. Upon each arrival, a small number of servers from each type is sampled uniformly at random. The job is then assigned to one of the sampled servers based on a selection rule. We propose two schemes, each corresponding to a specific selection rule that aims at reducing the mean sojourn time of jobs in the system. We first show that both methods achieve the maximal stability region. We then analyze the system operating under the proposed schemes as $N \to \infty$ which corresponds to the mean field. Our results show that asymptotic independence among servers holds even when $M$ is finite and exchangeability holds only within servers of the same type. We further establish the existence and uniqueness of stationary solution of the mean field and show that the tail distribution of server occupancy decays doubly exponentially for each server type. When the estimates of arrival rates are not available, the proposed schemes offer simpler alternatives to achieving lower mean sojourn time of jobs, as shown by our numerical studies.
Time-Approximation Trade-offs for Inapproximable Problems
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any $r(n)$, a simple, known scheme gives an approximation ratio of $r$ in time roughly $r^{n/r}$. We show that, for most values of $r$, if this running time could be significantly improved the ETH would fail. For Max Minimal Vertex Cover we give a non-trivial $\sqrt{r}$-approximation in time $2^{n/r}$. We match this with a similarly tight result. We also give a $\log r$-approximation for Min ATSP in time $2^{n/r}$ and an $r$-approximation for Max Grundy Coloring in time $r^{n/r}$. Furthermore, we show that Min Set Cover exhibits a curious behavior in this super-polynomial setting: for any $δ> 0$ it admits an $m^δ$-approximation, where $m$ is the number of sets, in just quasi-polynomial time. We observe that if such ratios could be achieved in polynomial time, the ETH or the Projection Games Conjecture would fail.
A provably convergent alternating minimization method for mean field inference
Venue: arXiv cs.LG 2015
Year: 2015

Mean-Field is an efficient way to approximate a posterior distribution in complex graphical models and constitutes the most popular class of Bayesian variational approximation methods. In most applications, the mean field distribution parameters are computed using an alternate coordinate minimization. However, the convergence properties of this algorithm remain unclear. In this paper, we show how, by adding an appropriate penalization term, we can guarantee convergence to a critical point, while keeping a closed form update at each step. A convergence rate estimate can also be derived based on recent results in non-convex optimization.
Automated Reasoning for Robot Ethics
Venue: arXiv cs.AI 2015
Year: 2015

Deontic logic is a very well researched branch of mathematical logic and philosophy. Various kinds of deontic logics are considered for different application domains like argumentation theory, legal reasoning, and acts in multi-agent systems. In this paper, we show how standard deontic logic can be used to model ethical codes for multi-agent systems. Furthermore we show how Hyper, a high performance theorem prover, can be used to prove properties of these ethical codes.
An Approach For Transforming of Relational Databases to OWL Ontology
Venue: arXiv cs.DB 2015
Year: 2015

Rapid growth of documents, web pages, and other types of text content is a huge challenge for the modern content management systems. One of the problems in the areas of information storage and retrieval is the lacking of semantic data. Ontologies can present knowledge in sharable and repeatedly usable manner and provide an effective way to reduce the data volume overhead by encoding the structure of a particular domain. Metadata in relational databases can be used to extract ontology from database in a special domain. According to solve the problem of sharing and reusing of data, approaches based on transforming relational database to ontology are proposed. In this paper we propose a method for automatic ontology construction based on relational database. Mining and obtaining further components from relational database leads to obtain knowledge with high semantic power and more expressiveness. Triggers are one of the database components which could be transformed to the ontology model and increase the amount of power and expressiveness of knowledge by presenting part of the knowledge dynamically
A Flexible Implementation of a Matrix Laurent Series-Based 16-Point Fast Fourier and Hartley Transforms
Venue: arXiv cs.NA 2015
Year: 2015

This paper describes a flexible architecture for implementing a new fast computation of the discrete Fourier and Hartley transforms, which is based on a matrix Laurent series. The device calculates the transforms based on a single bit selection operator. The hardware structure and synthesis are presented, which handled a 16-point fast transform in 65 nsec, with a Xilinx SPARTAN 3E device.
Fixed-parameter Tractable Distances to Sparse Graph Classes
Venue: arXiv cs.DS 2015
Year: 2015

We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.