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.

Enhancement of behavioral sensitization, anxiety-like behavior, and hippocampal and frontal cortical CREB levels following cocaine abstinence in mice exposed to cocaine during adolescence

Adolescence has been linked to greater risk-taking and novelty-seeking behavior and a higher prevalence of drug abuse and risk of relapse. Decreases in cyclic adenosine monophosphate response element binding protein (CREB) and phosphorylated CREB (pCREB) have been reported after repeated cocaine administration in animal models. We compared the behavioral effects of cocaine and abstinence in adolescent and adult mice and investigated possible age-related differences in CREB and pCREB levels. Adolescent and adult male Swiss mice received one daily injection of saline or cocaine (10 mg/kg, i.p.) for 8 days. On day 9, the mice received a saline injection to evaluate possible environmental conditioning. After 9 days of withdrawal, the mice were tested in the elevated plus maze to evaluate anxiety-like behavior. Twelve days after the last saline/cocaine injection, the mice received a challenge injection of either cocaine or saline, and locomotor activity was assessed. One hour after the last injection, the brains were extracted, and CREB and pCREB levels were evaluated using Western blot in the prefrontal cortex (PFC) and hippocampus. The cocaine-pretreated mice during adolescence exhibited a greater magnitude of the expression of behavioral sensitization and greater cocaine withdrawal-induced anxiety-like behavior compared with the control group. Significant increases in CREB levels in the PFC and hippocampus and pCREB in the hippocampus were observed in cocaine-abstinent animals compared with the animals treated with cocaine in adulthood. Interestingly, significant negative correlations were observed between cocaine sensitization and CREB levels in both regions. These results suggest that the behavioral and neurochemical consequences of psychoactive substances in a still-developing nervous system can be more severe than in an already mature nervous system

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.