2025
[ICONIP 2025] Ryo Iwaki, Takayuki Osogami, "Distorted Distributional Policy Evaluation for Offline Reinforcement Learning", the 32nd International Conference on Neural Information Processing (ICONIP 2025), Okinawa, Japan, November 2025.
[ICAPS 2025] Alexander Zadorojniy Orit Davidovich Takayuki Osogami, "Going Topological in Multi-risk Extended Markov Ratio Decision Processes", the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025), Melbourne, Australia, November 2025.
2024
[NeurIPS 2024] Tomoya Sakai, Haoxiang Qiu, Takayuki Katsuki, Daiki Kimura, Takayuki Osogami, Tadanobu Inoue, "A Surprisingly Simple Approach to Generalized Few-Shot Semantic Segmentation", The Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS 2024), Vancouver, Canada, December 2024. PDF
2023
[ICML 2023a] Takayuki Katsuki and Takayuki Osogami, “Regression with sensor data containing incomplete observations,” Proceedings of the 40th International Conference on Machine Learning (ICML 2023), pages 15911–15927, Honolulu, HI, USA, July 2023. PDF
[ICML 2023b] Hiroshi Kajino, Kohei Miyaguchi, and Takayuki Osogami, “Biases in evaluation of molecular optimization methods and bias reduction strategies,” Proceedings of the 40th International Conference on Machine Learning (ICML 2023), pages 15567-15585, Honolulu, HI, USA, July 2023. PDF
[IJCAI-23a] Takayuki Osogami, Segev Wasserkrug, and Elisheva Shamash, “Learning efficient truthful mechanisms for trading networks,” Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), pages 2862-2869, Macao, China, August 2023. PDF
[IJCAI-23b] Alexander Zadorojniy, Takayuki Osogami, and Orit Davidovich, “A rigorous risk-aware linear approach to extended Markov ratio decision processes with embedded learning,” Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), pages 5475-5483, Macao, China, August 2023. PDF
[AAMAS 2023] Nicolò Cesa-Bianchi, Tommaso Cesari, Takayuki Osogami, Marco Scarsini, and Segev Wasserkrug, "Learning the Stackelberg Equilibrium in a Newsvendor Game," Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), pages 242–250, London, UK, May 2023. PDF
2021
[AAAI-21] Takayuki Osogami, "Second Order Techniques for Learning Time-series with Structural Breaks," Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21), pages 9259-9267, February 2021. PDF
Abstract We study fundamental problems in learning nonstationary time-series: how to effectively regularize time-series models and how to adaptively tune forgetting rates. The effectiveness of L2 regularization depends on the choice of coordinates, and the variables need to be appropriately normalized. In nonstationary environment, however, what is appropriate can vary over time. Proposed regularization is invariant to the invertible linear transformation of coordinates, eliminating the necessity of normalization. We also propose an ensemble learning approach to adaptively tuning the forgetting rate and regularization-coefficient. We train multiple models with varying hyperparameters and evaluate their performance by the use of multiple hyper forgetting rates. At each step, we choose the best performing model on the basis of the best performing hyper forgetting rate. The effectiveness of the proposed approaches is demonstrated with real time-series.
2020
[AAAI-20] Takayuki Osogami, "Uncorrected least-squares temporal difference with lambda-return," Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20), pages 5323-5330, New York, NY, USA, February 2020. PDF
Abstract Temporal difference, TD(lambda), learning is a foundation of reinforcement learning and also of interest in its own right for the tasks of prediction. Recently, true online TD(lambda) has been shown to closely approximate the "forward view" at every step, while conventional TD(lambda) does this only at the end of an episode. We re-examine least-squares temporal difference, LSTD(lambda), which has been derived from conventional TD(lambda). We design Uncorrected LSTD(lambda) in such a way that, when lambda=1, Uncorrected LSTD(1) is equivalent to the least-squares method for the linear regression of Monte Carlo (MC) return at every step, while conventional LSTD(1) has this equivalence only at the end of an episode, since the MC return is corrected to be unbiased. We prove that Uncorrected LSTD(lambda) can have smaller variance than conventional LSTD(lambda), and this allows Uncorrected LSTD(lambda) to sometimes outperform conventional LSTD(lambda) in practice. When lambda=0, however, Uncorrected LSTD(0) is not equivalent to LSTD. We thus also propose Mixed LSTD(lambda), which matches conventional LSTD(lambda) at lambda=0 and Uncorrected LSTD(lambda) at lambda=1. In numerical experiments, we study how the three LSTD(lambda)s behave under limited training data.
2019
[ACML 2019] Takayuki Osogami and Toshihiro Takahashi, "Real-time tree search with pessimistic scenarios: Winning the NeurIPS 2018 Pommerman Competition," Proceedings of the 11th Asian Conference on Machine Learning (ACML 2019), pages 583-598, Nagoya, Japan, Nobember 2019. PDF
Abstract Autonomous agents need to make decisions in a sequential manner, under partially observable environment, and in consideration of how other agents behave. In critical situations, such decisions need to be made in real time for example to avoid collisions and recover to safe conditions. We propose a technique of tree search where a deterministic and pessimistic scenario is used after a specified depth. Because there is no branching with the deterministic scenario, the proposed technique allows us to take into account the events that can occur far ahead in the future. The effectiveness of the proposed technique is demonstrated in Pommerman, a multi-agent environment used in a NeurIPS 2018 competition, where the agents that implement the proposed technique have won the first and third places.
[AAAI-19] Takayuki Osogami and Rudy Raymond, "Determinantal reinforcement learning," Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), pages 4659-4666, Honolulu, HI, USA, January 2019. PDF
Abstract We study reinforcement learning for controlling multiple agents in a collaborative manner. In some of those tasks, it is insufficient for the individual agents to take relevant actions, but those actions should also have diversity. We propose the approach of using the determinant of a positive semidefinite matrix to approximate the action-value function in reinforcement learning, where we learn the matrix in a way that it represents the relevance and diversity of the actions. Experimental results show that the proposed approach allows the agents to learn a nearly optimal policy approximately ten times faster than baseline approaches in benchmark tasks of multi-agent reinforcement learning. The proposed approach is also shown to achieve the performance that cannot be achieved with conventional approaches in partially observable environment with exponentially large action space.
2018
[ICDM 2018] Takayuki Katsuki, Takayuki Osogami, Akira Koseki, Masaki Ono, Michiharu Kudo, Masaki Makino, and Atsushi Suzuki, "Time discounting convolution for event sequences with ambiguous timestamps," Proceedings of the IEEE International Conference on Data Mining (ICDM 2018), Singapore, November 2018.
Abstract A method is presented for modeling temporal event sequences, where events are recorded with ambiguous timestamps, unlike in ordinary time-series data. Small time-shifts in the observed sequences of events have no significant effect, and directly inputting timestamps or time durations into a model is not effective. The criteria that we require for modeling such temporal event sequences are providing robustness against time-shifts or uncertainty in timestamps as well as maintaining the essential capabilities of time-series models, i.e., forgetting meaningless past information and handling infinite sequences.
To meet these criteria, we develop a time discounting convolution method and a dynamic pooling mechanism. The time discounting convolution has a uni-directional convolution mechanism across time with two kinds of parameter sharing for efficiently representing the dependency between events in a time-shift invariant manner. It also has a mechanism of forgetting by discounting the effects of past observations. Dynamic pooling provides robustness against the uncertainty in timestamps and enhances the time-discounting capability by dynamically changing the window size in pooling operations. In our learning algorithm, the time discounting convolution and dynamic pooling mechanisms play critical roles in handling infinite and variable length sequences.
We apply the proposed method to prediction of event sequences with ambiguous timestamps, i.e., risk prediction from electronic health records. We also validate the general applicability of the proposed method to ordinary time-series data. Numerical experiments on the real world datasets demonstrate the advantages of our convolutional structure and dynamic pooling in prediction performance.
[PacificVis 2018] Kun Zhao, Takayuki Osogami, Tetsuro Morimura, "Events-based visual analytics for team-based invasion sports", Proceedings of the 11th IEEE Pacific Visualization Symposium (PacificVis 2018), Kobe, Japan, April 2018 (poster).
Abstract Traditional techniques for evaluating team performance in team-based invasion sports (e.g. soccer, basketball etc.) rely on the trajectories (sequences of locations) of all players. However, such trajectory data is huge and noisy, making the analysis difficult. In this paper, we focus our research on events occurred in sports and analyze the match by evaluating the value of those events. We propose a new method to extract significant events based on statistical features and evaluate the event value based on reinforcement learning. The evaluated value is visually inspected to understand how much each event can potentially contribute to scores. The experimental results with real soccer data show the effectiveness of the proposed approach.
[AAAI-18] Takayuki Osogami, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Maehara, "Dynamic determinantal point processes," Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), pages 3868-3875, New Orleans, Lousiana, USA, February 2018. PDF
Abstract The determinantal point process (DPP) has been receiving increasing attention in machine learning as a generative model of subsets consisting of relevant and diverse items. Recently, there has been a significant progress in developing efficient algorithms for learning the kernel matrix that characterizes a DPP. Here, we propose a dynamic DPP, which is a DPP whose kernel can change over time, and develop efficient learning algorithms for the dynamic DPP. In the dynamic DPP, the kernel depends on the subsets selected in the past, but we assume a particular structure in the dependency to allow efficient learning. We also assume that the kernel has a low rank and exploit a recently proposed learning algorithm for the DPP with low-rank factorization, but also show that its bottleneck computation can be reduced from O(M^2 K) time to O(M K^2) time, where M is the number of items under consideration, and $K$ is the rank of the kernel, which can be set smaller than M by orders of magnitude.
2017
[TSW 2017] Kun Zhao, Takayuki Osogami, and Rudy Raymond, "Fluid simulation with dynamic Boltzmann machine in batch manner," NIPS Time Series Workshop 2017, Long Beach, CA, USA, December 2017. PDF
Abstract Due to the complexity of solving Navier-Stokes equations, fluid simulation requires a significant amount of computational resources. In recent work [1], a machine learning technique has been applied not only to approximate but also to accelerate this complex and time-consuming computation. However, the prior work has not fully taken into account the fact that fluid dynamics is time-varying and involves dynamic features. In this work, we use a time-series machine learning technique, specifically the dynamic Boltzmann machine (DyBM) [6], to approximate fluid simulations. To enhance the training performance and accuracy, we develop a batch learning manner for DyBM instead of online learning and also add a low-rank approximation for reduced memory use and faster inference. We also propose a learning algorithm for DyBM to better learn and generate an initial part of the time-series. The experimental results suggest the efficiency and accuracy of our proposed techniques.
[TSW 2017] Rudy Raymond, Takayuki Osogami and Sakyasingha Dasgupta, "Dynamic Boltzmann machines for second order moments and generalized Gaussian distributions," NIPS Time Series Workshop 2017, Long Beach, CA, USA, December 2017. PDF
Abstract Dynamic Boltzmann Machine (DyBM) has been shown highly efficient to predict time-series data. Gaussian DyBM is a DyBM that assumes the predicted data is generated by a Gaussian distribution whose first-order moment (mean)dynamically changes over time but its second-order moment (variance) is fixed. However, in many financial applications, the assumption is quite limiting in two aspects. First, even when the data follows a Gaussian distribution, its variance may change over time. Such variance is also related to important temporal economic indicators such as the market volatility. Second, financial time-series data often requires learning datasets generated by the generalized Gaussian distribution with an additional shape parameter that is important to approximate heavy-tailed distributions. Addressing those aspects, we show how to extend DyBM that results in significant performance improvement in predicting financial time-series data.
[WSC 2017] Kun Zhao and Takayuki Osogami, "Modeling fluid simulation with dynamic Boltzmann machine," Proceedings of the 2017 Winter Simulation Conference 2017, pages 4503-4505, Las Vegas, NV, USA, December 2017. PDF
Abstract Fluid simulation requires a significant amount of computational resources because of the complexity of solving Navier-Stokes equations. In recent work [Ladický et al., 2015], a machine learning technique has been applied to only approximate, but to also accelerate, this complex and time-consuming computation. However, the prior work has not fully taken into account the fact that fluid dynamics is time-varying and involves dynamic features. In this work, we use a time-series machine learning technique, specifically the dynamic Boltzmann machine (DyBM) [Osogami et al., 2015], to approximate fluid simulations. We also propose a learning algorithm for DyBM to better learn and generate an initial part of the time-series. The experimental results suggest the efficiency and accuracy of our proposed techniques.
[ICML 2017] Takayuki Osogami, Hiroshi Kajino, Taro Sekiyama, "Bidirectional learning for time-series models with hidden units," Proceedings of the 34th International Conference on Machine Learning (ICML 2017), pages 2711-2720, Sydney, Australia, August 2017. PDF
Abstract Hidden units can play essential roles in modeling time-series having
long-term dependency or non-linearity but make it difficult to learn associated parameters. Here we propose a way to learn such a time-series model by training a backward model for the time-reversed time-series, where the backward model has a common set of parameters as the original (forward) model. Our key observation is that only a subset of the parameters is hard to learn, and that subset is complementary between the forward model and the backward model. By training both of the two models, we can effectively learn the values of the parameters that are hard to learn if only either of the two models is trained. We apply bidirectional learning to a dynamic Boltzmann machine extended with hidden units. Numerical experiments with synthetic and real datasets clearly demonstrate advantages of bidirectional learning.
[AAAI-17] Sakyasingha Dasgupta and Takayuki Osogami, "Nonlinear dynamic Boltzmann machines for time-series prediction," Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), pages 1833-1839, San Francisco, CA, January 2017. PDF
Abstract The dynamic Boltzmann machine (DyBM) has been proposed as a stochastic generative model of multi-dimensional time series, with an exact, learning rule that maximizes the log-likelihood of a given time series. The DyBM, however, is defined only for binary valued data, without any nonlinear hidden units. Here, in our first contribution, we extend the DyBM to deal with real valued data. We present a formulation called Gaussian DyBM, that can be seen as an extension of a vector autoregressive (VAR) model. This uses, in addition to standard (explanatory) variables, components that captures long term dependencies in the time series. In our second contribution, we extend the Gaussian DyBM model with a recurrent neural network (RNN) that controls the bias input to the DyBM units. We derive a stochastic gradient update rule such that, the output weights from the RNN can also be trained online along with other DyBM parameters. Furthermore, this acts as nonlinear hidden layer extending the capacity of DyBM and allows it to model nonlinear components in a given time-series. Numerical experiments with synthetic datasets show that the RNN-Gaussian DyBM improves predictive accuracy upon standard VAR by up to \approx 35%. On real multi-dimensional time-series prediction, consisting of high nonlinearity and non-stationarity, we demonstrate that this nonlinear DyBM model achieves significant improvement upon state of the art baseline methods like VAR and long short-term memory (LSTM) networks at a reduced computational cost.
2016
Takayuki Osogami,"Learning binary or real-valued time-series via spike-timing dependent plasticity," Computing with Spikes NIPS workshop, Barcelona, Spain, December 2016. PDF
Abstract A dynamic Boltzmann machine (DyBM) has been proposed as a model of a spiking neural network, and its learning rule of maximizing the log-likelihood of given time-series has been shown to exhibit key properties of spike-timing dependent plasticity (STDP), which had been postulated and experimentally confirmed in the field of neuroscience as a learning rule that refines the Hebbian rule. Here, we relax some of the constraints in the DyBM in a way that it becomes more suitable for computation and learning. We show that learning the DyBM can be considered as logistic regression for binary-valued time-series. We also show how the DyBM can learn real-valued data in the form of a Gaussian DyBM and discuss its relation to the vector autoregressive (VAR) model. The Gaussian DyBM extends the VAR by using additional explanatory variables, which correspond to the eligibility traces of the DyBM and capture long term dependency of the time-series. Numerical experiments show that the Gaussian DyBM significantly improves the predictive accuracy over VAR.
[ICPR16] Sakyasingha Dasgupta, Takayuki Yoshizumi, Takayuki Osogami, "Regularized dynamic Boltzmann machine with delay pruning for unsupervised learning of temporal sequences," Proceedings of the 23rd International Conference on Pattern Recognition (ICPR 2016), pages 1201-1206, Cancun, Mexico, December 2016. PDF
Abstract We introduce Delay Pruning, a simple yet powerful technique to regularize dynamic Boltzmann machines (DyBM). The recently introduced DyBM provides a particularly structured Boltzmann machine, as a generative model of a multi-dimensional time-series. This Boltzmann machine can have infinitely many layers of units but allows exact inference and learning based on its biologically motivated structure. DyBM uses the idea of conduction delays in the form of fixed length first-in first-out (FIFO) queues, with a neuron connected to another via this FIFO queue, and spikes from a pre-synaptic neuron travel along the queue to the post-synaptic neuron with a constant period of delay. Here, we present Delay Pruning as a mechanism to prune the lengths of the FIFO queues (making them zero) by setting some delay lengths to one with a fixed probability, and finally selecting the best performing model with fixed delays. The uniqueness of structure and a non-sampling based learning rule in DyBM, make the application of previously proposed regularization techniques like Dropout or DropConnect difficult, leading to poor generalization. First, we evaluate the performance of Delay Pruning to let DyBM learn a multidimensional temporal sequence generated by a Markov chain. Finally, we show the effectiveness of delay pruning in learning high dimensional sequences using the moving MNIST dataset, and compare it with Dropout and DropConnect methods.
[IJCAI16a] Shohei Ohsawa, Yachiko Obara, and Takayuki Osogami, "Gated probabilistic matrix factorization: Learning users' attention from missing values", The 25th International Joint Conference on Artificial Intelligence (IJCAI-16), pages 1888-1894, New York, NY, USA, July 2016. PDF
Abstract Recommender systems rely on techniques of predicting the ratings that users would give to yet unconsumed items. Probabilistic matrix factorization (PMF) is a standard technique for such prediction and makes a prediction on the basis of an underlying probabilistic generative model of the behavior of users. We investigate a new model of users’consumption and rating, where a user tends to consume an item that emphasizes those features that the user seeks to enjoy, and the ratings of the users are more strongly affected by those features than others. We incorporate this new user model into PMF and show that the resulting method, Gated PMF (GPMF), improves the predictive accuracy by several percent on standard datasets. GPMF is widely applicable, as it is trained only with the ratings given by users and does not rely on any auxiliary data.
[IJCAI16b] Takashi Imamichi, Takayuki Osogami, and Rudy Raymond, "Truncating shortest path search for efficient map-matching", Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-16), pages 589-595, New York, NY, USA, July 2016. PDF
Abstract We study the problem of map-matching, or finding the route on a road network from a trace of noisy and sparse observed points, particularly when a huge number of points are given. The algorithms based on Hidden Markov Models (HMMs) are known to achieve high accuracy for noisy and sparse data but suffer from high computational cost. We find that the bottleneck of the HMM-based map-matching is in the shortest path search for calculating transition probabilities. We propose a technique to truncate the shortest path search before finding all the shortest paths in the HMM-based map-matching without losing accuracy. We run the one-to-many shortest path search on the reversed network and terminate the search based on the log likelihood of the Viterbi algorithm. Computational experiments show that the proposed approaches can reduce the computational cost by a factor of at least 5.4.
[AAAI16] Makoto Otsuka and Takayuki Osogami, "A deep choice model," Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI-16), pages 850-856, Phoenix, AZ, January 2016. PDF
Abstract Human choice is complex in two ways. First, human choice often shows complex dependency on available alternatives. Second, human choice is often made after examining complex items such as images. The recently proposed choice model based on the restricted Boltzmann machine (RBM choice model) has been proved to represent three typical phenomena of human choice, which addresses the first complexity. We extend the RBM choice model to a deep choice model (DCM) to deal with the features of items, which are ignored in the RBM choice model. We then use deep learning to extract latent features from images and plug those latent features as input to the DCM. Our experiments show that the DCM can adequately learn the choice that involves both of two complexities in human choice.
2015
[ICML15] Takayuki Osogami, "Robust partially observable Markov decision process," Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), pages 106–115, Lille, France, July 2015. PDF
Abstract We seek to find the robust policy that maximizes the expected cumulative
reward for the worst case when a partially observable Markov decision process (POMDP) has uncertain parameters whose values are only known to be in a given region. We prove that the robust value function, which represents the expected cumulative reward that can be obtained with the robust policy, is convex with respect to the belief state. Based on the convexity, we design a value-iteration algorithm for finding the robust policy. We prove that our value iteration converges for an infinite horizon. We also design point-based value iteration for fining the robust policy more efficiency possibly with approximation. Numerical experiments show that our point-based value iteration can adequately find robust policies.
2014
[NIPS14] Takayuki Osogami and Makoto Otsuka, "Restricted Boltzmann machines modeling human choice," Advances in Neural Information Processing Systems, 27 (NIPS 2014), pages 73-81, Montreal, Quebec, Canada, December 2014. PDF
Abstract We extend the multinomial logit model to represent some of the empirical phenomena that are frequently observed in the choice made by humans. These phenomena include the similarity effect, the attraction effect, and the compromise effect. We formally quantify the strength of these phenomena that can be represented by our choice model, which illuminates the flexibility of our choice model. We then show that our choice model can be represented as a restricted Boltzmann machine and that its parameters can be learned effectively from data. Our numerical experiments with real data of human choice suggest that we can train our choice model in such a way that it represents the typical phenomena of choice.
[PAIS14] Takayuki Osogami and Rudy Raymond, "Efficient policy iteration for periodic Markov decision processes," Proceedings of the Eighth International Conference on Prestigious Applications of Intelligent Systems, pages 1167–1172, Prague, Czech Republic, August 2014. PDF
Abstract We propose a solution to a new problem that is faced by steelworks, who own private thermal power-plants and plan to use batteries to absorb fluctuations in power demand. A major challenge is in controlling both the power generation and the use of batteries under such fluctuations. We formulate a Markov decision process (MDP) and design the states of the MDP so that it has a periodic structure to avoid the explosion of its state space. We then develop a policy iteration algorithm that exploits the periodic structure for computational efficiency. Numerical experiments suggest that the combination of the proposed MDP and the policy iteration allows us to find a control policy that can significantly reduce the electricity cost.
[ECAI14] Rudy Raymond, Teruo Koyanagi, and Takayuki Osogami, "An approximate counting for big textual data streams," Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pages 1085-1086, Prague, Czech Republic, August 2014. PDF
Abstract The task of identifying and counting items that appear frequently in a dataset is important for artificial intelligent applications. For a small dataset, it can be done by recording the frequency of each item. For massive data stream, one has to resort to approximate counting with compact key-value data structures and fast stream algorithms. This paper introduces a multi-stage approximate counting algorithm for frequent patterns in text data stream. It combines the so-called lossy counting with compact data structures. It is designed to efficiently group textual data items in multiple stages according to their frequencies over the stream. That is, a few highly accessed items are grouped in high stage and stored in a hash table, and the rest of the items are grouped in middle or low stages and stored in appropriate data structures balancing their sizes, query time, and counting accuracies. We show the efficiency of the proposed algorithm theoretically and experimentally.
[AAAI14] Tetsuro Morimura, Takayuki Osogami, Tomoyuki Shirai, "Mixing-time regularized policy gradient," Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI-14), pages 1997-2003, Québec City, Québec, Canada, August 2014. PDF
Abstract Policy gradient reinforcement learning (PGRL) has been receiving substantial attention as a mean for seeking stochastic policies that maximize cumulative reward. However, the learning speed of PGRL is known to decrease substantially when PGRL explores the policies that give the Markov chains having long mixing time. We study a new approach of regularizing how the PGRL explores the policies by the use of the hitting time of the Markov chains. The hitting time gives an upper bound on the mixing time, and the proposed approach improves the learning efficiency by keeping the mixing time of the Markov chains short. In particular, we propose a method of temporal-difference learning for estimating the gradient of the hitting time. Numerical experiments show that the proposed method outperforms conventional methods of PGRL.
[ICPR14] Takayuki Osogami and Takayuki Katsuki, "A hierarchical Bayesian choice model with visibility," Proceedings of the 22nd International Conference on Pattern Recognition (ICPR 2014), pages 3618-3623, Stockholm, Sweden, August 2014. DOI 10.1109
Abstract We extend the standard choice model of multinomial logit model (MLM) into a hierarchical Bayesian model to simultaneously estimate the preferences of customers and the visibility of items from purchasing history. We say that an item has high visibility when customers well consider that item as a candidate before making a choice. We design two algorithms for estimating the parameters of the proposed choice model. One algorithm estimates the posterior distribution with the Gibbs sampling, and the other approximately performs the maximum a posteriori estimation. Our experimental results show that we can estimate the preferences of customers from their purchasing history without the prior knowledge of the choice set. The existing approaches to estimating the preferences of customers rely on the explicit knowledge of the choice set.
2013
[NIPS13] Tetsuro Morimura, Takayuki Osogami, and Tsuyoshi Ide, "Solving inverse problem of Markov chain with partial observations," Advances in Neural Information Processing Systems, 26 (NIPS 2013), pages 1655-1663, Lake Tahoe, NV, December 2013. PDF
Abstract The Markov chain is a convenient tool to represent the dynamics of complex systems such as traffic and social systems, where probabilistic transition takes place between internal states. A Markov chain is characterized by initial-state probabilities and a state-transition probability matrix. In the traditional setting, a major goal is to study properties of a Markov chain when those probabilities are known. This paper tackles an inverse version of the problem: we find those probabilities from partial observations at a limited number of states. The observations include the frequency of visiting a state and the rate of reaching a state from another. Practical examples of this task include traffic monitoring systems in cities, where we need to infer the traffic volume on single link on a road network from a limited number of observation points. We formulate this task as a regularized optimization problem, which is efficiently solved using the notion of natural gradient. Using synthetic and real-world data sets including city traffic monitoring data, we demonstrate the effectiveness of our method.
[ITS13] Takayuki Osogami, Hideyuki Mizuta, and Tsuyoshi Ide, "Identifying the optimal road closure with simulation," Proceedings of the 20th ITS World Congress, Paper #3178, Tokyo, Japan, October 2013. PDF
Abstract A transportation authority needs to decide which section of a road should be closed to allow road works. There are often multiple ways to close a section of a road, and the way to close the section can have a significant impact on the traffic flows around the closed section. We use IBM Mega Traffic Simulator version 2 (Megaffic2), an agent-based simulator of traffic flows, to analyze the impact of a road closure on traffic flows for multiple ways of road closures. Our analysis gives insights as to how a section of a road should be closed for road works that are planned in Hiroshima city in Japan.
[IJCAI13a] Takayuki Osogami and Rudy Raymond, "Map matching with inverse reinforcement learning," Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), pages 2547-2553, Beijing, China, August 2013. Accepted for both oral and poster presentation. PDF
Abstract We study map-matching, the problem of estimating the route that is traveled by a vehicle, where the points observed with the Global Positioning System are available. A state-of-the-art approach for this problem is a Hidden Markov Model (HMM). We propose a particular transition probability between latent road segments by the use of the number of turns in addition to the travel distance between the latent road segments. We use inverse reinforcement learning to estimate the importance of the number of turns relative to the travel distance. This estimated importance is incorporated in the transition probability of the HMM. We show, through numerical experiments, that the error of map-matching can be reduced substantially with the proposed transition probability.
[IJCAI13b] Hiroki Yanagisawa and Takayuki Osogami, "Improved integer programming approaches for the chance-constrained stochastic programming," Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), pages 2938-2944, Beijing, China, August 2013. Accepted for both oral and poster presentation. PDF
Abstract The Chance-Constrained Stochastic Programming (CCSP) is one of the models for decision making under uncertainty. In this paper, we consider the special case of the CCSP in which only the right-hand side vector is random with a discrete distribution having a finite support. The unit commitment problem is one of the applications of the special case of the CCSP. Existing methods for exactly solving the CCSP problems require an enumeration of scenarios when they model a CCSP problem using a Mixed Integer Programming (MIP). We show how to reduce the number of scenarios enumerated in the MIP model. In addition, we give another compact MIP formulation to approximately solve the CCSP problems.
[INFOCOM13] Hiroki Yanagisawa, Takayuki Osogami, and Rudy Raymond, "Dependable virtual machine allocation," Proceedings of the 32st Conference on Computer Communications (IEEE INFOCOM 2013), pages 629-637, Turin, Italy, April 2013. PDF
Abstract The difficulty in allocating virtual machines (VMs) on servers stems from the requirement that sufficient resources (such as CPU capacity and network bandwidth) must be available for each VM in the event of a failure or maintenance work as well as for temporal fluctuations of resource demands, which often exhibit periodic patterns. We propose a mixed integer programming approach that considers the fluctuations of the resource demands for optimal and dependable allocation of VMs. At the heart of the approach are techniques for optimally partitioning the time-horizon into intervals of variable lengths and for reliably estimating the resource demands in each interval. We show that our new approach allocates VMs successfully in a cloud computing environment in a financial company, where the dependability requirement is strict and there are various types of VMs exist.
2012
[NIPS12] Takayuki Osogami, "Robustness and risk-sensitivity in Markov decision processes," Advances in Neural Information Processing Systems, 25 (NIPS 2012), pages 233-241, Lake Tahoe, NV, December 2012. PDF
Abstract We uncover relations between robust MDPs and risk-sensitive MDPs. The objective of a robust MDP is to minimize a function, such as the expectation of cumulative cost, for the worst case when the parameters have uncertainties. The objective of a risk-sensitive MDP is to minimize a risk measure of the cumulative cost when the parameters are known. We show that a risk-sensitive MDP of minimizing the expected exponential utility is equivalent to a robust MDP of minimizing the worst-case expectation with a penalty for the deviation of the uncertain parameters from their nominal values, which is measured with the Kullback-Leibler divergence. We also show that a risk-sensitive MDP of minimizing an iterated risk measure that is composed of certain coherent risk measures is equivalent to a robust MDP of minimizing the worst-case expectation when the possible deviations of uncertain parameters from their nominal values are characterized with a concave function.
[ICPR12] Rudy Raymond, Tetsuro Morimura, Takayuki Osogami, and Noriaki Hirosue, "Map Matching with Hidden Markov Model on Sampled Road Network," Proceedings of the twenty-first conference of the International Association for Pattern Recognition (ICPR 2012), pages 2242-2245, Tsukuba, Japan, November 2012.
Abstract This paper presents a map matching method based on an ideal Hidden Markov Model (HMM) to find a sequence of roads that corresponds to a given sequence of raw GPS points. Our method is a simplification of the more-complex HMM-based method that maintains its capabilities to cope with the noises and sparsity of the raw GPS data. We test the method with the real-world raw GPS data that is publicly available. Experiments show that despite its simplicity, the proposed method performs sufficiently well under sparse GPS points and sparse road network data.
[AAAI12] Takayuki Osogami and Tetsuro Morimura, "Time-consistency of optimization problems," Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), pages 1945-1951, Toronto, Canada, July 2012. Accepted for both oral and poster presentation. PDF
Abstract We study time-consistency of optimization problems,where we say that an optimization problem is time-consistent if its optimal solution, or the optimal policy for choosing actions, does not depend on when the optimization problem is solved. Time-consistency is a minimal requirement on an optimization problem for the decisions made based on its solution to be rational. We show that the return that we can gain by taking "optimal" actions selected by solving a time-inconsistent optimization problem can be surely dominated by that we could gain by taking “suboptimal” actions. We establish sufficient conditions on the objective function and on the constraints for an optimization problem to be time-consistent. We also show when the sufficient conditions are necessary. Our results are relevant in stochastic settings particularly when the objective function is a risk measure other than expectation or when there is a constraint on a risk measure.
[SDM12] Rikiya Takahashi, Takayuki Osogami, and Tetsuro Morimura, "Large-Scale Nonparametric Estimation of Vehicle Travel Time Distributions," Proceedings of the 12th SIAM International Conference on Data Mining (SDM 2012), pages 12-23, Anaheim, CA, April 2012. Selected as one of the 10 best papers published in SDM'12. PDF
Abstract Fitting distributions of travel-time in vehicle traffic is an important application of spatio-temporal data mining. While regression methods to forecast the expected travel-time are standard approaches of travel-time prediction, we need to estimate distributions of the travel-time when using state-of-the-art risk-sensitive route recommendation systems. The authors introduce a novel nonparametric density estimator of travel-time for each road or link. The new estimator consists of basis functions modeled as mixtures of gamma or log-normal density functions, a sparse link similarity matrix given as an approximate diffusion kernel on a link connectivity graph, and importance weights for each link. Unlike the existing nonparametric methods that are computationally intensive, the new estimator is stably applicable to large datasets, because the basis functions and the importance weights are globally optimized with a fast convex clustering algorithm. Experimental results using real probe-car datasets show advantages of the new nonparametric estimator over parametric regression methods.
2011
[WSC11] Shoko Suzuki and Takayuki Osogami, "Real-time data assimilation," Proceedings of the 2011 Winter Simulation Conference (WSC 2011), pages 625-636, Phoenix, Arizona, December 2011. PDF
Abstract We investigate the idea of using the information obtained by observing a real system while simulating the real system to improve the accuracy of a prediction about the real system made based on the result of the simulation. Our approach runs multiple simulators simultaneously in parallel, where parameters of a simulation model are varied across the simulators. Based on the observation from a real system, some of the simulators are replicated, and others are terminated. We verify the effectiveness of our approach with numerical experiments. In addition, we provide a theoretical justification for our approach, using kernel density estimation.
[UAI11] Takayuki Osogami, "Iterated risk measures for risk-sensitive Markov decision processes with discounted cost",Proceedings of tThe 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011) pages 567-574, Barcelona, Spain, July 2011. PDF
Abstract We demonstrate a limitation of discounted expected utility, a standard approach for representing the preference to risk when future cost is discounted. Specifically, we provide an example of the preference of a decision maker that appears to be rational but cannot be represented with any discounted expected utility. A straightforward modification to discounted expected utility leads to inconsistent decision making over time. We will show that an iterated risk measure can represent the preference that cannot be represented by any discounted expected utility and that the decisions based on the iterated risk measure are consistent over time.
[DSN11] Takayuki Osogami and Rudy Raymond, "Simple bounds for a transient queue," Proceedings of the 41st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2011), pages 562-573, Hong Kong, China, June 2011. PDF
Abstract Bounds on performance of a queueing model can provide useful information to guarantee quality of service for communication networks. We study the bounds on the mean delay in a transient GI/GI/1 queue given the first two moments of the service time and the inter-arrival time, respectively. We establish a simple upper-bound, which then is used to show that the true transient mean-delay is at most four times larger than an asymptotic diffusion-approximation. We also prove that the tight lower-bound is zero as long as the service time and the inter-arrival time have finite variance and the load is below one. Tightness of the trivial lower-bound is in contrast to the stationary mean-delay, which has strictly positive lower-bound when the service time is sufficiently variable. We also show how our results can be applied to analyze the transient mean delay of packets in the real-world Internet.
[SIGMETRICS11] Varun Gupta and Takayuki Osogami, "Tight Moment-based Bounds for Queueing Systems in Light traffic," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2011), pages 133-134, San Diego, CA, June 2011. PDF
Abstract We present a new tool to analyze three queueing systems which have defied exact analysis so far: (i) the classical M/G/k multi-server system, (ii) queueing systems with fluctuating arrival and service rates, and (iii) the M/G/1 round-robin queue. We argue that rather than looking for exact expressions for the mean response time as a function of the job size distribution, a more fruitful approach is to find distributions which minimize or maximize the mean response time given the first n moments of the job size distribution.
We prove that for the M/G/k system in light traffic, and given n=2 and 3 moments, these 'extremal' distributions are given by principal representations of the moment sequence. Furthermore, if we restrict the distributions to lie in the class of Completely Monotone (CM) distributions, then for all the three queueing systems, for any n, the extremal distributions under the appropriate "light traffic" asymptotics are hyper-exponential distributions with finite number of phases. We conjecture that the property of extremality should be invariant to the system load, and thus our light traffic results should hold for general load as well.
2010
[PERFORMANCE10] Ryo Hirade, Takayuki Osogami, and Naoto Miyoshi, "Asymptotic optimality of Two Queue page replacement policy in a fluid limit," IFIP WG 7.3 International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance 2010), Namur, Belgium, November 2010 (poster presentation).
Abstract This paper proves the asymptotic optimality of the hit probability for Two Queue (2Q) page replacement policy in a fluid limit, where the number of items is scaled by n, the size of items is scaled by 1=n, and n approaches in.finity. To capture both recency and frequency, 2Q divides a buffer into two parts. Given the size of the buffer and the number of items, the hit probability for 2Q in the fluid limit approaches the theoretical upper bound as the ratio of partition becomes smaller.
[SIGMETRICS10] Takayuki Osogami and Rudy Raymond, "Semidefinite optimization for transient analysis of queues," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2010), pages 363-364, New York, NY, June 2010. PDF
Abstract We derive an upper bound on the tail distribution of the transient waiting time for the GI/GI/1 queue from a formulation of semidefinite programming (SDP). Our upper bounds are expressed in closed forms using the first two moments of the service time and the interarrival time. The upper bounds on the tail distributions are integrated to obtain the upper bounds on the corresponding expectations. We also extend the formulation of the SDP, using the higher moments of the service time and the interarrival time, and calculate upper bounds and lower bounds numerically.
2009
[INFOCOM09] Takayuki Osogami, "A fluid limit for cache algorithms with general request processes (extended abstract)," Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM 2009), pages 2836-2840, Rio de Janeiro, Brazil, April 2009. PDF
Abstract We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the Least-Recently-Used algorithm when requests are issued according to general stochastic point processes, which may be non-stationary. We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes as the number of replications approaches infinity. We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit. The usefulness of the fluid limit is demonstrated in two ways. First, our numerical experiments show that, when items are requested according to inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system as long as there are sufficient number of items. Second, we show that the asymptotic characteristics of the average miss probability as the cache size approaches infinity are often preserved in the fluid limit. This preservation is attractive since the asymptotic analysis in the fluid limit appears to be simpler than that in the original system. In addition, we show that the average miss probability in the fluid limit is asymptotically insensitive to particular dependencies in the requests when the request rates have a light tail, a property not known for the original system.
2008
[DSN08] Sei Kato and Takayuki Osogami, "Evaluating availability under quasi-heavy-tailed repair times," Proceedings of the 38th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2008), pages 442-451, Anchorage, AK, June 2008. PDF
Abstract The time required to recover from failures has a great impact on the availability of Information Technology (IT) systems. We define a class of probability distributions named quasi-heavy-tailed distributions as those distributions whose time series graph of the sample mean shows intermittent jumps in a given period. We find that the distribution of repair time is quasi-heavy-tailed for three IT systems, an in-house system hosted by IBM, a high performance computing system at the Los Alamos National Laboratory,and a distributed memory computer at the National Energy Research Scientific Computing Center. This means that the mean time to repair estimated by observing incidents within a certain period could dramatically change if we observe incidents successively for another period. In other words, the estimated mean time to repair has large fluctuations over time. As a result, classical metrics based on the mean time to repair are not optimal for evaluating the availability of these systems. We propose to evaluate the availability of IT systems with the T-year return value, estimated based on extreme value theory. The T-year return value refers to the value that the repair time exceeds on average once every estimated T years. We find that the T-year return value is a sound metric of the availability of the three IT systems.
2007
[QEST07] Takayuki Osogami, "Relations in the central limit theorem version of the response time law," Proceedings of the 4th International Conference on the Quantitative Evaluation of SysTems (QEST 2007), pages 69-78, Edinburgh, Scotland, September 2007. (See [PE10] PDF for an extended version.)
Abstract We study the accuracy of the estimators of mean response time and throughput in closed interactive systems such as Web systems. The response time law allows us to calculate the throughput from the mean response time and vice versa. However, we find that the accuracy of the two estimators can be quite different. We refine the response time law using the central limit theorem and study the asymptotic accuracy of the estimators when the measurement time approaches infinity. Based on the asymptotic accuracy of the estimators, we derive rules of thumb for the accuracy of the measured mean response time and measured throughput. Extensive simulation study suggests that the rules of thumb are often valid under realistic measurement time.
[SIGMETRICS07] Takayuki Osogami and Sei Kato, "Optimizing system configurations quickly by guessing at the performance," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2007), pages 145-156, San Diego, CA, June 2007. PDF
Abstract The performance of a Web system can be greatly improved by tuning its configuration parameters. However, finding the optimal configuration has been a time-consuming task due to the long measurement time needed to evaluate the performance of a given configuration. We propose an algorithm, which we refer to as Quick Optimization via Guessing (QOG), that quickly selects one of nearly best configurations with high probability. The key ideas in QOG are (i) the measurement of a configuration is terminated as soon as the configuration is found to be suboptimal, and (ii) the performance of a configuration is guessed at based on the measured similar configurations, so that the better configurations are more likely to be measured before the others. If the performance of a good configuration has been measured, a poor configuration will be quickly found to be suboptimal with short measurement time. We apply QOG to optimizing the configuration of a real Web system, and find that QOG can drastically reduce the total measurement time needed to select the best configuration. Our experiments also illuminate several interesting properties of QOG specifically when it is applied to optimizing Web systems.
[MAMA07] Takayuki Osogami, "Accuracy of measured throughputs and mean response times," The Ninth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2007), San Diego, CA, June 2007; ACM Performance Evaluation Review, 25(2):9-11. (See [PE10] PDF for an extended version.)
Abstract The performance of computer systems such as Web systems is measured to guarantee quality of service (QoS) or to compare difference configurations of the systems [8]. We consider the problem of whether we should measure mean response time or throughput to better guarantee QoS or to better compare different configurations of a Web system. Specifically, is measured mean response time or measured throughput more accurate, when the Web system is measured for a fixed period of time?
2006
[WSC06] Takayuki Osogami, "Finding Probably Best Systems Quickly via Simulations," Proceedings of the 2006 Winter Simulation Conference (WSC 2006), page 2285, Monterey, CA, December 2006. (See [TOMACS09] PDF for an extended version.)
Abstract The performance of computer systems can in theory be optimized by selecting the system configuration having the best simulated performance. Unfortunately, it is often computationally intractable to estimate the performance of all system configurations accurately via simulation. We propose an algorithm for finding the best system configuration without estimating the performance of each system configuration accurately, so that the total simulation time is minimized. We prove that with high probability our algorithm finds the best system configuration. In addition, our algorithm has an advantage in that it only infrequently changes the system configurations to be simulated. Numerical experiments show that our algorithm improves upon existing algorithms with respect to the total simulation time and the frequency of changing the system configurations.
[SIGMETRICS06] Takayuki Osogami and Toshinari Itoko, "Finding probably better system configurations quickly," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2006), pages 264-275, Saint-Malo, France, June 2006. PDF
Abstract The performance of computer and communication systems can in theory be optimized by iteratively finding better system configurations. However, a bottleneck is the time required in simulations/experiments for finding a better system configuration in each iteration. We propose algorithms that quickly find a system configuration that is probably better than the "standard" system configuration, where the performance of a given system configuration is estimated via simulations or experiments. We prove that our algorithms make correct decisions with high probability, and various heuristics to reduce the total simulation time are proposed. Numerical experiments show the effectiveness of the proposed algorithms, and this leads to several guidelines for designing efficient and reliable optimization procedures for the performance of computer and communication systems.
[MAMA06] Takayuki Osogami, "Finding probably best system configurations quickly," The Eighth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2006), Saint-Malo, France, June 2006; ACM Performance Evaluation Review, 34(3):39-41, 2006. (See [TOMACS09] PDF for an extended version.)
Abstract Computer systems often have many possible configurations, and designing a high performance system often requires selecting the best configuration. Unfortunately, the performance of complex systems can often be estimated only via simulations, or with measurements of real systems. Since longer simulation times are required to estimate the performance more accurately, it is often computationally intractable to estimate the performance of all configurations accurately via simulations. (Measurements of real systems can take even longer.)
2005
[SIGMETRICS05] Adam Wierman, Mor Harchol-Balter, and Takayuki Osogami, "Nearly Insensitive Bounds on SMART Scheduling," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2005), pages 205-216, Banff, Canada, June 2005. PDF
Abstract We define the class of SMART scheduling policies. These are policies that bias towards jobs with small remaining service times, jobs with small original sizes, or both, with the motivation of minimizing mean response time and/or mean slowdown. Examples of SMART policies include PSJF, SRPT, and hybrid policies such as RS (which biases according to the product of the remaining size and the original size of a job).For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely insensitive to the variability of the job size distribution. In particular, we focus on the SRPT and PSJF policies and prove insensitive bounds in these cases.
[MAMA05] Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf, "Robustness of Threshold Policies for Beneficiary-Donor Model," The Seventh Workshop on Mathematical Performance Modeling and Analysis (MAMA 2005), Banff, Canada, June 2005; ACM Performance Evaluation Review, 33(2):36-38, 2005. PDF
Abstract A common problem in multiserver systems is deciding how to allocate resources among jobs so as to minimize mean response time. Since good parameter settings typically depend on environmental conditions such as system loads, an allocation policy that is optimal in one environment may provide poor performance when the environment changes, or when the prediction of the environment is wrong. We say that such a policy is not robust. In this paper, we analytically compare the robustness of several threshold-based allocation policies, in a dual server beneficiary-donor model. We introduce two types of robustness: static robustness, which measures robustness against mis-estimation of the true load, and dynamic robustness, which measures robustness against fluctuations in the load. We find that policies employing multiple thresholds offer significant benefit over single threshold policies with respect to static robustness. Yet they surprisingly offer much less benefit with respect to dynamic robustness.
2004
[MAMA04] Takayuki Osogami, Adam Wierman, Mor Harchol-Balter, and Alan Scheller-Wolf, "A recursive analysis technique for multi-dimensionally infinite Markov chains," The Sixth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2004), New York, NY, June 2004; ACM Performance Evaluation Review, 32(2):3-5, 2004. PDF
Abstract Performance analysis of multiserver systems with multiple classes of jobs often has a common source of difficulty: the state space needed to capture the system behavior grows infinitely in multiple dimensions. For example, consider two processors, each serving its own M/M/1 queue, where one of the processors (the "donor") can help the other processor (the "beneficiary") with its jobs, during times when the donor processor is idle [5, 16] or when some threshold conditions are met [14, 15]. Since the behavior of beneficiary jobs depends on the number of donor jobs in system, performance analysis of beneficiary jobs involves a two dimensionally infinite (2D-infinite) state space, where one dimension corresponds to the number of beneficiary jobs and the other dimension corresponds to the number of donor jobs. Another example is an M/M/2 queue with two priority classes, where high priority jobs have preemptive priority over low priority jobs (see for example [1, 3, 4, 8, 10, 11, 12, 17] and references therein). Since the behavior of low priority jobs depends on the number of high priority jobs in system, performance analysis of low priority jobs involves 2D-infinite state space, where each dimension corresponds to the number of each class of jobs in system. As we will see, when there are m priority classes, performance analysis of the lowest priority classes involves m dimensionally infinite state space.
2003
[MASCOTS03] Adam Wierman, Takayuki Osogami, and Jorgen Olsen, "A Unified Framework for Modeling TCP-Vegas, TCP-SACK, and TCP-Reno," Proceedings of the 11th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2003), pages 269-278, Orlando, FL, October 2003. PDF
Abstract This article illustrates the generality of a framework for analytically modeling TCP introduced by Casetti and Meo in [9]. The key contribution of the model is a separation of modeling the internal features of a TCP source from the external
properties of the network. We generalize the model of TCP sources to include TCP-SACK and TCP-Vegas in addition to extending the originally modeled TCP-Reno. This work also evaluates a variety of models for the network, i.e. M/D/1, M/M/1, and M^r/M/1 queuing models.
[TOOLS03b] Takayuki Osogami and Mor Harchol-Balter, "A Closed-form Solution for Mapping General Distributions to Minimal PH Distributions," Proceedings of the 12th International Conference on Modelling Tools and Techniques for Computer and Communication System Performance Evaluation (TOOLS 2003), pages 200-217, Urbana, IL, September 2003. Selected as one of the best papers; an extended version was published in a special issue of Performance Evaluation [PE06a] PDF.
Abstract Approximating general distributions by phase-type (PH) distributions is a popular technique in queueing analysis, since the Markovian property of PH distributions often allows analytical tractability. This paper proposes an algorithm for mapping a general distribution G to a PH distribution where the goal is to .nd a PH distribution which matches the .rst three moments of G. Since e.ciency of the algorithm is of primary importance, we .rst de.ne a particular subset of the PH distributions, which we refer to as EC distributions. The class of EC distributions has very few free parameters, which narrows down the search space, making the algorithm e.cient -- In fact we provide a closed-form solution for the parameters of the EC distribution. Our solution is general in that it applies to any distribution whose .rst three moments can be matched by a PH distribution. Also, our resulting EC distribution requires a nearly minimal number of phases, always within one of the minimal number of phases required by any acyclic PH distribution. Lastly, we discuss numerical stability of our solution.
[TOOLS03a] Takayuki Osogami and Mor Harchol-Balter, "Necessary and Sufficient Conditions for Representing General Distributions by Coxians," Proceedings of the 12th International Conference on Modelling Tools and Techniques for Computer and Communication System Performance Evaluation (TOOLS 2003), pages 182-199, Urbana, IL, September 2003. Selected as one of the best papers; an extended version was published in a special issue of Performance Evaluation [PE06a] PDF.
Abstract A common analytical technique involves using a Coxian distribution to model a general distribution G, where the Coxian distribution agrees with G on the .rst three moments. This technique is motivated by the analytical tractability of the Coxian distribution. Algorithms for mapping an input distribution G to a Coxian distribution largely hinge on knowing a priori the necessary and su.cient number of phases in the representative Coxian distribution. In this paper, we formally characterize the set of distributions G which are well-represented by an n-phase Coxian distribution, in the sense that the Coxian distribution matches the .rst three moments of G. We also discuss a few common, practical examples.
[SIGMETRICS03] Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "Analysis of Cycle Stealing with Switching Cost," Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2003), pages 184-195, San Diego, CA, June 2003. PDF
Abstract We consider the scenario of two processors, each serving its own workload, where one of the processors (known as the "donor") can help the other processor (known as the "beneficiary") with its jobs, during times when the donor processor is idle. That is the beneficiary processor "steals idle cycles" from the donor processor. We assume that both donor jobs and beneficiary jobs may have generally-distributed service requirements. We assume that there is a switching cost required for the donor processor to start working on the beneficiary jobs, as well as a switching cost required for the donor processor to return to working on its own jobs. We also allow for threshold constraints, whereby the donor processor only initiates helping the beneficiary if both the donor is idle and the number of jobs at the beneficiary exceeds a certain threshold.We analyze the mean response time for the donor and beneficiary processors. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate several interesting principles with respect to the general benefits of cycle stealing and the design of cycle stealing policies.
[SPAA03] Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, and Mark S. Squillante, "Cycle Stealing under Immediate Dispatch Task Assignment," Proceedings of the Fifteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2003), pages 274-285, San Diego, CA, June 2003. PDF
Abstract We consider the practical problem of task assignment in a server farm, where each arriving job is immediately dispatched to a server in the farm. We look at the benefit of cycle stealing at the point of the dispatcher, where jobs normally destined for one machine may be routed to a different machine if it is idle. The analysis uses a technique which we refer to as dimensionality reduction via busy period transitions. Our analysis is approximate, but can be made as close to exact as desired, and is validated via simulation. Results show that the beneficiaries of the idle cycles can benefit unboundedly, due to an increase in their stability region, while the donors are only slightly penalized. These results still hold even when there is only one donor server and 20 beneficiary servers stealing its idle cycles.
[MAMA03] Adam Wierman, Takayuki Osogami, and Jorgen Olsen, "Modeling TCP-Vegas under On/Off Traffic," The Fifth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2003), San Diego, CA, September 2003; ACM Performance Evaluation Review, 31, pages 6-8, 2003. (An extended version available as [MASCOTS03] PDF)
[ICDCS03] Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, and Mark S. Squillante, "Analysis of Task Assignment with Cycle Stealing under Central Queue," Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS 2003), pages 628-637, Providence, RI, May 2003. PDF
Abstract We consider the problem of task assignment in a distributedserver system, where short jobs are separated fromlong jobs, but short jobs may be run in the long job partitionif it is idle (cycle stealing). Jobs are assumed to be non-preemptible,where short and long jobs have generally-distributedservice requirements, and arrivals are Poisson.We consider two variants of this problem: a centralqueue model and an immediate dispatch model. This paperpresents the first analysis of cycle stealing under thecentral-queue model. (Cycle stealing under the immediatedispatch model is analyzed in [9]). The analysis usesa technique which we refer to as busy period transitions.Results show that cycle stealing can reduce mean responsetime for short jobs by orders of magnitude, while long jobsare only slightly penalized. Furthermore using a centralqueue yields significant performance improvement over immediatedispatch, both from the perspective of the benefit toshort jobs and the penalty to long jobs.
2000
[ISAAC00] Takayuki Osogami and Hiroshi Imai, "Classification of Various Neighborhood Operations for the Nurse Scheduling Problem (Extended Abstract)", Proceedings of the Eleventh Annual International Symposium on Algorithms And Computation (ISAAC 2000), Taipei, Taiwan, December (2000); in Lecture Notes in Computer Science, 1969: 72-83, 2000. Extended version available as a technical report: PDF
Abstract Since the nurse scheduling problem (NSP) is a problem of finding a feasible solution, the solution space must include infeasible solutions to solve it using a local search algorithm. However, the solution space consisting of all the solutions is so large that the search requires much CPU time. In the NSP, some constraints have higher priority. Thus, we can define the solution space to be the set of solutions satisfying some of the important constraints, which are called the elementary constraints. The connectivity of the solution space is also important for the performance. However, the connectivity is not obvious when the solution space consists only of solutions satisfying the elementary constraints and is composed of small neighborhoods. This paper gives theoretical support for using 4-opt-type neighborhood operations by discussing the connectivity of its solution space and the size of the neighborhood. Another interesting point in our model is a special case of the NSP corresponds to the bipartite transportation problem, and our result also applies to it.