Complexity of inferences in polytree-shaped semi-qualitative probabilistic networks

Semi-qualitative probabilistic networks (SQPNs) merge two important graphical model formalisms: Bayesian networks and qualitative probabilistic networks. They provade a very Complexity of inferences in polytree-shaped semi-qualitative probabilistic networks and qualitative probabilistic networks. They provide a very general modeling framework by allowing the combination of numeric and qualitative assessments over a discrete domain, and can be compactly encoded by exploiting the same factorization of joint probability distributions that are behind the bayesian networks. This paper explores the computational complexity of semi-qualitative probabilistic networks, and takes the polytree-shaped networks as its main target. We show that the inference problem is coNP-Complete for binary polytrees with multiple observed nodes. We also show that interferences can be performed in time linear in the number of nodes if there is a single observed node. Because our proof is construtive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynominal-time algorithm for SQPn. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs.

Planejamento endodontico de dente duplo com tomografia computadorizada cone-beam em paciente do HRAC–USP: relato de caso

Objetivo: Dente Duplo (“double tooth”) é uma anomalia de forma que ocorre pela fusão de dois ou mais dentes ou geminação de um único dente, geralmente durante a fase de morfodiferenciação do germe dentário. A incidência de dente duplo varia 0,14-5,0% da população mundial, sem predileção pelo gênero. Apresentação unilateral é mais comum do que a bilateral. No geral, as anomalias dentarias em pacientes com fissura labiopalatina ocorrem próximas à região da fissura. O objetivo deste trabalho é relatar o tratamento endodôntico não cirúrgico de um caso de dentes duplos em um paciente com fissura labiopalatina. Relato de Caso: Paciente de gênero feminino de 10 anos com fissura labiopalatina matriculado no Hospital de Reabilitação de Anomalias Craniofaciais (HRAC-USP), encaminhado ao setor de Endodontia do HRAC-USP para realizar o tratamento endodôntico dos dentes 11 e 12 para ser re-anatomizados. Pela superposição dos dentes 11, 12, e presença de uma cúspide acessória (“talon cusp”) além de um dente supranumerário, as radiografia panorâmica e a radiografia periapical não mostram claramente a anatomia externa do dente e a interna dos condutos radiculares, motivo pelo qual foi solicitada uma tomografia computadorizada Cone-Beam para determinar o comprimento de trabalho para preparo biomecânico e obturação dos condutos radiculares. Serão apresentadas as etapas de diagnóstico e tratamento realizados no caso. Conclusão: Pela morfologia anormal da coroa e complexidade dos canais radiculares, o tratamento endodôntico apresentaria dificuldades, por isso o exame clínico e radiográfico cuidadoso é essencial para o sucesso do tratamento endodôntico. Desta forma concluise que a imagem fornecida pela tomografia computadorizada Cone-Beam foi útil no planejamento e tratamento deste caso.

Evolving decision trees with beam search-based initialization and lexicographic multi-objective evaluation

Decision tree induction algorithms represent one of the most popular techniques for dealing with classification problems. However, traditional decision-tree induction algorithms implement a greedy approach for node splitting that is inherently susceptible to local optima convergence. Evolutionary algorithms can avoid the problems associated with a greedy search and have been successfully employed to the induction of decision trees. Previously, we proposed a lexicographic multi-objective genetic algorithm for decision-tree induction, named LEGAL-Tree. In this work, we propose extending this approach substantially, particularly w.r.t. two important evolutionary aspects: the initialization of the population and the fitness function. We carry out a comprehensive set of experiments to validate our extended algorithm. The experimental results suggest that it is able to outperform both traditional algorithms for decision-tree induction and another evolutionary algorithm in a variety of application domains.

CID: an efficient complexity-invariant distance for time series

The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While dozens of classification algorithms have been applied to time series, recent empirical evidence strongly suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm is important, and depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping, and cardiology data requires invariance to the baseline (the mean value). Similarly, recent work suggests that for time series clustering, the choice of clustering algorithm is much less important than the choice of distance measure used.In this work we make a somewhat surprising claim. There is an invariance that the community seems to have missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where some complex objects may be incorrectly assigned to a simpler class. Similarly, for clustering this effect can introduce errors by “suggesting” to the clustering algorithm that subjectively similar, but complex objects belong in a sparser and larger diameter cluster than is truly warranted.We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification and clustering accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series mining experiments ever attempted in a single work, and show that complexity-invariant distance measures can produce improvements in classification and clustering in the vast majority of cases.

A complete CMOS UWB timed-array transmitter with a 3D Vivaldi antenna array for electronic high-resolution beam spatial scanning

We present a new Ultra Wide Band (UWB) Timed- Array Transmitter System with Beamforming capability for high-resolution remote acquisition of vital signals. The system consists of four identical channels, where each is formed of a serial topology with three modules: programmable delay circuit (PDC or τ), a novel UWB 5th Gaussian Derivative order pulse generator circuit (PG), and a planar Vivaldi antenna. The circuit was designed using 0.18μm CMOS standard process and the planar antenna array was designed with filmconductor on Rogers RO3206 substrate. Spice simulations results showed the pulse generation with 104 mVpp amplitude and 500 ps width. The power consumption is 543 μW, and energy consumption 0.27 pJ per pulse using a 2V power supply at a pulse repetition rate (PRR) of 100 MHz. Electromagnetic simulations results, using CST Microwave (MW) Studio 2011, showed the main lobe radiation with a gain maximum of 13.2 dB, 35.5º x 36.7º angular width, and a beam steering between 17º and -11º for azimuthal (θ) angles and 17º and -18º for elevation (φ) angles at the center frequency of 6 GHz

Entanglement of two-qubit photon beam by magnetic field.

We have studied the possibility of affecting the entanglement measure of 2-qubit system consisting of two photons with different fi xed frequencies but with two arbitrary linear polarizations, moving in the same direction, by the help of an applied external magnetic field. The interaction between the magnetic fi eld and the photons in our model is achieved through intermediate electrons that interact with both the photons and the magnetic fi eld. The possibility of exact theoretical analysis of this scheme is based on known exact solutions that describe the interaction of an electron subjected to an external magnetic fi eld (or a medium of electrons not interacting with each other) with a quantized field of two photons. We adapt these exact solutions to the case under consideration. Using explicit wave functions for the resulting electromagnetic fi eld, we calculate the entanglement measure of the photon beam as a function of the applied magnetic field and parameters of the electron medium.