The thesis describes a new database of uzun havas, a non-metered structured improvisation form in Turkish folk music, and a system, which uses Variable-Length Markov Models (VLMMs) to predict the melody in the uzun hava form. The database consists of 77 songs, encompassing 10849 notes, and it is used to train multiple viewpoints, where each event in a musical sequence are represented by parallel descriptors such as Durations and Notes. The thesis also introduces pitch-related viewpoints that are specifically aimed to model the unique melodic properties of makam music. The predictability of the system is quantitatively evaluated by an entropy based scheme. In the experiments, the results from the pitch-related viewpoints mapping 12-tone-scale of Western classical theory and 17 tone-scale of Turkish folk music are compared. It is shown that VLMMs are highly predictive in the note progressions of the transcriptions of uzun havas. This suggests that VLMMs may be applied to makam-based and non-metered musical forms, in addition to Western musical styles. To the best of knowledge, the work presents the first symbolic, machine-readable database and the first application of computational modeling in Turkish folk music.

This dissertation consists of three essays that apply both economic theory and econometric methods to understand design and dynamics of institutions. In particular, it studies how institutions aggregate information and deal with uncertainty and attempts to derive implications for optimal institution design. Here is a brief summary of the essays. In many economic, political and social situations where the environment changes in a random fashion necessitating costly action we face a choice of both the timing of the action as well as choosing the optimal action. In particular, if the stochastic environment possesses the property that the next environmental change becomes either more or less likely as more time passes since the last change (in other words the hazard rate of environmental change is not constant over time), then the timing of the action takes on special importance. In the first essay, joint with Maxwell B Stinchcombe, we model and solve a dynamic decision problem in a semi-Markov environment. We find that if the arrival times for state changes do not follow a memoryless process, time since the last observed change of state, in addition to the current state, becomes a crucial variable in the decision. We characterize the optimal policy and the optimal timing of executing that policy in the differentiable case by a set of first order conditions of a relatively simple form. They show that both in the case of increasing and decreasing hazard rates, the optimal response may be to wait before executing a policy change. The intuitive explanation of the result has to do with the fact that waiting reveals information about the likelihood of the next change occurring, hence waiting is valuable when actions are costly. This result helps shed new light on the structure of optimal decisions in many interesting problems of institution design, including the fact that constitutions often have built-in delay mechanisms to slow the pace of legislative change. Our model results could be used to characterize optimal timing rules for constitutional amendments. The paper also contributes to generalize the methodology of semi-Markov decision theory by formulating a dynamic programming set-up that looks to solve the timing-of-action problem whereas the existing literature looks to optimize over a much more limited set of policies where the action can only be taken at the instant when the state changes. In the second essay, we extend our research to situations, where the current choice of action influences the future path of the stochastic process, and apply it to the legal framework surrounding environmental issues, particularly to the ‘Precautionary Principle' as applied to climate change legislation. We represent scientific uncertainty about environmental degradation using the concept of 'ambiguity' and show that ambiguity aversion generates a 'precautionary effect'. As a result, justification is provided for the Precautionary Principle that is different from the ones provided by expected utility theory. This essay serves both as an application of the general theoretical results derived in the first essay and also stands alone as an analysis of a substantive question about environmental law. Prediction markets have attracted public attention in recent years for making accurate predictions about election outcomes, product sales, film box office and myriad other variables of interest and many believe that they will soon become a very important decision support system in a wide variety of areas including governance, law and industry. For successful design of these markets, a thorough understanding of the theoretical and empirical foundations of such markets is necessary. But the information aggregation process in these markets is not fully understood yet. There remains a number of open questions. The third essay, joint with Robert Lieli, attempts to analyze the direction and timing of information flow between prices, polls, and media coverage of events traded on prediction markets. Specifically, we examine the race between Barack Obama and Hillary Clinton in the 2008 Democratic primaries for presidential nomination. Substantively, we ask the following question: (i) Do prediction market prices have information that is not reflected in viii contemporaneous polls and media stories? (ii) Conversely, do prices react to information that appears to be news for pollsters or is prominently featured by the media? Quantitatively, we construct time series variables that reflect the "pollster's surprise" in each primary election, measured as the difference between actual vote share and vote share predicted by the latest poll before the primary, as well as indices that describe the extent of media coverage received by the candidates. We carry out Granger Causality tests between the day-to-day percentage change in the price of the "Obama wins nomination" security and these information variables. Some key results from our exercise can be summarized as follows. There seems to be mutual (two-way) Granger causality between prediction market prices and the surprise element in the primaries. There is also evidence of one-way Granger causality in the short run from price changes towards media news indices. These results suggest that prediction market prices anticipate at least some of the discrepancy between the actual outcome and the latest round of polls before the election. Nevertheless, prices also seem to be driven partly by election results, suggesting that there is an element of the pollster’s surprise that is genuine news for the market as well. / text

Estimation of the number of hidden states is challenging in hidden Markov models. Motivated by the analysis of a specific type of cell adhesion experiments, a new frame-work based on hidden Markov model and double penalized order selection is proposed. The order selection procedure is shown to be consistent in estimating the number of states. A modified Expectation-Maximization algorithm is introduced to efficiently estimate parameters in the model. Simulations show that the proposed framework outperforms existing methods. Applications of the proposed methodology to real data demonstrate the accuracy of estimating receptor-ligand bond lifetimes and waiting times which are essential in kinetic parameter estimation. The second part of the thesis is concerned with prediction of a deterministic response function y at some untried sites given values of y at a chosen set of design sites. The intended application is to computer experiments in which y is the output from a computer simulation and each design site represents a particular configuration of the input variables. A Bayesian version of the cubic spline method commonly used in numerical analysis is proposed, in which the random function that represents prior uncertainty about y is taken to be a specific stationary Gaussian process. An MCMC procedure is given for updating the prior given the observed y values. Simulation examples and a real data application are given to compare the performance of the Bayesian cubic spline with that of two existing methods.

This dissertation focuses on issues associated with the value of information in models of sequential decision making under uncertainty. All of these issues are motivated by inventory management problems. First, we study the effect of the accuracy of inventory counts on system performance when using a zero-memory controller in an inventory system that is modeled as a partially observed Markov decision process (POMDP). We derive conditions for which improving the accuracy of inventory counts will either (i) improve system performance, (ii) degrade system performance or (iii) will not affect system performance. With a computational study, we determine the range of profitability impacts that result from inaccurate inventory counts when using reasonable zero-memory control policies. Second, we assess the value of demand observation quality in an inventory system with Markovian demand and lost sales. Again, the POMDP serves as a problem model, and we develop computationally tractable suboptimal algorithms to enable the computation of effective lower bounds on system profitability when demand observations are noise-corrupted. We then extend our results toconsider the effects that product substitution has on system performance. We show that systems with low demand variability, high holding cost levels, and high levels of substitution benefit more from demand bservability than systems with high demand variability, low holding cost levels, and low levels of substitution. Third, to enhance our understanding of sequential inventory control with substitutable products, we analyze a two-item inventory problem with known deterministic primary demand, but stochastic one-way substitution. We model this problem as a MDP and show that a decision rule that minimizes the single period cost function, when applied at every decision epoch over the infinite horizon, is an optimal policy for the infinite horizon problem. A definition of increased substitutability is presented, and it is shown that increased substitutability never increases optimal expected total discounted cost.

Recently in robotics, substantial efforts have been invested on critical applications such as military, nursing, and search-and-rescue. These applications are critical in a sense that the robots may directly deal with human lives in life-or-death situations, and they are therefore required to make highly intelligent decisions as rapidly as possible. The intelligence we are looking for in this type of situations is proactiveness: the ability to anticipate as well as improvise. Anticipation here means that the robot can assess the current situation, predict the future consequence of the situation, and execute an action to have desired outcome based on the determined assessment and prediction. On the other hand, improvisation is performed when the consequence of the situation is not fully known. In other words, it is the ability to deal with a novel situation based on knowledge or skill being acquired before. In this presentation, we introduce a biologically inspired computational model of proactive intelligent behavior for robots. Integrating multiple levels of machine learning techniques such as temporal difference learning, instance-based learning, and partially observable Markov decision process, aggregated episodic memories are processed in order to accomplish anticipation as well as improvisation. How this model can be implemented within a software architectural framework and integrated into a physically realized robotic system is also explained. The experimental results using a real robot and high fidelity 3D simulators are then presented in order to help us understand how extended experience of a robot influences its ability to behave proactively.

Markov partitions provide a 'good' mechanism of symbolic dynamics for uniformly hyperbolic systems, forming the classical foundation for the thermodynamic formalism in this setting, and remaining useful in the modern theory. Usually, however, one takes Bowen's 1970's general construction for granted, or restricts to cases with simpler geometry (as on surfaces) or more algebraic structure. This thesis examines several questions on the algorithmic content of (topological) Markov partitions, starting with the pointwise, entropy-like, topological conjugacy invariant known as orbit complexity. The relation between orbit complexity de nitions of Brudno and Galatolo is examined in general compact spaces, and used in Theorem 2.0.9 to bound the decrease in some of these quantities under semiconjugacy. A corollary, and a pointwise analogue of facts about metric entropy, is that any Markov partition produces symbolic dynamics matching the original orbit complexity at each point. A Lebesgue-typical value for orbit complexity near a hyperbolic attractor is also established (with some use of Brin-Katok local entropy), and is technically distinct from typicality statements discussed by Galatolo, Bonanno and their co-authors. Both our results are proved adapting classical arguments of Bowen for entropy. Chapters 3 and onwards consider the axiomatisation and computable construction of Markov partitions. We propose a framework of 'abstract local product structures'

Thesis (Ph.D.) - Carleton University, 2005. / Includes bibliographical references (p. 168-173). Also available in electronic format on the Internet.

Thesis (Ph. D.)--Ohio State University, 2005. / Title from first page of PDF file. Document formatted into pages; contains xiv, 155 p.; also includes graphics (some col.). Includes bibliographical references (p. 147-155). Available online via OhioLINK's ETD Center

When designing intelligent agents that must solve sequential decision problems, often we do not have enough knowledge to build a complete model for the problems at hand. Reinforcement learning enables an agent to learn behavior by acquiring experience through trial-and-error interactions with the environment. However, knowledge is usually built from scratch and learning the optimal policy may take a long time. In this work, we improve the learning performance by exploring transfer learning; that is, the knowledge acquired in previous source tasks is used to accelerate learning in new target tasks. If the tasks present similarities, then the transferred knowledge guides the agent towards faster learning. We explore the use of a relational representation that allows description of relationships among objects. This representation simplifies the use of abstraction and the extraction of the similarities among tasks, enabling the generalization of solutions that can be used across different, but related, tasks. This work presents two model-free algorithms for online learning of abstract policies: AbsSarsa(λ) and AbsProb-RL. The former builds a deterministic abstract policy from value functions, while the latter builds a stochastic abstract policy through direct search on the space of policies. We also propose the S2L-RL agent architecture, containing two levels of learning: an abstract level and a ground level. The agent simultaneously builds a ground policy and an abstract policy; not only the abstract policy can accelerate learning on the current task, but also it can guide the agent in a future task. Experiments in a robotic navigation environment show that these techniques are effective in improving the agents learning performance, especially during the early stages of the learning process, when the agent is completely unaware of the new task. / Na construção de agentes inteligentes para a solução de problemas de decisão sequenciais, o uso de aprendizado por reforço é necessário quando o agente não possui conhecimento suficiente para construir um modelo completo do problema. Entretanto, o aprendizado de uma política ótima é em geral muito lento pois deve ser atingido através de tentativa-e-erro e de repetidas interações do agente com o ambiente. Umas das técnicas para se acelerar esse processo é possibilitar a transferência de aprendizado, ou seja, utilizar o conhecimento adquirido para se resolver tarefas passadas no aprendizado de novas tarefas. Assim, se as tarefas tiverem similaridades, o conhecimento prévio guiará o agente para um aprendizado mais rápido. Neste trabalho é explorado o uso de uma representação relacional, que explicita relações entre objetos e suas propriedades. Essa representação possibilita que se explore abstração e semelhanças estruturais entre as tarefas, possibilitando a generalização de políticas de ação para o uso em tarefas diferentes, porém relacionadas. Este trabalho contribui com dois algoritmos livres de modelo para construção online de políticas abstratas: AbsSarsa(λ) e AbsProb-RL. O primeiro constrói uma política abstrata determinística através de funções-valor, enquanto o segundo constrói uma política abstrata estocástica através de busca direta no espaço de políticas. Também é proposta a arquitetura S2L-RL para o agente, que possui dois níveis de aprendizado: o nível abstrato e o nível concreto. Uma política concreta é construída simultaneamente a uma política abstrata, que pode ser utilizada tanto para guiar o agente no problema atual quanto para guiá-lo em um novo problema futuro. Experimentos com tarefas de navegação robótica mostram que essas técnicas são efetivas na melhoria do desempenho do agente, principalmente nas fases inicias do aprendizado, quando o agente desconhece completamente o novo problema.

Autonomous vehicles is soon a reality in the every-day life. Though before it is used commercially the vehicles need to be proven safe. The current standard for functional safety on roads, ISO 26262, does not include autonomous vehicles at the moment, which is why in this project an approach using semi-Markov models is used to assess safety. A semi-Markov process is a stochastic process modelled by a state space model where the transitions between the states of the model can be arbitrarily distributed. The approach is realized as a MATLAB tool where the user can use a steady-state based analysis called a Loss and Risk based measure of safety to assess safety. The tool works and can assess safety of semi-Markov systems as long as they are irreducible and positive recurrent. For systems that fulfill these properties, it is possible to draw conclusions about the safety of the system through a risk analysis and also about which autonomous driving level the system is in through a sensitivity analysis. The developed tool, or the approach with the semi-Markov model, might be a good complement to ISO 26262.