OpenRaiser/Intern-Atlas huggingface dataset:
Prospective Study for Semantic Inter-Media Fusion in Content-Based Medical Image Retrieval
Venue: arXiv cs.IR 2008
Year: 2008

One important challenge in modern Content-Based Medical Image Retrieval (CBMIR) approaches is represented by the semantic gap, related to the complexity of the medical knowledge. Among the methods that are able to close this gap in CBMIR, the use of medical thesauri/ontologies has interesting perspectives due to the possibility of accessing on-line updated relevant webservices and to extract real-time medical semantic structured information. The CBMIR approach proposed in this paper uses the Unified Medical Language System's (UMLS) Metathesaurus to perform a semantic indexing and fusion of medical media. This fusion operates before the query processing (retrieval) and works at an UMLS-compliant conceptual indexing level. Our purpose is to study various techniques related to semantic data alignment, preprocessing, fusion, clustering and retrieval, by evaluating the various techniques and highlighting future research directions. The alignment and the preprocessing are based on partial text/image retrieval feedback and on the data structure. We analyze various probabilistic, fuzzy and evidence-based approaches for the fusion process and different similarity functions for the retrieval process. All the proposed methods are evaluated on the Cross Language Evaluation Forum's (CLEF) medical image retrieval benchmark, by focusing also on a more homogeneous component medical image database: the Pathology Education Instructional Resource (PEIR).
Secrecy Capacity of a Class of Broadcast Channels with an Eavesdropper
Venue: arXiv cs.IT 2008
Year: 2008

We study the security of communication between a single transmitter and multiple receivers in a broadcast channel in the presence of an eavesdropper. We consider several special classes of channels. As the first model, we consider the degraded multi-receiver wiretap channel where the legitimate receivers exhibit a degradedness order while the eavesdropper is more noisy with respect to all legitimate receivers. We establish the secrecy capacity region of this channel model. Secondly, we consider the parallel multi-receiver wiretap channel with a less noisiness order in each sub-channel, where this order is not necessarily the same for all sub-channels. We establish the common message secrecy capacity and sum secrecy capacity of this channel. Thirdly, we study a special class of degraded parallel multi-receiver wiretap channels and provide a stronger result. In particular, we study the case with two sub-channels two users and one eavesdropper, where there is a degradedness order in each sub-channel such that in the first (resp. second) sub-channel the second (resp. first) receiver is degraded with respect to the first (resp. second) receiver, while the eavesdropper is degraded with respect to both legitimate receivers in both sub-channels. We determine the secrecy capacity region of this channel. Finally, we focus on a variant of this previous channel model where the transmitter can use only one of the sub-channels at any time. We characterize the secrecy capacity region of this channel as well.
Trembling hand perfection is NP-hard
Venue: arXiv cs.GT 2008
Year: 2008

It is NP-hard to decide if a given pure-strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect.
A new Contrast Based Image Fusion using Wavelet Packets
Venue: arXiv cs.IT 2008
Year: 2008

Image Fusion, a technique which combines complimentary information from different images of the same scene so that the fused image is more suitable for segmentation, feature extraction, object recognition and Human Visual System. In this paper, a simple yet efficient algorithm is presented based on contrast using wavelet packet decomposition. First, all the source images are decomposed into low and high frequency sub-bands and then fusion of high frequency sub-bands is done by the means of Directive Contrast. Now, inverse wavelet packet transform is performed to reconstruct the fused image. The performance of the algorithm is carried out by the comparison made between proposed and existing algorithm.
Adversarial Scheduling in Evolutionary Game Dynamics
Venue: arXiv cs.DM 2008
Year: 2008

Consider a system in which players at nodes of an underlying graph G repeatedly play Prisoner's Dilemma against their neighbors. The players adapt their strategies based on the past behavior of their opponents by applying the so-called win-stay lose-shift strategy. This dynamics has been studied in (Kittock 94), (Dyer et al. 2002), (Mossel and Roch, 2006). With random scheduling, starting from any initial configuration with high probability the system reaches the unique fixed point in which all players cooperate. This paper investigates the validity of this result under various classes of adversarial schedulers. Our results can be sumarized as follows: 1. An adversarial scheduler that can select both participants to the game can preclude the system from reaching the unique fixed point on most graph topologies. 2. A nonadaptive scheduler that is only allowed to choose one of the participants is no more powerful than a random scheduler. With this restriction even an adaptive scheduler is not significantly more powerful than the random scheduler, provided it is "reasonably fair". The results exemplify the adversarial scheduling approach we propose as a foundational basis for the generative approach to social science (Epstein 2007).
Decomposition Principles and Online Learning in Cross-Layer Optimization for Delay-Sensitive Applications
Venue: arXiv cs.MM 2008
Year: 2008

In this paper, we propose a general cross-layer optimization framework in which we explicitly consider both the heterogeneous and dynamically changing characteristics of delay-sensitive applications and the underlying time-varying network conditions. We consider both the independently decodable data units (DUs, e.g. packets) and the interdependent DUs whose dependencies are captured by a directed acyclic graph (DAG). We first formulate the cross-layer design as a non-linear constrained optimization problem by assuming complete knowledge of the application characteristics and the underlying network conditions. The constrained cross-layer optimization is decomposed into several cross-layer optimization subproblems for each DU and two master problems. The proposed decomposition method determines the necessary message exchanges between layers for achieving the optimal cross-layer solution. However, the attributes (e.g. distortion impact, delay deadline etc) of future DUs as well as the network conditions are often unknown in the considered real-time applications. The impact of current cross-layer actions on the future DUs can be characterized by a state-value function in the Markov decision process (MDP) framework. Based on the dynamic programming solution to the MDP, we develop a low-complexity cross-layer optimization algorithm using online learning for each DU transmission. This online algorithm can be implemented in real-time in order to cope with unknown source characteristics, network dynamics and resource constraints. Our numerical results demonstrate the efficiency of the proposed online algorithm.
Analysis of Energy Efficiency in Fading Channels under QoS Constraints
Venue: arXiv cs.IT 2008
Year: 2008

Energy efficiency in fading channels in the presence of Quality of Service (QoS) constraints is studied. Effective capacity, which provides the maximum arrival rate that a wireless channel can sustain while satisfying statistical QoS constraints, is considered. Spectral efficiency--bit energy tradeoff is analyzed in the low-power and wideband regimes by employing the effective capacity formulation, rather than the Shannon capacity. Through this analysis, energy requirements under QoS constraints are identified. The analysis is conducted under two assumptions: perfect channel side information (CSI) available only at the receiver and perfect CSI available at both the receiver and transmitter. In particular, it is shown in the low-power regime that the minimum bit energy required under QoS constraints is the same as that attained when there are no such limitations. However, this performance is achieved as the transmitted power vanishes. Through the wideband slope analysis, the increased energy requirements at low but nonzero power levels in the presence of QoS constraints are determined. A similar analysis is also conducted in the wideband regime, and minimum bit energy and wideband slope expressions are obtained. In this regime, the required bit energy levels are found to be strictly greater than those achieved when Shannon capacity is considered. Overall, a characterization of the energy-bandwidth-delay tradeoff is provided.
A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing
Venue: arXiv cs.DM 2008
Year: 2008

In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.
On the Energy Efficiency of Orthogonal Signaling
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, transmission over the additive white Gaussian noise (AWGN) channel, and coherent and noncoherent fading channels using M-ary orthogonal frequency-shift keying (FSK) or on-off frequency-shift keying (OOFSK) is considered. The receiver is assumed to perform hard-decision detection. In this setting, energy required to reliably send one bit of information is investigated. It is shown that for fixed M and duty cycle, bit energy requirements grow without bound as the signal-to-noise ratio (SNR) vanishes. The minimum bit energy values are numerically obtained for different values of M and the duty cycle. The impact of fading on the energy efficiency is identified. Requirements to approach the minimum bit energy of -1.59 dB are determined.
Dependence Balance Based Outer Bounds for Gaussian Networks with Cooperation and Feedback
Venue: arXiv cs.IT 2008
Year: 2008

We obtain new outer bounds on the capacity regions of the two-user multiple access channel with generalized feedback (MAC-GF) and the two-user interference channel with generalized feedback (IC-GF). These outer bounds are based on the idea of dependence balance which was proposed by Hekstra and Willems [1]. To illustrate the usefulness of our outer bounds, we investigate three different channel models. We first consider a Gaussian MAC with noisy feedback (MAC-NF), where transmitter $k$, $k=1,2$, receives a feedback $Y_{F_{k}}$, which is the channel output $Y$ corrupted with additive white Gaussian noise $Z_{k}$. As the feedback noise variances become large, one would expect the feedback to become useless, which is not reflected by the cut-set bound. We demonstrate that our outer bound improves upon the cut-set bound for all non-zero values of the feedback noise variances. Moreover, in the limit as $σ_{Z_{k}}^{2}\to \infty$, $k=1,2$, our outer bound collapses to the capacity region of the Gaussian MAC without feedback. Secondly, we investigate a Gaussian MAC with user-cooperation (MAC-UC), where each transmitter receives an additive white Gaussian noise corrupted version of the channel input of the other transmitter [2]. For this channel model, the cut-set bound is sensitive to the cooperation noises, but not sensitive enough. For all non-zero values of cooperation noise variances, our outer bound strictly improves upon the cut-set outer bound. Thirdly, we investigate a Gaussian IC with user-cooperation (IC-UC). For this channel model, the cut-set bound is again sensitive to cooperation noise variances but not sensitive enough. We demonstrate that our outer bound strictly improves upon the cut-set bound for all non-zero values of cooperation noise variances.
Dynamic Complexity of Formal Languages
Venue: arXiv cs.CC 2008
Year: 2008

The paper investigates the power of the dynamic complexity classes DynFO, DynQF and DynPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DynPROP exactly are the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, it is shown that any context-free language can be maintained in DynFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DynQF. Furthermore, the dynamic complexity of regular tree languages is investigated and some results concerning arbitrary structures are obtained: there exist first-order definable properties which are not maintainable in DynPROP. On the other hand any existential first-order property can be maintained in DynQF when allowing precomputation.
Decomposition of Decidable First-Order Logics over Integers and Reals
Venue: arXiv cs.LO 2008
Year: 2008

We tackle the issue of representing infinite sets of real- valued vectors. This paper introduces an operator for combining integer and real sets. Using this operator, we decompose three well-known logics extending Presburger with reals. Our decomposition splits a logic into two parts : one integer, and one decimal (i.e. on the interval [0,1]). We also give a basis for an implementation of our representation.
Interoperability between Heterogeneous Federation Architectures: Illustration with SAML and WS-Federation
Venue: arXiv cs.CR 2008
Year: 2008

Digital identity management intra and inter information systems, and, service oriented architectures, are the roots of identity federation. This kind of security architectures aims at enabling information system interoperability. Existing architectures, however, do not consider interoperability of heterogeneous federation architectures, which rely on different federation protocols.In this paper, we try to initiate an in-depth reflection on this issue, through the comparison of two main federation architecture specifications: SAML and WS-Federation. We firstly propose an overall outline of identity federation. We furthermore address the issue of interoperability for federation architectures using a different federation protocol. Afterwards, we compare SAML and WS-Federation. Eventually, we define the ways of convergence, and therefore, of interoperability.
Unfolding Convex Polyhedra via Quasigeodesic Star Unfoldings
Venue: arXiv cs.CG 2008
Year: 2008

We extend the notion of a star unfolding to be based on a simple quasigeodesic loop Q rather than on a point. This gives a new general method to unfold the surface of any convex polyhedron P to a simple, planar polygon: shortest paths from all vertices of P to Q are cut, and all but one segment of Q is cut.
Completeness for Flat Modal Fixpoint Logics
Venue: arXiv cs.LO 2008
Year: 2008

This paper exhibits a general and uniform method to prove completeness for certain modal fixpoint logics. Given a set Γof modal formulas of the form γ(x, p1, . . ., pn), where x occurs only positively in γ, the language L\sharp (Γ) is obtained by adding to the language of polymodal logic a connective \sharp\_γfor each γε. The term \sharp\_γ(\varphi1, . . ., \varphin) is meant to be interpreted as the least fixed point of the functional interpretation of the term γ(x, φ1, . . ., φn). We consider the following problem: given Γ, construct an axiom system which is sound and complete with respect to the concrete interpretation of the language L\sharp (Γ) on Kripke frames. We prove two results that solve this problem. First, let K\sharp (Γ) be the logic obtained from the basic polymodal K by adding a Kozen-Park style fixpoint axiom and a least fixpoint rule, for each fixpoint connective \sharp\_γ. Provided that each indexing formula γsatisfies the syntactic criterion of being untied in x, we prove this axiom system to be complete. Second, addressing the general case, we prove the soundness and completeness of an extension K+ (Γ) of K\_\sharp (Γ). This extension is obtained via an effective procedure that, given an indexing formula γas input, returns a finite set of axioms and derivation rules for \sharp\_γ, of size bounded by the length of γ. Thus the axiom system K+ (Γ) is finite whenever Γis finite.
On the Expressive Power of 2-Stack Visibly Pushdown Automata
Venue: arXiv cs.LO 2008
Year: 2008

Visibly pushdown automata are input-driven pushdown automata that recognize some non-regular context-free languages while preserving the nice closure and decidability properties of finite automata. Visibly pushdown automata with multiple stacks have been considered recently by La Torre, Madhusudan, and Parlato, who exploit the concept of visibility further to obtain a rich automata class that can even express properties beyond the class of context-free languages. At the same time, their automata are closed under boolean operations, have a decidable emptiness and inclusion problem, and enjoy a logical characterization in terms of a monadic second-order logic over words with an additional nesting structure. These results require a restricted version of visibly pushdown automata with multiple stacks whose behavior can be split up into a fixed number of phases. In this paper, we consider 2-stack visibly pushdown automata (i.e., visibly pushdown automata with two stacks) in their unrestricted form. We show that they are expressively equivalent to the existential fragment of monadic second-order logic. Furthermore, it turns out that monadic second-order quantifier alternation forms an infinite hierarchy wrt words with multiple nestings. Combining these results, we conclude that 2-stack visibly pushdown automata are not closed under complementation. Finally, we discuss the expressive power of Büchi 2-stack visibly pushdown automata running on infinite (nested) words. Extending the logic by an infinity quantifier, we can likewise establish equivalence to existential monadic second-order logic.
Square Complex Orthogonal Designs with no Zero Entry for any $2^m$ Antennas
Venue: arXiv cs.IT 2008
Year: 2008

Space-time block codes from square complex orthogonal designs (SCOD) have been extensively studied and most of the existing SCODs contain large number of zeros. The zeros in the designs result in high peak-to-average power ratio and also impose a severe constraint on hardware implementation of the code while turning off some of the transmitting antennas whenever a zero is transmitted. Recently, SCODs with no zero entry have been constructed for $2^a$ transmit antennas whenever $a+1$ is a power of 2. Though there exists codes for 4 and 16 transmit antennas with no zero entry, there is no general method of construction which gives codes for any number of transmit antennas. In this paper, we construct SCODs for any power of 2 number of transmit antennas having all its entries non-zero. Simulation results show that the codes constructed in this paper outperform the existing codes for the same number of antennas under peak power constraint while performing the same under average power constraint.
Kalinahia: Considering Quality of Service to Design and Execute Distributed Multimedia Applications
Venue: arXiv cs.MM 2008
Year: 2008

One of the current challenges of Information Systems is to ensure semi-structured data transmission, such as multimedia data, in a distributed and pervasive environment. Information Sytems must then guarantee users a quality of service ensuring data accessibility whatever the hardware and network conditions may be. They must also guarantee information coherence and particularly intelligibility that imposes a personalization of the service. Within this framework, we propose a design method based on original models of multimedia applications and quality of service. We also define a supervision platform Kalinahia using a user centered heuristic allowing us to define at any moment which configuration of software components constitutes the best answers to users' wishes in terms of service.
Pattern Recognition and Memory Mapping using Mirroring Neural Networks
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, we present a new kind of learning implementation to recognize the patterns using the concept of Mirroring Neural Network (MNN) which can extract information from distinct sensory input patterns and perform pattern recognition tasks. It is also capable of being used as an advanced associative memory wherein image data is associated with voice inputs in an unsupervised manner. Since the architecture is hierarchical and modular it has the potential of being used to devise learning engines of ever increasing complexity.
Shape Fitting on Point Sets with Probability Distributions
Venue: arXiv cs.CG 2008
Year: 2008

A typical computational geometry problem begins: Consider a set P of n points in R^d. However, many applications today work with input that is not precisely known, for example when the data is sensed and has some known error model. What if we do not know the set P exactly, but rather we have a probability distribution mu_p governing the location of each point p in P? Consider a set of (non-fixed) points P, and let mu_P be the probability distribution of this set. We study several measures (e.g. the radius of the smallest enclosing ball, or the area of the smallest enclosing box) with respect to mu_P. The solutions to these problems do not, as in the traditional case, consist of a single answer, but rather a distribution of answers. We describe several data structures that approximate distributions of answers for shape fitting problems. We provide simple and efficient randomized algorithms for computing all of these data structures, which are easy to implement and practical. We provide some experimental results to assert this. We also provide more involved deterministic algorithms for some of these data structures that run in time polynomial in n and 1/eps, where eps is the approximation factor.
A Growing Self-Organizing Network for Reconstructing Curves and Surfaces
Venue: arXiv cs.NE 2008
Year: 2008

Self-organizing networks such as Neural Gas, Growing Neural Gas and many others have been adopted in actual applications for both dimensionality reduction and manifold learning. Typically, in these applications, the structure of the adapted network yields a good estimate of the topology of the unknown subspace from where the input data points are sampled. The approach presented here takes a different perspective, namely by assuming that the input space is a manifold of known dimension. In return, the new type of growing self-organizing network presented gains the ability to adapt itself in way that may guarantee the effective and stable recovery of the exact topological structure of the input manifold.
Analyse et structuration automatique des guides de bonnes pratiques cliniques : essai d'évaluation
Venue: arXiv cs.AI 2008
Year: 2008

Health Practice Guideliens are supposed to unify practices and propose recommendations to physicians. This paper describes GemFrame, a system capable of semi-automatically filling an XML template from free texts in the clinical domain. The XML template includes semantic information not explicitly encoded in the text (pairs of conditions and ac-tions/recommendations). Therefore, there is a need to compute the exact scope of condi-tions over text sequences expressing the re-quired actions. We present a system developped for this task. We show that it yields good performance when applied to the analysis of French practice guidelines. We conclude with a precise evaluation of the tool.