Mind change optimal learning of Bayes net structure

This paper analyzes the problem of learning the structure of a Bayes net (BN) in the theoretical framework of Gold’s learning paradigm. Bayes nets are one of the most prominent formalisms for knowledge representation and probabilistic and causal reasoning. We follow constraint-based approaches to learning Bayes net structure, where learning is based on observed conditional dependencies between variables of interest (e.g., “X is dependent on Y given any assignment to variable Z”). Applying learning criteria in this model leads to the following results. (1) The mind change complexity of identifying a Bayes net graph over variables V from dependency data is |V| 2 , the maximum number of edges. (2) There is a unique fastest mind-change optimal Bayes net learner; convergence speed is evaluated using Gold’s dominance notion of “uniformly faster convergence”. This learner conjectures a graph if it is the unique Bayes net pattern that satisfies the observed dependencies with a minimum number of edges, and outputs “no guess” otherwise. Therefore we are using standard learning criteria to define a natural and novel Bayes net learning algorithm. We investigate the complexity of computing the output of the fastest mind-change optimal learner, and show that this problem is NP-hard (assuming P = RP). To our knowledge this is the first NP-hardness result concerning the existence of a uniquely optimal Bayes net structure.

Mothers, monsters, heroes and whores: reinscribing patriarchy in European Holocaust films

This article examines the portrayal of female Gentile rescuers in Holocaust films. We analyze two recent and somewhat unconventional Eastern European films, Agnieszka Holland’s In Darkness (Poland, 2011) and Jan Hrebejk’s Divided We Fall (Czech Republic, 2000), which, to varying degrees, disrupt conventional narratives of selfless heroism and avoid the eroticized objectification of women common in many (particularly American) Holocaust films. Nevertheless, a detailed analysis reveals how these films also marginalize or erase women’s roles as rescuers, either in preference to narratives of dominative masculine heroism or in order to undertake a politico-religious appropriation of the Holocaust, each of which implicitly excludes and exploits the feminine. In both cases, the films trivialize women’s particular and complex historical experiences, including sexual violence, and subordinate them to masculine interests.