OpenRaiser/Intern-Atlas huggingface dataset:
The Ultrasound Visualization Pipeline - A Survey
Venue: arXiv cs.GR 2012
Year: 2012

Ultrasound is one of the most frequently used imaging modality in medicine. The high spatial resolution, its interactive nature and non-invasiveness makes it the first choice in many examinations. Image interpretation is one of ultrasound's main challenges. Much training is required to obtain a confident skill level in ultrasound-based diagnostics. State-of-the-art graphics techniques is needed to provide meaningful visualizations of ultrasound in real-time. In this paper we present the process-pipeline for ultrasound visualization, including an overview of the tasks performed in the specific steps. To provide an insight into the trends of ultrasound visualization research, we have selected a set of significant publications and divided them into a technique-based taxonomy covering the topics pre-processing, segmentation, registration, rendering and augmented reality. For the different technique types we discuss the difference between ultrasound-based techniques and techniques for other modalities.
Classification of Various Security Techniques in Databases and their Comparative Analysis
Venue: arXiv cs.CR 2012
Year: 2012

Data security is one of the most crucial and a major challenge in the digital world. Security, privacy and integrity of data are demanded in every operation performed on internet. Whenever security of data is discussed, it is mostly in the context of secure transfer of data over the unreliable communication networks. But the security of the data in databases is also as important. In this paper we will be presenting some of the common security techniques for the data that can be implemented in fortifying and strengthening the databases.
Efficiently expressing feasibility problems in Linear Systems, as feasibility problems in Asymptotic-Linear-Programs
Venue: arXiv cs.CC 2012
Year: 2012

We present a polynomial-time algorithm that obtains a set of Asymptotic Linear Programs (ALPs) from a given linear system S, such that one of these ALPs admits a feasible solution if and only if S admits a feasible solution. We also show how to use the same algorithm to determine whether or not S admits a non-trivial solution for any desired subset of its variables. S is allowed to consist of linear constraints over real variables with integer coefficients, where each constraint has either a lesser-than-or-equal-to, or a lesser-than, or a not-equal-to relational operator. Each constraint of the obtained ALPs has a lesser-than-or-equal-to relational operator, and the coefficients of its variables vary linearly with respect to the time parameter that tends to positive infinity.
A Novel Effective, Secure and Robust CDMA Digital Image Watermarking in YUV Color Space Using DWT2
Venue: arXiv cs.CR 2012
Year: 2012

This paper is allocated to CDMA digital images watermarking for ownership verification and image authentication applications, which for more security, watermark W is converted to a sequence and then a random binary sequence R of size n is adopted to encrypt the watermark; where n is the size of the watermark. This adopting process uses a pseudo-random number generator to determine the pixel to be used on a given key. After converting the host image to YUV color space and then wavelet decomposition of Y channel, this adopted watermark is embedded into the selected subbands coefficients of Y channel using the correlation properties of additive pseudo- random noise patterns. The experimental results show that the proposed approach provides extra imperceptibility, security and robustness against JPEG compression and different noises attacks compared to the similar proposed methods. Moreover, the proposed approach has no need of the original image to extract watermarks.
A Comparison between Digital Image Watermarking in Tow Different Color Spaces Using DWT2
Venue: arXiv cs.CR 2012
Year: 2012

A novel digital watermarking for ownership verification and image authentication applications using discrete wavelet transform (DWT) is proposed in this paper. Most previous proposed watermarking algorithms embed sequences of random numbers as watermarks. Here binary images are taken as watermark for embedding. In the proposed approach, the host image is converted into the YCbCr color space and then its Y channel decomposed into wavelet coefficients. The selected approximation coefficients are quantized and then their four least significant bits of the quantized coefficients are replaced by the watermark using LSB insertion technique. At last, the watermarked image is synthesized from the changed and unchanged DWT coefficients. The experiments show that the proposed approach provides extra imperceptibility and robustness against wavelet compression compared to the traditional embedding methods in RGB color space. Moreover, the proposed approach has no need of the original image to extract watermarks.
Distributed Tree Kernels
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we propose the distributed tree kernels (DTK) as a novel method to reduce time and space complexity of tree kernels. Using a linear complexity algorithm to compute vectors for trees, we embed feature spaces of tree fragments in low-dimensional spaces where the kernel computation is directly done with dot product. We show that DTKs are faster, correlate with tree kernels, and obtain a statistically similar performance in two natural language processing tasks.
Partial-Hessian Strategies for Fast Learning of Nonlinear Embeddings
Venue: arXiv cs.LG 2012
Year: 2012

Stochastic neighbor embedding (SNE) and related nonlinear manifold learning algorithms achieve high-quality low-dimensional representations of similarity data, but are notoriously slow to train. We propose a generic formulation of embedding algorithms that includes SNE and other existing algorithms, and study their relation with spectral methods and graph Laplacians. This allows us to define several partial-Hessian optimization strategies, characterize their global and local convergence, and evaluate them empirically. We achieve up to two orders of magnitude speedup over existing training methods with a strategy (which we call the spectral direction) that adds nearly no overhead to the gradient and yet is simple, scalable and applicable to several existing and future embedding algorithms.
Nonparametric variational inference
Venue: arXiv cs.LG 2012
Year: 2012

Variational methods are widely used for approximate posterior inference. However, their use is typically limited to families of distributions that enjoy particular conjugacy properties. To circumvent this limitation, we propose a family of variational approximations inspired by nonparametric kernel density estimation. The locations of these kernels and their bandwidth are treated as variational parameters and optimized to improve an approximate lower bound on the marginal likelihood of the data. Using multiple kernels allows the approximation to capture multiple modes of the posterior, unlike most other variational approximations. We demonstrate the efficacy of the nonparametric approximation with a hierarchical logistic regression model and a nonlinear matrix factorization model. We obtain predictive performance as good as or better than more specialized variational methods and sample-based approximations. The method is easy to apply to more general graphical models for which standard variational methods are difficult to derive.
Bayesian Sequential Auctions
Venue: arXiv cs.GT 2012
Year: 2012

In many natural settings agents participate in multiple different auctions that are not simultaneous. In such auctions, future opportunities affect strategic considerations of the players. The goal of this paper is to develop a quantitative understanding of outcomes of such sequential auctions. In earlier work (Paes Leme et al. 2012) we initiated the study of the price of anarchy in sequential auctions. We considered sequential first price auctions in the full information model, where players are aware of all future opportunities, as well as the valuation of all players. In this paper, we study efficiency in sequential auctions in the Bayesian environment, relaxing the informational assumption on the players. We focus on two environments, both studied in the full information model in Paes Leme et al. 2012, matching markets and matroid auctions. In the full information environment, a sequential first price cut auction for matroid settings is efficient. In Bayesian environments this is no longer the case, as we show using a simple example with three players. Our main result is a bound of $1+\frac{e}{e-1}\approx 2.58$ on the price of anarchy in both matroid auctions and single-value matching markets (even with correlated types) and a bound of $2\frac{e}{e-1}\approx 3.16$ for general matching markets with independent types. To bound the price of anarchy we need to consider possible deviations at an equilibrium. In a sequential Bayesian environment the effect of deviations is more complex than in one-shot games; early bids allow others to infer information about the player's value. We create effective deviations despite the presence of this difficulty by introducing a bluffing technique of independent interest.
The Robustness and Super-Robustness of L^p Estimation, when p < 1
Venue: arXiv cs.LG 2012
Year: 2012

In robust statistics, the breakdown point of an estimator is the percentage of outliers with which an estimator still generates reliable estimation. The upper bound of breakdown point is 50%, which means it is not possible to generate reliable estimation with more than half outliers. In this paper, it is shown that for majority of experiences, when the outliers exceed 50%, but if they are distributed randomly enough, it is still possible to generate a reliable estimation from minority good observations. The phenomenal of that the breakdown point is larger than 50% is named as super robustness. And, in this paper, a robust estimator is called strict robust if it generates a perfect estimation when all the good observations are perfect. More specifically, the super robustness of the maximum likelihood estimator of the exponential power distribution, or L^p estimation, where p<1, is investigated. This paper starts with proving that L^p (p<1) is a strict robust location estimator. Further, it is proved that L^p (p < 1)has the property of strict super-robustness on translation, rotation, scaling transformation and robustness on Euclidean transform.
On List Colouring and List Homomorphism of Permutation and Interval Graphs
Venue: arXiv cs.DM 2012
Year: 2012

List colouring is an NP-complete decision problem even if the total number of colours is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list colouring of permutation graphs with a bounded total number of colours. More generally we give a polynomial-time algorithm that solves the list-homomorphism problem to any fixed target graph for a large class of input graphs including all permutation and interval graphs.
Lucretia - a type system for objects in languages with reflection
Venue: arXiv cs.PL 2012
Year: 2012

Object-oriented scripting languages such as JavaScript or Python gain in popularity due to their flexibility. Still, the growing code bases written in the languages call for methods that make possible to automatically control the properties of the programs that ensure their stability in the running time. We propose a type system, called Lucretia, that makes possible to control the object structure of languages with reflection. Subject reduction and soundness of the type system with respect to the semantics of the language is proved.
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
Venue: arXiv cs.CG 2012
Year: 2012

In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that for every fixed k, B_k-VPG is a proper subset of B_{k+1}-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is given by a B_{k+1}-VPG representation. We also show that the class B_k-VPG (for k>0) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.
Linking Quality Attributes and Constraints with Architectural Decisions
Venue: arXiv cs.SE 2012
Year: 2012

Quality attributes and constraints are among the main drivers of architectural decision making. The quality attributes are improved or damaged by the architectural decisions, while restrictions directly include or exclude parts of the architecture (for example, the logical components or technologies). We can determine the impact of a decision of architecture in software quality, or which parts of the architecture are affected by a constraint, but the difficult problem is whether we are respecting the quality requirements (requirements on quality attributes) and constraints with all the architectural decisions made. Currently, the common practice is that architects use their own experience to design architectures that meet the quality requirements and restrictions, but at the end, especially for the crucial decisions, the architect has to deal with complex trade-offs between quality attributes and juggle possible incompatibilities raised by the constraints. In this paper we present Quark, a computer-aided method to support architects in software architecture decision making.
Eliminating Scanning Delay using Advanced Neighbor Discovery with Caching (ANDWC)
Venue: arXiv cs.NI 2012
Year: 2012

The advance in wireless technologies and portable devices such as smart phones has made the Wireless Local Area Networks (WLANs) popular in the recent years. Nowadays, WLANs have become widely accepted in both private and public sectors due to ease of installation, reasonable prices and high data rates that can support real time applications. However, fast handoff required for such real-time applications is not provided in the current IEEE 802.11 specifications. Consequently, providing seamless mobility in these WLANs is an important issue. To solve this problem, a new fast handoff scheme called Advanced Neighbor Discovery with Caching (ANDWC) is proposed. This new mechanism is based on the user's mobility between two or more different Basic Service Sets (Layer 2 mobility). ANDWC can eliminate scanning delay (which contributes up to 90% of the total handoff latency) to provide seamless handoff by using pre-neighbor-discovery and caching mechanisms.
Learning Probabilistic Relational Dynamics for Multiple Tasks
Venue: arXiv cs.AI 2012
Year: 2012

The ways in which an agent's actions affect the world can often be modeled compactly using a set of relational probabilistic planning rules. This paper addresses the problem of learning such rule sets for multiple related tasks. We take a hierarchical Bayesian approach, in which the system learns a prior distribution over rule sets. We present a class of prior distributions parameterized by a rule set prototype that is stochastically modified to produce a task-specific rule set. We also describe a coordinate ascent algorithm that iteratively optimizes the task-specific rule sets and the prior distribution. Experiments using this algorithm show that transferring information from related tasks significantly reduces the amount of training data required to predict action effects in blocks-world domains.
Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

We formulate in this paper the mini-bucket algorithm for approximate inference in terms of exact inference on an approximate model produced by splitting nodes in a Bayesian network. The new formulation leads to a number of theoretical and practical implications. First, we show that branchand- bound search algorithms that use minibucket bounds may operate in a drastically reduced search space. Second, we show that the proposed formulation inspires new minibucket heuristics and allows us to analyze existing heuristics from a new perspective. Finally, we show that this new formulation allows mini-bucket approximations to benefit from recent advances in exact inference, allowing one to significantly increase the reach of these approximations.
Collaborative Filtering and the Missing at Random Assumption
Venue: arXiv cs.LG 2012
Year: 2012

Rating prediction is an important application, and a popular research topic in collaborative filtering. However, both the validity of learning algorithms, and the validity of standard testing procedures rest on the assumption that missing ratings are missing at random (MAR). In this paper we present the results of a user study in which we collect a random sample of ratings from current users of an online radio service. An analysis of the rating data collected in the study shows that the sample of random ratings has markedly different properties than ratings of user-selected songs. When asked to report on their own rating behaviour, a large number of users indicate they believe their opinion of a song does affect whether they choose to rate that song, a violation of the MAR condition. Finally, we present experimental results showing that incorporating an explicit model of the missing data mechanism can lead to significant improvements in prediction performance on the random sample of ratings.
Polynomial Constraints in Causal Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

We use the implicitization procedure to generate polynomial equality constraints on the set of distributions induced by local interventions on variables governed by a causal Bayesian network with hidden variables. We show how we may reduce the complexity of the implicitization problem and make the problem tractable in certain causal Bayesian networks. We also show some preliminary results on the algebraic structure of polynomial constraints. The results have applications in distinguishing between causal models and in testing causal models with combined observational and experimental data.
Accuracy Bounds for Belief Propagation
Venue: arXiv cs.AI 2012
Year: 2012

The belief propagation (BP) algorithm is widely applied to perform approximate inference on arbitrary graphical models, in part due to its excellent empirical properties and performance. However, little is known theoretically about when this algorithm will perform well. Using recent analysis of convergence and stability properties in BP and new results on approximations in binary systems, we derive a bound on the error in BP's estimates for pairwise Markov random fields over discrete valued random variables. Our bound is relatively simple to compute, and compares favorably with a previous method of bounding the accuracy of BP.
Making life better one large system at a time: Challenges for UAI research
Venue: arXiv cs.SE 2012
Year: 2012

The rapid growth and diversity in service offerings and the ensuing complexity of information technology ecosystems present numerous management challenges (both operational and strategic). Instrumentation and measurement technology is, by and large, keeping pace with this development and growth. However, the algorithms, tools, and technology required to transform the data into relevant information for decision making are not. The claim in this paper (and the invited talk) is that the line of research conducted in Uncertainty in Artificial Intelligence is very well suited to address the challenges and close this gap. I will support this claim and discuss open problems using recent examples in diagnosis, model discovery, and policy optimization on three real life distributed systems.
Imitation Learning with a Value-Based Prior
Venue: arXiv cs.LG 2012
Year: 2012

The goal of imitation learning is for an apprentice to learn how to behave in a stochastic environment by observing a mentor demonstrating the correct behavior. Accurate prior knowledge about the correct behavior can reduce the need for demonstrations from the mentor. We present a novel approach to encoding prior knowledge about the correct behavior, where we assume that this prior knowledge takes the form of a Markov Decision Process (MDP) that is used by the apprentice as a rough and imperfect model of the mentor's behavior. Specifically, taking a Bayesian approach, we treat the value of a policy in this modeling MDP as the log prior probability of the policy. In other words, we assume a priori that the mentor's behavior is likely to be a high value policy in the modeling MDP, though quite possibly different from the optimal policy. We describe an efficient algorithm that, given a modeling MDP and a set of demonstrations by a mentor, provably converges to a stationary point of the log posterior of the mentor's policy, where the posterior is computed with respect to the "value based" prior. We also present empirical evidence that this prior does in fact speed learning of the mentor's policy, and is an improvement in our experiments over similar previous methods.
Dynamic Pricing under Finite Space Demand Uncertainty: A Multi-Armed Bandit with Dependent Arms
Venue: arXiv cs.LG 2012
Year: 2012

We consider a dynamic pricing problem under unknown demand models. In this problem a seller offers prices to a stream of customers and observes either success or failure in each sale attempt. The underlying demand model is unknown to the seller and can take one of N possible forms. In this paper, we show that this problem can be formulated as a multi-armed bandit with dependent arms. We propose a dynamic pricing policy based on the likelihood ratio test. We show that the proposed policy achieves complete learning, i.e., it offers a bounded regret where regret is defined as the revenue loss with respect to the case with a known demand model. This is in sharp contrast with the logarithmic growing regret in multi-armed bandit with independent arms.
Analysis of a Nature Inspired Firefly Algorithm based Back-propagation Neural Network Training
Venue: arXiv cs.AI 2012
Year: 2012

Optimization algorithms are normally influenced by meta-heuristic approach. In recent years several hybrid methods for optimization are developed to find out a better solution. The proposed work using meta-heuristic Nature Inspired algorithm is applied with back-propagation method to train a feed-forward neural network. Firefly algorithm is a nature inspired meta-heuristic algorithm, and it is incorporated into back-propagation algorithm to achieve fast and improved convergence rate in training feed-forward neural network. The proposed technique is tested over some standard data set. It is found that proposed method produces an improved convergence within very few iteration. This performance is also analyzed and compared to genetic algorithm based back-propagation. It is observed that proposed method consumes less time to converge and providing improved convergence rate with minimum feed-forward neural network design.