Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

The location of Ti atom in sodium alanate : an ab initio spin-polarised study

In this work, ab initio spin-polarised Density Functional Theory (DFT) calculations are performed to study the interaction of a Ti atom with a NaAlH4(001) surface. We confirm that an interstitially located Ti atom in the NaAlH4 subsurface is the most energetically favoured configuration as recently reported (Chem. Comm. (17) 2006, 1822). On the NaAlH4(001) surface, the Ti atom is most stable when adsorbed between two sodium atoms with an AlH4 unit beneath. A Ti atom on top of an Al atom is also found to be an important structure at low temperatures. The diffusion of Ti from the Al-top site to the Na-bridging site has a low activation barrier of 0.20 eV and may be activated at the experimental temperatures (∼323 K). The diffusion of a Ti atom into the energetically favoured subsurface interstitial site occurs via the Na-bridging surface site and is essentially barrierless.

Quantum one-time programs

A one-time program is a hypothetical device by which a user may evaluate a circuit on exactly one input of his choice, before the device self-destructs. One-time programs cannot be achieved by software alone, as any software can be copied and re-run. However, it is known that every circuit can be compiled into a one-time program using a very basic hypothetical hardware device called a one-time memory. At first glance it may seem that quantum information, which cannot be copied, might also allow for one-time programs. But it is not hard to see that this intuition is false: one-time programs for classical or quantum circuits based solely on quantum information do not exist, even with computational assumptions. This observation raises the question, "what assumptions are required to achieve one-time programs for quantum circuits?" Our main result is that any quantum circuit can be compiled into a one-time program assuming only the same basic one-time memory devices used for classical circuits. Moreover, these quantum one-time programs achieve statistical universal composability (UC-security) against any malicious user. Our construction employs methods for computation on authenticated quantum data, and we present a new quantum authentication scheme called the trap scheme for this purpose. As a corollary, we establish UC-security of a recent protocol for delegated quantum computation.

Rice ragged stunt oryzavirus genome segment S4 could encode an RNA dependent RNA polymerase and a second protein of unknown function

The complete nucleotide sequence of genome segment S4 of rice ragged stunt oryzavirus (RRSV, Thai-isolate) was determined. The 3823 bp sequence contains two large open reading frames (ORFs). ORF1, spanning nucleotides 12 to 3776, is capable of encoding a protein of M(r) 141,380 (P4a). The P4a amino acid sequence predicted from the nucleotide sequence contains sequence motifs conserved in RNA-dependent RNA polymerases (RDRPs). When compared for evolutionary relationships with RDRPs of other reoviruses using the amino acid sequences around the conserved GDD motif, P4a was shown to be more related to Nilaparvata lugens reovirus and reovirus serotype 3 than to rice dwarf phytoreovirus, bovine rotavirus or bluetongue virus. The ORF2, spanning nucleotides 491 to 1468, is out of frame with ORF1 and is capable of encoding a protein of 36, 920 (P4b). Coupled in vitro transcription-translation from cloned ORF2 in wheat germ extract confirmed the existence of ORF2 but in vivo production and possible function of P4b is yet to be determined.

Molecular sliding filament model for muscular contraction based on multiscale investigation

A multiscale approach that bridges the biophysics of the actin molecules at nanoscale and the biomechanics of actin filament at microscale level is developed and used to evaluate the mechanical performances of actin filament bundles. In order to investigate the contractile properties of skeletal muscle which is induced by the protein motor of myosin, a molecular model is proposed in the prediction of the dynamic behaviors of skeletal muscle based on classic sliding filament model. Randomly distributed myosin motors are applied on a 2.2 μm long sarcomere, whose principal components include actin and myosin filaments. It can be found that, the more myosin motors on the sarcomere, the faster the sarcomere contracts. The result demonstrates that the sarcomere shortening speed cannot increase infinitely by the modulation of myosin, thus providing insight into the self-protective properties of skeletal muscles. This molecular filament sliding model provides a theoretical way to evaluate the properties of skeletal muscles, and contributes to the understandings of the molecular mechanisms in the physiological phenomenon of muscular contraction.

[Den musikindustriella förändringen fortsätter och en tjänstebaserad musikekonomi börjar ta form] [in Swedish]

Det har nu gått mer än tio år sedan en student vid Northeastern University i USA lanserade den första fildelningstjänsten som blev framgångsrik bland den breda allmänheten (e.g. Alderman 2001). Lanseringen av tjänsten, som kallades Napster, ses ofta som inledningen på ett av de mest dramatiska decennierna i musikbranschens historia. En lång rad internetbaserade tjänster som följt i Napsters spår har gjort det möjligt att sprida musik till miljontals användare utan att upphovsmän och rättighetsinnehavare fått någon ersättning. Katt-och-råtta-leken mellan lagstiftning och teknik har varit intensiv och har utvecklats till ett av decenniets allra hetaste diskussionsämnen bland politiker och ledarskribenter. Försäljningen av inspelad musik har sjunkit dramatiskt och musikbranschen har tvingats ifrågasätta många väletablerade sanningar. Det här kapitlet belyser ett antal fundamentala aspekter av denna förändring och utforskar några av den ”nya” musikbranschens viktigaste karaktäristika. Under den tid som musikbranschen har beforskats har vanligtvis betoningen legat på fonogrammen, det vill säga den del av branschen som rör produktion och konsumtion av inspelad musik. På grund av branschens förändrade struktur kommer dock det här kapitlet att vidga perspektivet en smula och även inkludera musikbranschens andra delar som exempelvis konserter och förlagsverksamhet...

Medical semantic similarity with a neural language model

Advances in neural network language models have demonstrated that these models can effectively learn representations of words meaning. In this paper, we explore a variation of neural language models that can learn on concepts taken from structured ontologies and extracted from free-text, rather than directly from terms in free-text. This model is employed for the task of measuring semantic similarity between medical concepts, a task that is central to a number of techniques in medical informatics and information retrieval. The model is built with two medical corpora (journal abstracts and patient records) and empirically validated on two ground-truth datasets of human-judged concept pairs assessed by medical professionals. Empirically, our approach correlates closely with expert human assessors ($\approx$ 0.9) and outperforms a number of state-of-the-art benchmarks for medical semantic similarity. The demonstrated superiority of this model for providing an effective semantic similarity measure is promising in that this may translate into effectiveness gains for techniques in medical information retrieval and medical informatics (e.g., query expansion and literature-based discovery).

Association between aneurysm shoulder stress and abdominal aortic aneurysm expansion: A longitudinal follow-up study

Background Aneurysm expansion rate is an important indicator of the potential risk of abdominal aortic aneurysm (AAA) rupture. Stress within the AAA wall is also thought to be a trigger for its rupture. However, the association between aneurysm wall stresses and expansion of AAA is unclear. Methods and Results Forty-four patients with AAAs were included in this longitudinal follow-up study. They were assessed by serial abdominal ultrasonography and computed tomography scans if a critical size was reached or a rapid expansion occurred. Patient-specific 3-dimensional AAA geometries were reconstructed from the follow-up computed tomography images. Structural analysis was performed to calculate the wall stresses of the AAA models at both baseline and final visit. A nonlinear large-strain finite element method was used to compute the wall-stress distribution. The relationship between wall stresses and expansion rate was investigated. Slowly and rapidly expanding aneurysms had comparable baseline maximum diameters (median, 4.35 cm [interquartile range, 4.12 to 5.0 cm] versus 4.6 cm [interquartile range, 4.2 to 5.0 cm]; P=0.32). Rapidly expanding AAAs had significantly higher shoulder stresses than slowly expanding AAAs (median, 300 kPa [interquartile range, 280 to 320 kPa] versus 225 kPa [interquartile range, 211 to 249 kPa]; P=0.0001). A good correlation between shoulder stress at baseline and expansion rate was found (r=0.71; P=0.0001). Conclusion A higher shoulder stress was found to have an association with a rapidly expanding AAA. Therefore, it may be useful for estimating the expansion of AAAs and improve risk stratification of patients with AAAs.