On the Complexity of Strong and Epistemic Credal Networks

Credal networks are graph-based statistical models whose parameters take values on a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The result of inferences with such models depends on the irrelevance/independence concept adopted. In this paper, we study the computational complexity of inferences under the concepts of epistemic irrelevance and strong independence. We strengthen complexity results by showing that inferences with strong independence are NP-hard even in credal trees with ternary variables, which indicates that tractable algorithms, including the existing one for epistemic trees, cannot be used for strong independence. We prove that the polynomial time of inferences in credal trees under epistemic irrelevance is not likely to extend to more general models, because the problem becomes NP-hard even in simple polytrees. These results draw a definite line between networks with efficient inferences and those where inferences are hard, and close several open questions regarding the computational complexity of such models.

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 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 inferences can be performed in linear time if there is a single observed node, which is a relevant practical case. Because our proof is constructive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynomial-time algorithm for SQPNs. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs.

New Complexity Results for MAP in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. It is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.

The Complexity of Approximately Solving Influence Diagrams

Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.

The Inferential Complexity of Bayesian and Credal Networks

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).

Complete control of high-harmonic generation for high average power applications

We present a new dual-gas multi-jet HHG source which can be perfectly controlled via phasematching of the long and short trajectory contributions and is applicable for high average power driver laser systems. © 2011 Optical Society of America.

Seasonal variation in month of diagnosis in children with type 1 diabetes registered in 23 European centers during 1989-2008: little short-term influence of sunshine hours or average temperature

BACKGROUND: The month of diagnosis in childhood type 1 diabetes shows seasonal variation.

OBJECTIVE: We describe the pattern and investigate if year-to-year irregularities are associated with meteorological factors using data from 50 000 children diagnosed under the age of 15 yr in 23 population-based European registries during 1989-2008.

METHODS: Tests for seasonal variation in monthly counts aggregated over the 20 yr period were performed. Time series regression was used to investigate if sunshine hour and average temperature data were predictive of the 240 monthly diagnosis counts after taking account of seasonality and long term trends.

RESULTS: Significant sinusoidal pattern was evident in all but two small centers with peaks in November to February and relative amplitudes ranging from ±11 to ±38% (median ±17%). However, most centers showed significant departures from a sinusoidal pattern. Pooling results over centers, there was significant seasonal variation in each age-group at diagnosis, with least seasonal variation in those under 5 yr. Boys showed greater seasonal variation than girls, particularly those aged 10-14 yr. There were no differences in seasonal pattern between four 5-yr sub-periods. Departures from the sinusoidal trend in monthly diagnoses in the period were significantly associated with deviations from the norm in average temperature (0.8% reduction in diagnoses per 1 °C excess) but not with sunshine hours.

CONCLUSIONS: Seasonality was consistently apparent throughout the period in all age-groups and both sexes, but girls and the under 5 s showed less marked variation. Neither sunshine hour nor average temperature data contributed in any substantial way to explaining departures from the sinusoidal pattern.

On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω(m) messages, where m is the number of edges in the network, and Ω(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms. 

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Reviewing the Literature on the Breakdown of Foster Care Placements for Young People: Complexity and the Social Work Task

Young people in long-term foster care are at risk of experiencing poor social, emotional, behavioural and educational outcomes. Moreover, these placements have a significantly greater chance of breaking down compared to those involving children. This article critically evaluates the factors associated with this particular outcome. It was carried out through a literature review conducted by a social work practitioner in one Health and Social Care Trust in Northern Ireland. The findings evidenced that, apart from overriding safety concerns, placement breakdown was not a one-off event but rather a complex process involving the interplay between a range of dynamic risk and protective factors over time, operating in the wider context of the young person’s history and life experiences. The significance of these findings for social work practitioners is finally considered by identifying key theories to inform understanding and intervention.

Impact of average household income and damage exposure on post-earthquake distress and functioning: A community study following the February 2011 Christchurch earthquake.

Post-traumatic stress, depression and anxiety symptoms are common outcomes following earthquakes, and may persist for months and years. This study systematically examined the impact of neighbourhood damage exposure and average household income on psychological distress and functioning in 600 residents of Christchurch, New Zealand, 4–6 months after the fatal February, 2011 earthquake. Participants were from highly affected and relatively unaffected suburbs in low, medium and high average household income areas. The assessment battery included the Acute Stress Disorder Scale, the depression module of the Patient Health Questionnaire (PHQ-9), and the Generalized Anxiety Disorder Scale (GAD-7), along with single item measures of substance use, earthquake damage and impact, and disruptions in daily life and relationship functioning. Controlling for age, gender and social isolation, participants from low income areas were more likely to meet diagnostic cut-offs for depression and anxiety, and have more severe anxiety symptoms. Higher probabilities of acute stress, depression and anxiety diagnoses were evident in affected versus unaffected areas, and those in affected areas had more severe acute stress, depression and anxiety symptoms. An interaction between income and earthquake effect was found for depression, with those from the low and medium income affected suburbs more depressed. Those from low income areas were more likely, post-earthquake, to start psychiatric medication and increase smoking. There was a uniform increase in alcohol use across participants. Those from the low income affected suburb had greater general and relationship disruption post-quake. Average household income and damage exposure made unique contributions to earthquake-related distress and dysfunction.

Biofilm Complexity Controls Fine Particle Dynamics in Streams

Most models of riverine eco-hydrology and biogeochemistry rely upon bulk parameterization of fluxes. However, the transport and retention of carbon and nutrients in headwater streams is strongly influenced by biofilms (surface-attached microbial communities), which results in strong feedbacks between stream hydrodynamics and biogeochemistry. Mechanistic understanding of the interactions between streambed biofilms and nutrient dynamics is lacking. Here we present experimental results linking microscale observations of biofilm community structure to the deposition and resuspension of clay-sized mineral particles in streams. Biofilms were grown in identical 3 m recirculating flumes over periods of 14-50 days. Fluorescent particles were introduced to each flume, and their deposition was traced over 30 minutes. Particle resuspension from the biofilms was then observed under an increased stream flow, mimicking a flood event. We quantified particle fluxes using flow cytometry and epifluorescence microscopy. We directly observed particle adhesion to the biofilm using a confocal laser scanning microscope. 3-D Optical Coherence Tomography was used to determine biofilm roughness, areal coverage and void space in each flume. These measurements allow us to link biofilm complexity to particle retention during both baseflow and floodflow. The results suggest that increased biofilm complexity favors deposition and retention of fine particles in streams.

Preparing to prescribe: How do clerkship students learn in the midst of complexity?

Prescribing tasks, which involve pharmacological knowledge, clinical decision-making and practical skill, take place within unpredictable social environments and involve interactions within and between endlessly changing health care teams. Despite this, curriculum designers commonly assume them to be simple to learn and perform. This research used mixed methods to explore how undergraduate medical students learn to prescribe in the 'real world'. It was informed by cognitive psychology, sociocultural theory, and systems thinking. We found that learning to prescribe occurs as a dynamic series of socially negotiated interactions within and between individuals, communities and environments. As well as a thematic analysis, we developed a framework of three conceptual spaces in which learning opportunities for prescribing occur. This illustrates a complex systems view of prescribing education and defines three major system components: the "social space", where the environmental conditions influence or bring about a learning experience; the "process space", describing what happens during the learning experience; and the intra-personal "cognitive space", where the learner may develop aspects of prescribing expertise. This conceptualisation broadens the scope of inquiry of prescribing education research by highlighting the complex interplay between individual and social dimensions of learning. This perspective is also likely to be relevant to students' learning of other clinical competencies.

The role of complexity metrics in a multi-institutional dosimetry audit of VMAT

OBJECTIVE: To demonstrate the benefit of complexity metrics such as the modulation complexity score (MCS) and monitor units (MUs) in multi-institutional audits of volumetric-modulated arc therapy (VMAT) delivery.

METHODS: 39 VMAT treatment plans were analysed using MCS and MU. A virtual phantom planning exercise was planned and independently measured using the PTW Octavius(®) phantom and seven29(®) 2D array (PTW-Freiburg GmbH, Freiburg, Germany). MCS and MU were compared with the median gamma index pass rates (2%/2 and 3%/3 mm) and plan quality. The treatment planning systems (TPS) were grouped by VMAT modelling being specifically designed for the linear accelerator manufacturer's own treatment delivery system (Type 1) or independent of vendor for VMAT delivery (Type 2). Differences in plan complexity (MCS and MU) between TPS types were compared.

RESULTS: For Varian(®) linear accelerators (Varian(®) Medical Systems, Inc., Palo Alto, CA), MCS and MU were significantly correlated with gamma pass rates. Type 2 TPS created poorer quality, more complex plans with significantly higher MUs and MCS than Type 1 TPS. Plan quality was significantly correlated with MU for Type 2 plans. A statistically significant correlation was observed between MU and MCS for all plans (R = -0.84, p < 0.01).

CONCLUSION: MU and MCS have a role in assessing plan complexity in audits along with plan quality metrics. Plan complexity metrics give some indication of plan deliverability but should be analysed with plan quality.

ADVANCES IN KNOWLEDGE: Complexity metrics were investigated for a national rotational audit involving 34 institutions and they showed value. The metrics found that more complex plans were created for planning systems which were independent of vendor for VMAT delivery.