Classification calibration dimension for general multiclass losses

We study consistency properties of surrogate loss functions for general multiclass classification problems, defined by a general loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning problems), to the general multiclass setting, and derive necessary and sufficient conditions for a surrogate loss to be classification calibrated with respect to a loss matrix in this setting. We then introduce the notion of \emph{classification calibration dimension} of a multiclass loss matrix, which measures the smallest `size' of a prediction space for which it is possible to design a convex surrogate that is classification calibrated with respect to the loss matrix. We derive both upper and lower bounds on this quantity, and use these results to analyze various loss matrices. In particular, as one application, we provide a different route from the recent result of Duchi et al.\ (2010) for analyzing the difficulty of designing `low-dimensional' convex surrogates that are consistent with respect to pairwise subset ranking losses. We anticipate the classification calibration dimension may prove to be a useful tool in the study and design of surrogate losses for general multiclass learning problems.

Optimal control of information epidemics modeled as Maki Thompson rumors

We model the spread of information in a homogeneously mixed population using the Maki Thompson rumor model. We formulate an optimal control problem, from the perspective of single campaigner, to maximize the spread of information when the campaign budget is fixed. Control signals, such as advertising in the mass media, attempt to convert ignorants and stiflers into spreaders. We show the existence of a solution to the optimal control problem when the campaigning incurs non-linear costs under the isoperimetric budget constraint. The solution employs Pontryagin's Minimum Principle and a modified version of forward backward sweep technique for numerical computation to accommodate the isoperimetric budget constraint. The techniques developed in this paper are general and can be applied to similar optimal control problems in other areas. We have allowed the spreading rate of the information epidemic to vary over the campaign duration to model practical situations when the interest level of the population in the subject of the campaign changes with time. The shape of the optimal control signal is studied for different model parameters and spreading rate profiles. We have also studied the variation of the optimal campaigning costs with respect to various model parameters. Results indicate that, for some model parameters, significant improvements can be achieved by the optimal strategy compared to the static control strategy. The static strategy respects the same budget constraint as the optimal strategy and has a constant value throughout the campaign horizon. This work finds application in election and social awareness campaigns, product advertising, movie promotion and crowdfunding campaigns. (C) 2014 Elsevier B.V. All rights reserved.

Statistical significance of episodes with general partial orders

Frequent episode discovery is one of the methods used for temporal pattern discovery in sequential data. An episode is a partially ordered set of nodes with each node associated with an event type. For more than a decade, algorithms existed for episode discovery only when the associated partial order is total (serial episode) or trivial (parallel episode). Recently, the literature has seen algorithms for discovering episodes with general partial orders. In frequent pattern mining, the threshold beyond which a pattern is inferred to be interesting is typically user-defined and arbitrary. One way of addressing this issue in the pattern mining literature has been based on the framework of statistical hypothesis testing. This paper presents a method of assessing statistical significance of episode patterns with general partial orders. A method is proposed to calculate thresholds, on the non-overlapped frequency, beyond which an episode pattern would be inferred to be statistically significant. The method is first explained for the case of injective episodes with general partial orders. An injective episode is one where event-types are not allowed to repeat. Later it is pointed out how the method can be extended to the class of all episodes. The significance threshold calculations for general partial order episodes proposed here also generalize the existing significance results for serial episodes. Through simulations studies, the usefulness of these statistical thresholds in pruning uninteresting patterns is illustrated. (C) 2014 Elsevier Inc. All rights reserved.

Physical Layer Data Fusion Via Distributed Co-Phasing With General Signal Constellations

This paper studies a pilot-assisted physical layer data fusion technique known as Distributed Co-Phasing (DCP). In this two-phase scheme, the sensors first estimate the channel to the fusion center (FC) using pilots sent by the latter; and then they simultaneously transmit their common data by pre-rotating them by the estimated channel phase, thereby achieving physical layer data fusion. First, by analyzing the symmetric mutual information of the system, it is shown that the use of higher order constellations (HOC) can improve the throughput of DCP compared to the binary signaling considered heretofore. Using an HOC in the DCP setting requires the estimation of the composite DCP channel at the FC for data decoding. To this end, two blind algorithms are proposed: 1) power method, and 2) modified K-means algorithm. The latter algorithm is shown to be computationally efficient and converges significantly faster than the conventional K-means algorithm. Analytical expressions for the probability of error are derived, and it is found that even at moderate to low SNRs, the modified K-means algorithm achieves a probability of error comparable to that achievable with a perfect channel estimate at the FC, while requiring no pilot symbols to be transmitted from the sensor nodes. Also, the problem of signal corruption due to imperfect DCP is investigated, and constellation shaping to minimize the probability of signal corruption is proposed and analyzed. The analysis is validated, and the promising performance of DCP for energy-efficient physical layer data fusion is illustrated, using Monte Carlo simulations.

Universal Hashing for Information-Theoretic Security

The information-theoretic approach to security entails harnessing the correlated randomness available in nature to establish security. It uses tools from information theory and coding and yields provable security, even against an adversary with unbounded computational power. However, the feasibility of this approach in practice depends on the development of efficiently implementable schemes. In this paper, we review a special class of practical schemes for information-theoretic security that are based on 2-universal hash families. Specific cases of secret key agreement and wiretap coding are considered, and general themes are identified. The scheme presented for wiretap coding is modular and can be implemented easily by including an extra preprocessing layer over the existing transmission codes.

Timing Calculations for a General N-Level Dodecagonal Space Vector Structure Using Only Reference Phase Voltages

Multilevel inverters with dodecagonal (12-sided polygon) voltage space vector (SV) structures have advantages like extension of linear modulation range, elimination of fifth and seventh harmonics in phase voltages and currents for the full modulation range including extreme 12-step operation, reduced device voltage ratings, lesser dv/dt stresses on devices and motor phase windings resulting in lower EMI/EMC problems, and lower switching frequency-making it more suitable for high-power drive applications. This paper proposes a simple method to obtain pulsewidth modulation (PWM) timings for a dodecagonal voltage SV structure using only sampled reference voltages. In addition to this, a carrier-based method for obtaining the PWM timings for a general N-level dodecagonal structure is proposed in this paper for the first time. The algorithm outputs the triangle information and the PWM timing values which can be set as the compare values for any carrier-based hardware PWM module to obtain SV PWM like switching sequences. The proposed method eliminates the need for angle estimation, computation of modulation indices, and iterative search algorithms that are typical in multilevel dodecagonal SV systems. The proposed PWM scheme was implemented on a five-level dodecagonal SV structure. Exhaustive simulation and experimental results for steady-state and transient conditions are presented to validate the proposed method.

Campaigning in Heterogeneous Social Networks: Optimal Control of SI Information Epidemics

We study the optimal control problem of maximizing the spread of an information epidemic on a social network. Information propagation is modeled as a susceptible-infected (SI) process, and the campaign budget is fixed. Direct recruitment and word-of-mouth incentives are the two strategies to accelerate information spreading (controls). We allow for multiple controls depending on the degree of the nodes/individuals. The solution optimally allocates the scarce resource over the campaign duration and the degree class groups. We study the impact of the degree distribution of the network on the controls and present results for Erdos-Renyi and scale-free networks. Results show that more resource is allocated to high-degree nodes in the case of scale-free networks, but medium-degree nodes in the case of Erdos-Renyi networks. We study the effects of various model parameters on the optimal strategy and quantify the improvement offered by the optimal strategy over the static and bang-bang control strategies. The effect of the time-varying spreading rate on the controls is explored as the interest level of the population in the subject of the campaign may change over time. We show the existence of a solution to the formulated optimal control problem, which has nonlinear isoperimetric constraints, using novel techniques that is general and can be used in other similar optimal control problems. This work may be of interest to political, social awareness, or crowdfunding campaigners and product marketing managers, and with some modifications may be used for mitigating biological epidemics.

A general theory on media with randomly distributed inclusions .1. The average field behaviors

In this paper, a theory is developed to calculate the average strain field in the materials with randomly distributed inclusions. Many previous researches investigating the average field behaviors were based upon Mori and Tanaka's idea. Since they were restricted to studying those materials with uniform distributions of inclusions they did not need detailed statistical information of random microstructures, and could use the volume average to replace the ensemble average. To study more general materials with randomly distributed inclusions, the number density function is introduced in formulating the average field equation in this research. Both uniform and nonuniform distributions of inclusions are taken into account in detail.

Chemical contaminants, pathogen exposure and general health status of live and beach-cast Washington sea otters (Enhydra lutris kenyoni)

Analyses of blood and liver samples from live captured sea otters and liver samples from beachcast sea otter carcasses off the remote Washington coast indicate relatively low exposure to contaminants, but suggest that even at the low levels measured, exposure may be indicated by biomarker response. Evidence of pathogen exposure is noteworthy - infectious disease presents a potential risk to Washington sea otters, particularly due to their small population size and limited distribution. During 2001 and 2002, 32 sea otters were captured, of which 28 were implanted with transmitters to track their movements and liver and blood samples were collected to evaluate contaminant and pathogen exposure. In addition, liver samples from fifteen beachcast animals that washed ashore between 1991 and 2002 were analyzed to provide historical information and a basis of reference for values obtained from live otters. The results indicate low levels of metals, butyltins, and organochlorine compounds in the blood samples, with many of the organochlorines not detected except polychlorinated biphenyls (PCBs), and a few aromatic hydrocarbons detected in the liver of the live captured animals. Aliphatic hydrocarbons were measurable in the liver from the live captured animals; however, some of these are likely from biogenic sources. A significant reduction of vitamin A storage in the liver was observed in relation to PCB, dibutyltin and octacosane concentration. A significant and strong positive correlation in vitamin A storage in the liver was observed for cadmium and several of the aliphatic hydrocarbons. Peripheral blood mononuclear cell (PBMC) cytochrome P450 induction was elevated in two of 16 animals and may be potentially related to aliphatic and aromatic hydrocarbon exposure. Mean concentration of total butyltin in the liver of the Washington beach-cast otters was more than 15 times lower than the mean concentration reported by Kannan et al. (1998) for Southern sea otters in California. Organochlorine compounds were evident in the liver of beach-cast animals, despite the lack of large human population centers and development along the Washington coast. Concentrations of PCBs and chlordanes (e.g., transchlordane, cis-chlordane, trans-nonachlor, cis-nonachlor and oxychlordane) in liver of Washington beach-cast sea otters were similar to those measured in Aleutian and California sea otters, excluding those from Monterey Bay, which were higher. Mean concentrations of 1,1,1,- trichloro-2,2-bis(p-chlorophyenyl)ethanes (DDTs) were lower, and mean concentrations of cyclohexanes (HCH, e.g., alpha BHC, beta BHC, delta BHC and gamma BHC) were slightly higher in Washington beach-cast otters versus those from California and the Aleutians. Epidemiologically, blood tests revealed that 80 percent of the otters tested positive for morbillivirus and 60 percent for Toxoplasma, the latter of which has been a significant cause of mortality in Southern sea otters in California. This is the first finding of positive morbillivirus titers in sea otters from the Northeast Pacific. Individual deaths may occur from these diseases, perhaps more so when animals are otherwise immuno-compromised or infected with multiple diseases, but a population-threatening die-off from these diseases singly is unlikely while population immunity remains high. The high frequency of detection of morbillivirus and Toxoplasma in the live otters corresponds well with the cause of death of stranded Washington sea otters reported herein, which has generally been attributable to infectious disease. Washington’s sea otter population continues to grow, with over 1100 animals currently inhabiting Washington waters; however, the rate of growth has slowed over recent years. The population has a limited distribution and has not yet reached its carrying capacity and as such, is still considered at high risk to catastrophic events. (PDF contains 189 pages)

Distributed optimization in power networks and general multi-agent systems

The dissertation studies the general area of complex networked systems that consist of interconnected and active heterogeneous components and usually operate in uncertain environments and with incomplete information. Problems associated with those systems are typically large-scale and computationally intractable, yet they are also very well-structured and have features that can be exploited by appropriate modeling and computational methods. The goal of this thesis is to develop foundational theories and tools to exploit those structures that can lead to computationally-efficient and distributed solutions, and apply them to improve systems operations and architecture.

Specifically, the thesis focuses on two concrete areas. The first one is to design distributed rules to manage distributed energy resources in the power network. The power network is undergoing a fundamental transformation. The future smart grid, especially on the distribution system, will be a large-scale network of distributed energy resources (DERs), each introducing random and rapid fluctuations in power supply, demand, voltage and frequency. These DERs provide a tremendous opportunity for sustainability, efficiency, and power reliability. However, there are daunting technical challenges in managing these DERs and optimizing their operation. The focus of this dissertation is to develop scalable, distributed, and real-time control and optimization to achieve system-wide efficiency, reliability, and robustness for the future power grid. In particular, we will present how to explore the power network structure to design efficient and distributed market and algorithms for the energy management. We will also show how to connect the algorithms with physical dynamics and existing control mechanisms for real-time control in power networks.

The second focus is to develop distributed optimization rules for general multi-agent engineering systems. A central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to the given system level objective. Ideally, a system designer seeks to satisfy this goal while conditioning each agent’s control on the least amount of information possible. Our work focused on achieving this goal using the framework of game theory. In particular, we derived a systematic methodology for designing local agent objective functions that guarantees (i) an equivalence between the resulting game-theoretic equilibria and the system level design objective and (ii) that the resulting game possesses an inherent structure that can be exploited for distributed learning, e.g., potential games. The control design can then be completed by applying any distributed learning algorithm that guarantees convergence to the game-theoretic equilibrium. One main advantage of this game theoretic approach is that it provides a hierarchical decomposition between the decomposition of the systemic objective (game design) and the specific local decision rules (distributed learning algorithms). This decomposition provides the system designer with tremendous flexibility to meet the design objectives and constraints inherent in a broad class of multiagent systems. Furthermore, in many settings the resulting controllers will be inherently robust to a host of uncertainties including asynchronous clock rates, delays in information, and component failures.

Voting games with incomplete information

We examine voting situations in which individuals have incomplete information over each others' true preferences. In many respects, this work is motivated by a desire to provide a more complete understanding of so-called probabilistic voting.

Chapter 2 examines the similarities and differences between the incentives faced by politicians who seek to maximize expected vote share, expected plurality, or probability of victory in single member: single vote, simple plurality electoral systems. We find that, in general, the candidates' optimal policies in such an electoral system vary greatly depending on their objective function. We provide several examples, as well as a genericity result which states that almost all such electoral systems (with respect to the distributions of voter behavior) will exhibit different incentives for candidates who seek to maximize expected vote share and those who seek to maximize probability of victory.

In Chapter 3, we adopt a random utility maximizing framework in which individuals' preferences are subject to action-specific exogenous shocks. We show that Nash equilibria exist in voting games possessing such an information structure and in which voters and candidates are each aware that every voter's preferences are subject to such shocks. A special case of our framework is that in which voters are playing a Quantal Response Equilibrium (McKelvey and Palfrey (1995), (1998)). We then examine candidate competition in such games and show that, for sufficiently large electorates, regardless of the dimensionality of the policy space or the number of candidates, there exists a strict equilibrium at the social welfare optimum (i.e., the point which maximizes the sum of voters' utility functions). In two candidate contests we find that this equilibrium is unique.

Finally, in Chapter 4, we attempt the first steps towards a theory of equilibrium in games possessing both continuous action spaces and action-specific preference shocks. Our notion of equilibrium, Variational Response Equilibrium, is shown to exist in all games with continuous payoff functions. We discuss the similarities and differences between this notion of equilibrium and the notion of Quantal Response Equilibrium and offer possible extensions of our framework.

Optimum linear coding for additive noise systems using information feedback

The feedback coding problem for Gaussian systems in which the noise is neither white nor statistically independent between channels is formulated in terms of arbitrary linear codes at the transmitter and at the receiver. This new formulation is used to determine a number of feedback communication systems. In particular, the optimum linear code that satisfies an average power constraint on the transmitted signals is derived for a system with noiseless feedback and forward noise of arbitrary covariance. The noisy feedback problem is considered and signal sets for the forward and feedback channels are obtained with an average power constraint on each. The general formulation and results are valid for non-Gaussian systems in which the second order statistics are known, the results being applicable to the determination of error bounds via the Chebychev inequality.

Bassenthwaite Lake: a general assessment of environmental and biological features and their susceptibility to change

Bassenthwaite (Lake) is one of the larger Cumbrian lakes, certainly one of the most distinctive, and of considerable conservation and amenity value. Although its shores lack sizeable settlements, its main inflow receives sewage effluent from a major tourist centre (Keswick) and is subject to episodic floods. These influences, the growing development of leisure activities at the lake (e.g. sailing, time-share units), and recent road-construction, have led to past appraisals of ecological impacts and lake management. The lake has not been the subject of intense and long-term ecological study, but much scattered information exists that is relevant to future management decisions. In the present Report, commissioned by North West Water, such information - published and unpublished - is surveyed. Especial attention is given to evidence bearing on susceptibility to change, affecting the lake environment and its biota or species of conservation interest. Extensive use has been made of the results of a recent (1986-7) seasonal survey by the FBA.

A general assessment of environmental and biological features of Windermere and their susceptibility to change

Bassenthwaite (Lake) is one of the larger Cumbrian lakes, certainly one of the most distinctive, and of considerable conservation and amenity value. Although its shores lack sizeable settlements, its main inflow receives sewage effluent from a major tourist centre (Keswick) and is subject to episodic floods. These influences, the growing development of leisure activities at the lake (e.g. sailing, time-share units), and recent road-construction, have led to past appraisals of ecological impacts and lake management. The lake has not been the subject of intense and long-term ecological study, but much scattered information exists that is relevant to future management decisions. In the present Report, commissioned by North West Water, such information - published and unpublished - is surveyed. Especial attention is given to evidence bearing on susceptibility to change, affecting the lake environment and its biota or species of conservation interest. Extensive use has been made of the results of a recent (1986-7) seasonal survey by the FBA.