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.

Exponentiated gradient algorithms for large-margin structured classification

We consider the problem of structured classification, where the task is to predict a label y from an input x, and y has meaningful internal structure. Our framework includes supervised training of Markov random fields and weighted context-free grammars as special cases. We describe an algorithm that solves the large-margin optimization problem defined in [12], using an exponential-family (Gibbs distribution) representation of structured objects. The algorithm is efficient—even in cases where the number of labels y is exponential in size—provided that certain expectations under Gibbs distributions can be calculated efficiently. The method for structured labels relies on a more general result, specifically the application of exponentiated gradient updates [7, 8] to quadratic programs.

Adaptive online gradient descent

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between [square root T] and [log T]. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Learning from episodes of degradation and recovery in variable Australian rangelands

Land-change science emphasizes the intimate linkages between the human and environmental components of land management systems. Recent theoretical developments in drylands identify a small set of key principles that can guide the understanding of these linkages. Using these principles, a detailed study of seven major degradation episodes over the past century in Australian grazed rangelands was reanalyzed to show a common set of events: (i) good climatic and economic conditions for a period, leading to local and regional social responses of increasing stocking rates, setting the preconditions for rapid environmental collapse, followed by (ii) a major drought coupled with a fall in the market making destocking financially unattractive, further exacerbating the pressure on the environment; then (iii) permanent or temporary declines in grazing productivity, depending on follow-up seasons coupled again with market and social conditions. The analysis supports recent theoretical developments but shows that the establishment of environmental knowledge that is strictly local may be insufficient on its own for sustainable management. Learning systems based in a wider community are needed that combine local knowledge, formal research, and institutional support. It also illustrates how natural variability in the state of both ecological and social systems can interact to precipitate nonequilibrial change in each other, so that planning cannot be based only on average conditions. Indeed, it is this variability in both environment and social subsystems that hinders the local learning required to prevent collapse.

Extreme ultraviolet (EUV) degradation of poly(olefin sulfone)s : towards applications as EUV photoresists

Poly(olefin sulfone)s, formed by the reaction of sulfur dioxide (SO2) and an olefin, are known to be highly susceptible to degradation by radiation and thus have been identified as candidate materials for chain scission-based extreme ultraviolet lithography (EUVL) resist materials. In order to investigate this further, the synthesis and characterisation of two poly(olefin sulfone)s namely poly(1-pentene sulfone) (PPS) and poly(2-methyl-1-pentene sulfone) (PMPS), was achieved and the two materials were evaluated for possible chain scission EUVL resist applications. It was found that both materials possess high sensitivities to EUV photons; however; the rates of outgassing were extremely high. The only observed degradation products were found to be SO2 and the respective olefin suggesting that depolymerisation takes place under irradiation in a vacuum environment. In addition to depolymerisation, a concurrent conversion of SO2 moieties to a sulfide phase was observed using XPS.