Showing 1–36 of 36 results for author: Matsushima, T

Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers

Authors: Atsushi Miki, Yusuke Morishita, Toshiyasu Matsushima

Abstract: Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. Here, PIRs in which servers do not communicate with each other are called standard PIRs, and PIRs in which some servers communicate with each other are called colluding PIRs. The information-theoretic upper bound on efficiency has been given in previous studies. However, the cond… ▽ More Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. Here, PIRs in which servers do not communicate with each other are called standard PIRs, and PIRs in which some servers communicate with each other are called colluding PIRs. The information-theoretic upper bound on efficiency has been given in previous studies. However, the conditions for PIRs to keep privacy, to decode the desired message, and to achieve that upper bound have not been clarified in matrix form. In this paper, we prove the necessary and sufficient conditions for the properties of standard PIR and colluding PIR. Further, we represent the properties in matrix form. △ Less

Submitted 13 July, 2024; v1 submitted 21 April, 2024; originally announced April 2024.

Comments: 16 pages

An Algorithmic Framework for Constructing Multiple Decision Trees by Evaluating Their Combination Performance Throughout the Construction Process

Authors: Keito Tajima, Naoki Ichijo, Yuta Nakahara, Toshiyasu Matsushima

Abstract: Predictions using a combination of decision trees are known to be effective in machine learning. Typical ideas for constructing a combination of decision trees for prediction are bagging and boosting. Bagging independently constructs decision trees without evaluating their combination performance and averages them afterward. Boosting constructs decision trees sequentially, only evaluating a combin… ▽ More Predictions using a combination of decision trees are known to be effective in machine learning. Typical ideas for constructing a combination of decision trees for prediction are bagging and boosting. Bagging independently constructs decision trees without evaluating their combination performance and averages them afterward. Boosting constructs decision trees sequentially, only evaluating a combination performance of a new decision tree and the fixed past decision trees at each step. Therefore, neither method directly constructs nor evaluates a combination of decision trees for the final prediction. When the final prediction is based on a combination of decision trees, it is natural to evaluate the appropriateness of the combination when constructing them. In this study, we propose a new algorithmic framework that constructs decision trees simultaneously and evaluates their combination performance throughout the construction process. Our framework repeats two procedures. In the first procedure, we construct new candidates of combinations of decision trees to find a proper combination of decision trees. In the second procedure, we evaluate each combination performance of decision trees under some criteria and select a better combination. To confirm the performance of the proposed framework, we perform experiments on synthetic and benchmark data. △ Less

Submitted 9 February, 2024; originally announced February 2024.

Boosting-Based Sequential Meta-Tree Ensemble Construction for Improved Decision Trees

Authors: Ryota Maniwa, Naoki Ichijo, Yuta Nakahara, Toshiyasu Matsushima

Abstract: A decision tree is one of the most popular approaches in machine learning fields. However, it suffers from the problem of overfitting caused by overly deepened trees. Then, a meta-tree is recently proposed. It solves the problem of overfitting caused by overly deepened trees. Moreover, the meta-tree guarantees statistical optimality based on Bayes decision theory. Therefore, the meta-tree is expec… ▽ More A decision tree is one of the most popular approaches in machine learning fields. However, it suffers from the problem of overfitting caused by overly deepened trees. Then, a meta-tree is recently proposed. It solves the problem of overfitting caused by overly deepened trees. Moreover, the meta-tree guarantees statistical optimality based on Bayes decision theory. Therefore, the meta-tree is expected to perform better than the decision tree. In contrast to a single decision tree, it is known that ensembles of decision trees, which are typically constructed boosting algorithms, are more effective in improving predictive performance. Thus, it is expected that ensembles of meta-trees are more effective in improving predictive performance than a single meta-tree, and there are no previous studies that construct multiple meta-trees in boosting. Therefore, in this study, we propose a method to construct multiple meta-trees using a boosting approach. Through experiments with synthetic and benchmark datasets, we conduct a performance comparison between the proposed methods and the conventional methods using ensembles of decision trees. Furthermore, while ensembles of decision trees can cause overfitting as well as a single decision tree, experiments confirmed that ensembles of meta-trees can prevent overfitting due to the tree depth. △ Less

Submitted 9 February, 2024; originally announced February 2024.

Real-World Robot Applications of Foundation Models: A Review

Authors: Kento Kawaharazuka, Tatsuya Matsushima, Andrew Gambardella, Jiaxian Guo, Chris Paxton, Andy Zeng

Abstract: Recent developments in foundation models, like Large Language Models (LLMs) and Vision-Language Models (VLMs), trained on extensive data, facilitate flexible application across different tasks and modalities. Their impact spans various fields, including healthcare, education, and robotics. This paper provides an overview of the practical application of foundation models in real-world robotics, wit… ▽ More Recent developments in foundation models, like Large Language Models (LLMs) and Vision-Language Models (VLMs), trained on extensive data, facilitate flexible application across different tasks and modalities. Their impact spans various fields, including healthcare, education, and robotics. This paper provides an overview of the practical application of foundation models in real-world robotics, with a primary emphasis on the replacement of specific components within existing robot systems. The summary encompasses the perspective of input-output relationships in foundation models, as well as their role in perception, motion planning, and control within the field of robotics. This paper concludes with a discussion of future challenges and implications for practical robot applications. △ Less

Submitted 8 February, 2024; originally announced February 2024.

Open X-Embodiment: Robotic Learning Datasets and RT-X Models

Authors: Open X-Embodiment Collaboration, Abby O'Neill, Abdul Rehman, Abhinav Gupta, Abhiram Maddukuri, Abhishek Gupta, Abhishek Padalkar, Abraham Lee, Acorn Pooley, Agrim Gupta, Ajay Mandlekar, Ajinkya Jain, Albert Tung, Alex Bewley, Alex Herzog, Alex Irpan, Alexander Khazatsky, Anant Rai, Anchit Gupta, Andrew Wang, Andrey Kolobov, Anikait Singh, Animesh Garg, Aniruddha Kembhavi, Annie Xie , et al. (267 additional authors not shown)

Abstract: Large, high-capacity models trained on diverse datasets have shown remarkable successes on efficiently tackling downstream applications. In domains from NLP to Computer Vision, this has led to a consolidation of pretrained models, with general pretrained backbones serving as a starting point for many applications. Can such a consolidation happen in robotics? Conventionally, robotic learning method… ▽ More Large, high-capacity models trained on diverse datasets have shown remarkable successes on efficiently tackling downstream applications. In domains from NLP to Computer Vision, this has led to a consolidation of pretrained models, with general pretrained backbones serving as a starting point for many applications. Can such a consolidation happen in robotics? Conventionally, robotic learning methods train a separate model for every application, every robot, and even every environment. Can we instead train generalist X-robot policy that can be adapted efficiently to new robots, tasks, and environments? In this paper, we provide datasets in standardized data formats and models to make it possible to explore this possibility in the context of robotic manipulation, alongside experimental results that provide an example of effective X-robot policies. We assemble a dataset from 22 different robots collected through a collaboration between 21 institutions, demonstrating 527 skills (160266 tasks). We show that a high-capacity model trained on this data, which we call RT-X, exhibits positive transfer and improves the capabilities of multiple robots by leveraging experience from other platforms. More details can be found on the project website https://robotics-transformer-x.github.io. △ Less

Submitted 1 June, 2024; v1 submitted 13 October, 2023; originally announced October 2023.

Comments: Project website: https://robotics-transformer-x.github.io

TRAIL Team Description Paper for RoboCup@Home 2023

Authors: Chikaha Tsuji, Dai Komukai, Mimo Shirasaka, Hikaru Wada, Tsunekazu Omija, Aoi Horo, Daiki Furuta, Saki Yamaguchi, So Ikoma, Soshi Tsunashima, Masato Kobayashi, Koki Ishimoto, Yuya Ikeda, Tatsuya Matsushima, Yusuke Iwasawa, Yutaka Matsuo

Abstract: Our team, TRAIL, consists of AI/ML laboratory members from The University of Tokyo. We leverage our extensive research experience in state-of-the-art machine learning to build general-purpose in-home service robots. We previously participated in two competitions using Human Support Robot (HSR): RoboCup@Home Japan Open 2020 (DSPL) and World Robot Summit 2020, equivalent to RoboCup World Tournament.… ▽ More Our team, TRAIL, consists of AI/ML laboratory members from The University of Tokyo. We leverage our extensive research experience in state-of-the-art machine learning to build general-purpose in-home service robots. We previously participated in two competitions using Human Support Robot (HSR): RoboCup@Home Japan Open 2020 (DSPL) and World Robot Summit 2020, equivalent to RoboCup World Tournament. Throughout the competitions, we showed that a data-driven approach is effective for performing in-home tasks. Aiming for further development of building a versatile and fast-adaptable system, in RoboCup @Home 2023, we unify three technologies that have recently been evaluated as components in the fields of deep learning and robot learning into a real household robot system. In addition, to stimulate research all over the RoboCup@Home community, we build a platform that manages data collected from each site belonging to the community around the world, taking advantage of the characteristics of the community. △ Less

Submitted 5 October, 2023; originally announced October 2023.

Self-Recovery Prompting: Promptable General Purpose Service Robot System with Foundation Models and Self-Recovery

Authors: Mimo Shirasaka, Tatsuya Matsushima, Soshi Tsunashima, Yuya Ikeda, Aoi Horo, So Ikoma, Chikaha Tsuji, Hikaru Wada, Tsunekazu Omija, Dai Komukai, Yutaka Matsuo Yusuke Iwasawa

Abstract: A general-purpose service robot (GPSR), which can execute diverse tasks in various environments, requires a system with high generalizability and adaptability to tasks and environments. In this paper, we first developed a top-level GPSR system for worldwide competition (RoboCup@Home 2023) based on multiple foundation models. This system is both generalizable to variations and adaptive by prompting… ▽ More A general-purpose service robot (GPSR), which can execute diverse tasks in various environments, requires a system with high generalizability and adaptability to tasks and environments. In this paper, we first developed a top-level GPSR system for worldwide competition (RoboCup@Home 2023) based on multiple foundation models. This system is both generalizable to variations and adaptive by prompting each model. Then, by analyzing the performance of the developed system, we found three types of failure in more realistic GPSR application settings: insufficient information, incorrect plan generation, and plan execution failure. We then propose the self-recovery prompting pipeline, which explores the necessary information and modifies its prompts to recover from failure. We experimentally confirm that the system with the self-recovery mechanism can accomplish tasks by resolving various failure cases. Supplementary videos are available at https://sites.google.com/view/srgpsr . △ Less

Submitted 26 September, 2023; v1 submitted 25 September, 2023; originally announced September 2023.

Comments: Website: https://sites.google.com/view/srgpsr

GenDOM: Generalizable One-shot Deformable Object Manipulation with Parameter-Aware Policy

Authors: So Kuroki, Jiaxian Guo, Tatsuya Matsushima, Takuya Okubo, Masato Kobayashi, Yuya Ikeda, Ryosuke Takanami, Paul Yoo, Yutaka Matsuo, Yusuke Iwasawa

Abstract: Due to the inherent uncertainty in their deformability during motion, previous methods in deformable object manipulation, such as rope and cloth, often required hundreds of real-world demonstrations to train a manipulation policy for each object, which hinders their applications in our ever-changing world. To address this issue, we introduce GenDOM, a framework that allows the manipulation policy… ▽ More Due to the inherent uncertainty in their deformability during motion, previous methods in deformable object manipulation, such as rope and cloth, often required hundreds of real-world demonstrations to train a manipulation policy for each object, which hinders their applications in our ever-changing world. To address this issue, we introduce GenDOM, a framework that allows the manipulation policy to handle different deformable objects with only a single real-world demonstration. To achieve this, we augment the policy by conditioning it on deformable object parameters and training it with a diverse range of simulated deformable objects so that the policy can adjust actions based on different object parameters. At the time of inference, given a new object, GenDOM can estimate the deformable object parameters with only a single real-world demonstration by minimizing the disparity between the grid density of point clouds of real-world demonstrations and simulations in a differentiable physics simulator. Empirical validations on both simulated and real-world object manipulation setups clearly show that our method can manipulate different objects with a single demonstration and significantly outperforms the baseline in both environments (a 62% improvement for in-domain ropes and a 15% improvement for out-of-distribution ropes in simulation, as well as a 26% improvement for ropes and a 50% improvement for cloths in the real world), demonstrating the effectiveness of our approach in one-shot deformable object manipulation. △ Less

Submitted 23 February, 2024; v1 submitted 16 September, 2023; originally announced September 2023.

Comments: Extended version of arXiv:2306.09872

GenORM: Generalizable One-shot Rope Manipulation with Parameter-Aware Policy

Authors: So Kuroki, Jiaxian Guo, Tatsuya Matsushima, Takuya Okubo, Masato Kobayashi, Yuya Ikeda, Ryosuke Takanami, Paul Yoo, Yutaka Matsuo, Yusuke Iwasawa

Abstract: Due to the inherent uncertainty in their deformability during motion, previous methods in rope manipulation often require hundreds of real-world demonstrations to train a manipulation policy for each rope, even for simple tasks such as rope goal reaching, which hinder their applications in our ever-changing world. To address this issue, we introduce GenORM, a framework that allows the manipulation… ▽ More Due to the inherent uncertainty in their deformability during motion, previous methods in rope manipulation often require hundreds of real-world demonstrations to train a manipulation policy for each rope, even for simple tasks such as rope goal reaching, which hinder their applications in our ever-changing world. To address this issue, we introduce GenORM, a framework that allows the manipulation policy to handle different deformable ropes with a single real-world demonstration. To achieve this, we augment the policy by conditioning it on deformable rope parameters and training it with a diverse range of simulated deformable ropes so that the policy can adjust actions based on different rope parameters. At the time of inference, given a new rope, GenORM estimates the deformable rope parameters by minimizing the disparity between the grid density of point clouds of real-world demonstrations and simulations. With the help of a differentiable physics simulator, we require only a single real-world demonstration. Empirical validations on both simulated and real-world rope manipulation setups clearly show that our method can manipulate different ropes with a single demonstration and significantly outperforms the baseline in both environments (62% improvement in in-domain ropes, and 15% improvement in out-of-distribution ropes in simulation, 26% improvement in real-world), demonstrating the effectiveness of our approach in one-shot rope manipulation. △ Less

Submitted 19 June, 2023; v1 submitted 13 June, 2023; originally announced June 2023.

Prediction Algorithms Achieving Bayesian Decision Theoretical Optimality Based on Decision Trees as Data Observation Processes

Authors: Yuta Nakahara, Shota Saito, Naoki Ichijo, Koki Kazama, Toshiyasu Matsushima

Abstract: In the field of decision trees, most previous studies have difficulty ensuring the statistical optimality of a prediction of new data and suffer from overfitting because trees are usually used only to represent prediction functions to be constructed from given data. In contrast, some studies, including this paper, used the trees to represent stochastic data observation processes behind given data.… ▽ More In the field of decision trees, most previous studies have difficulty ensuring the statistical optimality of a prediction of new data and suffer from overfitting because trees are usually used only to represent prediction functions to be constructed from given data. In contrast, some studies, including this paper, used the trees to represent stochastic data observation processes behind given data. Moreover, they derived the statistically optimal prediction, which is robust against overfitting, based on the Bayesian decision theory by assuming a prior distribution for the trees. However, these studies still have a problem in computing this Bayes optimal prediction because it involves an infeasible summation for all division patterns of a feature space, which is represented by the trees and some parameters. In particular, an open problem is a summation with respect to combinations of division axes, i.e., the assignment of features to inner nodes of the tree. We solve this by a Markov chain Monte Carlo method, whose step size is adaptively tuned according to a posterior distribution for the trees. △ Less

Submitted 12 June, 2023; originally announced June 2023.

Batch Updating of a Posterior Tree Distribution over a Meta-Tree

Authors: Yuta Nakahara, Toshiyasu Matsushima

Abstract: Previously, we proposed a probabilistic data generation model represented by an unobservable tree and a sequential updating method to calculate a posterior distribution over a set of trees. The set is called a meta-tree. In this paper, we propose a more efficient batch updating method. Previously, we proposed a probabilistic data generation model represented by an unobservable tree and a sequential updating method to calculate a posterior distribution over a set of trees. The set is called a meta-tree. In this paper, we propose a more efficient batch updating method. △ Less

Submitted 16 July, 2023; v1 submitted 16 March, 2023; originally announced March 2023.

Collective Intelligence for 2D Push Manipulations with Mobile Robots

Authors: So Kuroki, Tatsuya Matsushima, Jumpei Arima, Hiroki Furuta, Yutaka Matsuo, Shixiang Shane Gu, Yujin Tang

Abstract: While natural systems often present collective intelligence that allows them to self-organize and adapt to changes, the equivalent is missing in most artificial systems. We explore the possibility of such a system in the context of cooperative 2D push manipulations using mobile robots. Although conventional works demonstrate potential solutions for the problem in restricted settings, they have com… ▽ More While natural systems often present collective intelligence that allows them to self-organize and adapt to changes, the equivalent is missing in most artificial systems. We explore the possibility of such a system in the context of cooperative 2D push manipulations using mobile robots. Although conventional works demonstrate potential solutions for the problem in restricted settings, they have computational and learning difficulties. More importantly, these systems do not possess the ability to adapt when facing environmental changes. In this work, we show that by distilling a planner derived from a differentiable soft-body physics simulator into an attention-based neural network, our multi-robot push manipulation system achieves better performance than baselines. In addition, our system also generalizes to configurations not seen during training and is able to adapt toward task completions when external turbulence and environmental changes are applied. Supplementary videos can be found on our project website: https://sites.google.com/view/ciom/home △ Less

Submitted 4 April, 2023; v1 submitted 28 November, 2022; originally announced November 2022.

Comments: Robotics and Automation Letters(RA-L) 2023

World Robot Challenge 2020 -- Partner Robot: A Data-Driven Approach for Room Tidying with Mobile Manipulator

Authors: Tatsuya Matsushima, Yuki Noguchi, Jumpei Arima, Toshiki Aoki, Yuki Okita, Yuya Ikeda, Koki Ishimoto, Shohei Taniguchi, Yuki Yamashita, Shoichi Seto, Shixiang Shane Gu, Yusuke Iwasawa, Yutaka Matsuo

Abstract: Tidying up a household environment using a mobile manipulator poses various challenges in robotics, such as adaptation to large real-world environmental variations, and safe and robust deployment in the presence of humans.The Partner Robot Challenge in World Robot Challenge (WRC) 2020, a global competition held in September 2021, benchmarked tidying tasks in the real home environments, and importa… ▽ More Tidying up a household environment using a mobile manipulator poses various challenges in robotics, such as adaptation to large real-world environmental variations, and safe and robust deployment in the presence of humans.The Partner Robot Challenge in World Robot Challenge (WRC) 2020, a global competition held in September 2021, benchmarked tidying tasks in the real home environments, and importantly, tested for full system performances.For this challenge, we developed an entire household service robot system, which leverages a data-driven approach to adapt to numerous edge cases that occur during the execution, instead of classical manual pre-programmed solutions. In this paper, we describe the core ingredients of the proposed robot system, including visual recognition, object manipulation, and motion planning. Our robot system won the second prize, verifying the effectiveness and potential of data-driven robot systems for mobile manipulation in home environments. △ Less

Submitted 21 July, 2022; v1 submitted 20 July, 2022; originally announced July 2022.

An Algorithm for Computing the Stratonovich's Value of Information

Authors: Akira Kamatsuka, Takahiro Yoshida, Koki Kazama, Toshiyasu Matsushima

Abstract: We propose an algorithm for computing Stratonovich's value of information (VoI) that can be regarded as an analogue of the distortion-rate function. We construct an alternating optimization algorithm for VoI under a general information leakage constraint and derive a convergence condition. Furthermore, we discuss algorithms for computing VoI under specific information leakage constraints, such as… ▽ More We propose an algorithm for computing Stratonovich's value of information (VoI) that can be regarded as an analogue of the distortion-rate function. We construct an alternating optimization algorithm for VoI under a general information leakage constraint and derive a convergence condition. Furthermore, we discuss algorithms for computing VoI under specific information leakage constraints, such as Shannon's mutual information (MI), $f$-leakage, Arimoto's MI, Sibson's MI, and Csiszar's MI. △ Less

Submitted 8 May, 2022; v1 submitted 5 May, 2022; originally announced May 2022.

Stochastic 2D Signal Generative Model with Wavelet Packets Basis Regarded as a Random Variable and Bayes Optimal Processing

Authors: Ryohei Oka, Yuta Nakahara, Toshiyasu Matsushima

Abstract: This study deals with two-dimensional (2D) signal processing using the wavelet packet transform. When the basis is unknown the candidate of basis increases in exponential order with respect to the signal size. Previous studies do not consider the basis as a random vaiables. Therefore, the cost function needs to be used to select a basis. However, this method is often a heuristic and a greedy searc… ▽ More This study deals with two-dimensional (2D) signal processing using the wavelet packet transform. When the basis is unknown the candidate of basis increases in exponential order with respect to the signal size. Previous studies do not consider the basis as a random vaiables. Therefore, the cost function needs to be used to select a basis. However, this method is often a heuristic and a greedy search because it is impossible to search all the candidates for a huge number of bases. Therefore, it is difficult to evaluate the entire signal processing under a criterion and also it does not always gurantee the optimality of the entire signal processing. In this study, we propose a stochastic generative model in which the basis is regarded as a random variable. This makes it possible to evaluate entire signal processing under a unified criterion i.e. Bayes criterion. Moreover we can derive an optimal signal processing scheme that achieves the theoretical limit. This derived scheme shows that all the bases should be combined according to the posterior in stead of selecting a single basis. Although exponential order calculations is required for this scheme, we have derived a recursive algorithm for this scheme, which successfully reduces the computational complexity from the exponential order to the polynomial order. △ Less

Submitted 1 May, 2022; v1 submitted 26 January, 2022; originally announced February 2022.

A Generalization of the Stratonovich's Value of Information and Application to Privacy-Utility Trade-off

Authors: Akira Kamatsuka, Takahiro Yoshida, Toshiyasu Matsushima

Abstract: The Stratonovich's value of information (VoI) is quantity that measure how much inferential gain is obtained from a perturbed sample under information leakage constraint. In this paper, we introduce a generalized VoI for a general loss function and general information leakage. Then we derive an upper bound of the generalized VoI. Moreover, for a classical loss function, we provide a achievable con… ▽ More The Stratonovich's value of information (VoI) is quantity that measure how much inferential gain is obtained from a perturbed sample under information leakage constraint. In this paper, we introduce a generalized VoI for a general loss function and general information leakage. Then we derive an upper bound of the generalized VoI. Moreover, for a classical loss function, we provide a achievable condition of the upper bound which is weaker than that of in previous studies. Since VoI can be viewed as a formulation of a privacy-utility trade-off (PUT) problem, we provide an interpretation of the achievable condition in the PUT context. △ Less

Submitted 27 January, 2022; originally announced January 2022.

Probability Distribution on Rooted Trees

Authors: Yuta Nakahara, Shota Saito, Akira Kamatsuka, Toshiyasu Matsushima

Abstract: The hierarchical and recursive expressive capability of rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. On the other hand, such hierarchical expressive capability causes a problem in tree selection to avoid overfitting. One unified approach to solve this is a Bayesian approach, on which the rooted tree i… ▽ More The hierarchical and recursive expressive capability of rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. On the other hand, such hierarchical expressive capability causes a problem in tree selection to avoid overfitting. One unified approach to solve this is a Bayesian approach, on which the rooted tree is regarded as a random variable and a direct loss function can be assumed on the selected model or the predicted value for a new data point. However, all the previous studies on this approach are based on the probability distribution on full trees, to the best of our knowledge. In this paper, we propose a generalized probability distribution for any rooted trees in which only the maximum number of child nodes and the maximum depth are fixed. Furthermore, we derive recursive methods to evaluate the characteristics of the probability distribution without any approximations. △ Less

Submitted 24 January, 2022; originally announced January 2022.

Comments: arXiv admin note: substantial text overlap with arXiv:2109.12825

Tool as Embodiment for Recursive Manipulation

Authors: Yuki Noguchi, Tatsuya Matsushima, Yutaka Matsuo, Shixiang Shane Gu

Abstract: Humans and many animals exhibit a robust capability to manipulate diverse objects, often directly with their bodies and sometimes indirectly with tools. Such flexibility is likely enabled by the fundamental consistency in underlying physics of object manipulation such as contacts and force closures. Inspired by viewing tools as extensions of our bodies, we present Tool-As-Embodiment (TAE), a param… ▽ More Humans and many animals exhibit a robust capability to manipulate diverse objects, often directly with their bodies and sometimes indirectly with tools. Such flexibility is likely enabled by the fundamental consistency in underlying physics of object manipulation such as contacts and force closures. Inspired by viewing tools as extensions of our bodies, we present Tool-As-Embodiment (TAE), a parameterization for tool-based manipulation policies that treat hand-object and tool-object interactions in the same representation space. The result is a single policy that can be applied recursively on robots to use end effectors to manipulate objects, and use objects as tools, i.e. new end-effectors, to manipulate other objects. By sharing experiences across different embodiments for grasping or pushing, our policy exhibits higher performance than if separate policies were trained. Our framework could utilize all experiences from different resolutions of tool-enabled embodiments to a single generic policy for each manipulation skill. Videos at https://sites.google.com/view/recursivemanipulation △ Less

Submitted 1 December, 2021; originally announced December 2021.

Probability Distribution on Full Rooted Trees

Authors: Yuta Nakahara, Shota Saito, Akira Kamatsuka, Toshiyasu Matsushima

Abstract: The recursive and hierarchical structure of full rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. In most of these cases, the full rooted tree is not a random variable; as such, model selection to avoid overfitting becomes problematic. A method to solve this problem is to assume a prior distribution on th… ▽ More The recursive and hierarchical structure of full rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. In most of these cases, the full rooted tree is not a random variable; as such, model selection to avoid overfitting becomes problematic. A method to solve this problem is to assume a prior distribution on the full rooted trees. This enables the optimal model selection based on the Bayes decision theory. For example, by assigning a low prior probability to a complex model, the maximum a posteriori estimator prevents the selection of the complex one. Furthermore, we can average all the models weighted by their posteriors. In this paper, we propose a probability distribution on a set of full rooted trees. Its parametric representation is suitable for calculating the properties of our distribution using recursive functions, such as the mode, expectation, and posterior distribution. Although such distributions have been proposed in previous studies, they are only applicable to specific applications. Therefore, we extract their mathematically essential components and derive new generalized methods to calculate the expectation, posterior distribution, etc. △ Less

Submitted 23 January, 2022; v1 submitted 27 September, 2021; originally announced September 2021.

Journal ref: Entropy 2022, 24(3), 328

A Stochastic Model for Block Segmentation of Images Based on the Quadtree and the Bayes Code for It

Authors: Yuta Nakahara, Toshiyasu Matsushima

Abstract: In information theory, lossless compression of general data is based on an explicit assumption of a stochastic generative model on target data. However, in lossless image compression, the researchers have mainly focused on the coding procedure that outputs the coded sequence from the input image, and the assumption of the stochastic generative model is implicit. In these studies, there is a diffic… ▽ More In information theory, lossless compression of general data is based on an explicit assumption of a stochastic generative model on target data. However, in lossless image compression, the researchers have mainly focused on the coding procedure that outputs the coded sequence from the input image, and the assumption of the stochastic generative model is implicit. In these studies, there is a difficulty in confirming the information-theoretical optimality of the coding procedure to the stochastic generative model. Hence, in this paper, we propose a novel stochastic generative model of images by redefining the implicit stochastic generative model in a previous coding procedure. That is based on the quadtree so that our model effectively represents the variable block size segmentation of images. Then, we construct the Bayes code optimal for the proposed stochastic generative model. In general, the computational cost to calculate the posterior distribution required in the Bayes code increases exponentially for the image size. However, we introduce an efficient algorithm to calculate it in the polynomial order of the image size without loss of the optimality. Some experiments are performed to confirm the flexibility of the proposed stochastic model and the efficiency of the introduced algorithm. △ Less

Submitted 7 June, 2021; originally announced June 2021.

Journal ref: Entropy 2021, 23, 991

An Efficient Bayes Coding Algorithm for the Non-Stationary Source in Which Context Tree Model Varies from Interval to Interval

Authors: Koshi Shimada, Shota Saito, Toshiyasu Matsushima

Abstract: The context tree source is a source model in which the occurrence probability of symbols is determined from a finite past sequence, and is a broader class of sources that includes i.i.d. and Markov sources. The proposed source model in this paper represents that a subsequence in each interval is generated from a different context tree model. The Bayes code for such sources requires weighting of th… ▽ More The context tree source is a source model in which the occurrence probability of symbols is determined from a finite past sequence, and is a broader class of sources that includes i.i.d. and Markov sources. The proposed source model in this paper represents that a subsequence in each interval is generated from a different context tree model. The Bayes code for such sources requires weighting of the posterior probability distributions for the change patterns of the context tree source and for all possible context tree models. Therefore, the challenge is how to reduce this exponential order computational complexity. In this paper, we assume a special class of prior probability distribution of change patterns and context tree models, and propose an efficient Bayes coding algorithm whose computational complexity is the polynomial order. △ Less

Submitted 13 May, 2021; v1 submitted 11 May, 2021; originally announced May 2021.

Co-Adaptation of Algorithmic and Implementational Innovations in Inference-based Deep Reinforcement Learning

Authors: Hiroki Furuta, Tadashi Kozuno, Tatsuya Matsushima, Yutaka Matsuo, Shixiang Shane Gu

Abstract: Recently many algorithms were devised for reinforcement learning (RL) with function approximation. While they have clear algorithmic distinctions, they also have many implementation differences that are algorithm-independent and sometimes under-emphasized. Such mixing of algorithmic novelty and implementation craftsmanship makes rigorous analyses of the sources of performance improvements across a… ▽ More Recently many algorithms were devised for reinforcement learning (RL) with function approximation. While they have clear algorithmic distinctions, they also have many implementation differences that are algorithm-independent and sometimes under-emphasized. Such mixing of algorithmic novelty and implementation craftsmanship makes rigorous analyses of the sources of performance improvements across algorithms difficult. In this work, we focus on a series of off-policy inference-based actor-critic algorithms -- MPO, AWR, and SAC -- to decouple their algorithmic innovations and implementation decisions. We present unified derivations through a single control-as-inference objective, where we can categorize each algorithm as based on either Expectation-Maximization (EM) or direct Kullback-Leibler (KL) divergence minimization and treat the rest of specifications as implementation details. We performed extensive ablation studies, and identified substantial performance drops whenever implementation details are mismatched for algorithmic choices. These results show which implementation or code details are co-adapted and co-evolved with algorithms, and which are transferable across algorithms: as examples, we identified that tanh Gaussian policy and network sizes are highly adapted to algorithmic types, while layer normalization and ELU are critical for MPO's performances but also transfer to noticeable gains in SAC. We hope our work can inspire future work to further demystify sources of performance improvements across multiple algorithms and allow researchers to build on one another's both algorithmic and implementational innovations. △ Less

Submitted 25 October, 2021; v1 submitted 31 March, 2021; originally announced March 2021.

Comments: Accepted at NeurIPS 2021. The implementation is available at: https://github.com/frt03/inference-based-rl

Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning

Authors: Hiroki Furuta, Tatsuya Matsushima, Tadashi Kozuno, Yutaka Matsuo, Sergey Levine, Ofir Nachum, Shixiang Shane Gu

Abstract: Progress in deep reinforcement learning (RL) research is largely enabled by benchmark task environments. However, analyzing the nature of those environments is often overlooked. In particular, we still do not have agreeable ways to measure the difficulty or solvability of a task, given that each has fundamentally different actions, observations, dynamics, rewards, and can be tackled with diverse R… ▽ More Progress in deep reinforcement learning (RL) research is largely enabled by benchmark task environments. However, analyzing the nature of those environments is often overlooked. In particular, we still do not have agreeable ways to measure the difficulty or solvability of a task, given that each has fundamentally different actions, observations, dynamics, rewards, and can be tackled with diverse RL algorithms. In this work, we propose policy information capacity (PIC) -- the mutual information between policy parameters and episodic return -- and policy-optimal information capacity (POIC) -- between policy parameters and episodic optimality -- as two environment-agnostic, algorithm-agnostic quantitative metrics for task difficulty. Evaluating our metrics across toy environments as well as continuous control benchmark tasks from OpenAI Gym and DeepMind Control Suite, we empirically demonstrate that these information-theoretic metrics have higher correlations with normalized task solvability scores than a variety of alternatives. Lastly, we show that these metrics can also be used for fast and compute-efficient optimizations of key design parameters such as reward shaping, policy architectures, and MDP properties for better solvability by RL algorithms without ever running full RL experiments. △ Less

Submitted 31 May, 2021; v1 submitted 23 March, 2021; originally announced March 2021.

Comments: Accepted to ICML2021. The code is available at: https://github.com/frt03/pic

Theoretical Analysis of the Advantage of Deepening Neural Networks

Authors: Yasushi Esaki, Yuta Nakahara, Toshiyasu Matsushima

Abstract: We propose two new criteria to understand the advantage of deepening neural networks. It is important to know the expressivity of functions computable by deep neural networks in order to understand the advantage of deepening neural networks. Unless deep neural networks have enough expressivity, they cannot have good performance even though learning is successful. In this situation, the proposed cr… ▽ More We propose two new criteria to understand the advantage of deepening neural networks. It is important to know the expressivity of functions computable by deep neural networks in order to understand the advantage of deepening neural networks. Unless deep neural networks have enough expressivity, they cannot have good performance even though learning is successful. In this situation, the proposed criteria contribute to understanding the advantage of deepening neural networks since they can evaluate the expressivity independently from the efficiency of learning. The first criterion shows the approximation accuracy of deep neural networks to the target function. This criterion has the background that the goal of deep learning is approximating the target function by deep neural networks. The second criterion shows the property of linear regions of functions computable by deep neural networks. This criterion has the background that deep neural networks whose activation functions are piecewise linear are also piecewise linear. Furthermore, by the two criteria, we show that to increase layers is more effective than to increase units at each layer on improving the expressivity of deep neural networks. △ Less

Submitted 24 September, 2020; originally announced September 2020.

Comments: 9 pages, 7 figures; accepted in 19th IEEE International Conference on Machine Learning and Applications (IEEE ICMLA 2020)

ACM Class: I.2.6; I.5.1

Journal ref: 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 479-484

Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization

Authors: Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, Shixiang Gu

Abstract: Most reinforcement learning (RL) algorithms assume online access to the environment, in which one may readily interleave updates to the policy with experience collection using that policy. However, in many real-world applications such as health, education, dialogue agents, and robotics, the cost or potential risk of deploying a new data-collection policy is high, to the point that it can become pr… ▽ More Most reinforcement learning (RL) algorithms assume online access to the environment, in which one may readily interleave updates to the policy with experience collection using that policy. However, in many real-world applications such as health, education, dialogue agents, and robotics, the cost or potential risk of deploying a new data-collection policy is high, to the point that it can become prohibitive to update the data-collection policy more than a few times during learning. With this view, we propose a novel concept of deployment efficiency, measuring the number of distinct data-collection policies that are used during policy learning. We observe that naïvely applying existing model-free offline RL algorithms recursively does not lead to a practical deployment-efficient and sample-efficient algorithm. We propose a novel model-based algorithm, Behavior-Regularized Model-ENsemble (BREMEN) that can effectively optimize a policy offline using 10-20 times fewer data than prior works. Furthermore, the recursive application of BREMEN is able to achieve impressive deployment efficiency while maintaining the same or better sample efficiency, learning successful policies from scratch on simulated robotic environments with only 5-10 deployments, compared to typical values of hundreds to millions in standard RL baselines. Codes and pre-trained models are available at https://github.com/matsuolab/BREMEN . △ Less

Submitted 23 June, 2020; v1 submitted 5 June, 2020; originally announced June 2020.

Evaluation of Error Probability of Classification Based on the Analysis of the Bayes Code: Extension and Example

Authors: Shota Saito, Toshiyasu Matsushima

Abstract: Suppose that we have two training sequences generated by parametrized distributions $P_{θ^*}$ and $P_{ξ^*}$, where $θ^*$ and $ξ^*$ are unknown true parameters. Given training sequences, we study the problem of classifying whether a test sequence was generated according to $P_{θ^*}$ or $P_{ξ^*}$. This problem can be thought of as a hypothesis testing problem and our aim is to analyze the weighted s… ▽ More Suppose that we have two training sequences generated by parametrized distributions $P_{θ^*}$ and $P_{ξ^*}$, where $θ^*$ and $ξ^*$ are unknown true parameters. Given training sequences, we study the problem of classifying whether a test sequence was generated according to $P_{θ^*}$ or $P_{ξ^*}$. This problem can be thought of as a hypothesis testing problem and our aim is to analyze the weighted sum of type-I and type-II error probabilities. Utilizing the analysis of the codeword lengths of the Bayes code, our previous study derived more refined bounds on the error probability than known previously. However, our previous study had the following deficiencies: i) the prior distributions of $θ$ and $ξ$ are the same; ii) the prior distributions of two hypotheses are uniform; iii) no numerical calculation at finite blocklength. This study solves these problems. We remove the restrictions i) and ii) and derive more general results than obtained previously. To deal with problem iii), we perform a numerical calculation for a concrete model. △ Less

Submitted 2 May, 2021; v1 submitted 8 October, 2019; originally announced October 2019.

Covariance Evolution for Spatially "Mt. Fuji" Coupled LDPC Codes

Authors: Yuta Nakahara, Toshiyasu Matsushima

Abstract: A spatially "Mt. Fuji" coupled low-density parity check (LDPC) ensemble is a modified version of the original spatially coupled (SC) LDPC ensemble. Its desirable properties are first observed in experimentally. The decoding error probability in the error floor region over the binary erasure channel (BEC) is theoretically analyzed later. In this paper, as the last piece of the theoretical analysis… ▽ More A spatially "Mt. Fuji" coupled low-density parity check (LDPC) ensemble is a modified version of the original spatially coupled (SC) LDPC ensemble. Its desirable properties are first observed in experimentally. The decoding error probability in the error floor region over the binary erasure channel (BEC) is theoretically analyzed later. In this paper, as the last piece of the theoretical analysis over the BEC, we analyze the decoding error probability in the waterfall region by modifying the covariance evolution which has been used to analyze the original SC-LDPC ensemble. △ Less

Submitted 17 August, 2019; v1 submitted 10 April, 2019; originally announced April 2019.

Comments: accepted to IEEE Information Theory Workshop (ITW) 2019

Distributed Stochastic Gradient Descent Using LDGM Codes

Authors: Shunsuke Horii, Takahiro Yoshida, Manabu Kobayashi, Toshiyasu Matsushima

Abstract: We consider a distributed learning problem in which the computation is carried out on a system consisting of a master node and multiple worker nodes. In such systems, the existence of slow-running machines called stragglers will cause a significant decrease in performance. Recently, coding theoretic framework, which is named Gradient Coding (GC), for mitigating stragglers in distributed learning h… ▽ More We consider a distributed learning problem in which the computation is carried out on a system consisting of a master node and multiple worker nodes. In such systems, the existence of slow-running machines called stragglers will cause a significant decrease in performance. Recently, coding theoretic framework, which is named Gradient Coding (GC), for mitigating stragglers in distributed learning has been established by Tandon et al. Most studies on GC are aiming at recovering the gradient information completely assuming that the Gradient Descent (GD) algorithm is used as a learning algorithm. On the other hand, if the Stochastic Gradient Descent (SGD) algorithm is used, it is not necessary to completely recover the gradient information, and its unbiased estimator is sufficient for the learning. In this paper, we propose a distributed SGD scheme using Low-Density Generator Matrix (LDGM) codes. In the proposed system, it may take longer time than existing GC methods to recover the gradient information completely, however, it enables the master node to obtain a high-quality unbiased estimator of the gradient at low computational cost and it leads to overall performance improvement. △ Less

Submitted 15 January, 2019; originally announced January 2019.

Non-Asymptotic Fundamental Limits of Guessing Subject to Distortion

Authors: Shota Saito, Toshiyasu Matsushima

Abstract: This paper investigates the problem of guessing subject to distortion, which was introduced by Arikan and Merhav. While the primary concern of the previous study was asymptotic analysis, our primary concern is non-asymptotic analysis. We prove non-asymptotic achievability and converse bounds of the moment of the number of guesses without side information (resp. with side information) by using a qu… ▽ More This paper investigates the problem of guessing subject to distortion, which was introduced by Arikan and Merhav. While the primary concern of the previous study was asymptotic analysis, our primary concern is non-asymptotic analysis. We prove non-asymptotic achievability and converse bounds of the moment of the number of guesses without side information (resp. with side information) by using a quantity based on the Rényi entropy (resp. the Arimoto-Rényi conditional entropy). Also, we introduce an error probability and show similar results. Further, from our bounds, we derive a single-letter characterization of the asymptotic exponent of guessing moment for a stationary memoryless source. △ Less

Submitted 9 January, 2019; v1 submitted 19 August, 2018; originally announced August 2018.

A Novel Scheme to Improve Lossless Image Coders by Explicit Description of Generative Model Classes

Authors: Yuta Nakahara, Toshiyasu Matsushima

Abstract: In this study, we propose a novel scheme for systematic improvement of lossless image compression coders from the point of view of the universal codes in information theory. In the proposed scheme, we describe a generative model class of images as a stochastic model. Using the Bayes codes, we are able to construct a lossless image compression coder which is optimal under the Bayes criterion for a… ▽ More In this study, we propose a novel scheme for systematic improvement of lossless image compression coders from the point of view of the universal codes in information theory. In the proposed scheme, we describe a generative model class of images as a stochastic model. Using the Bayes codes, we are able to construct a lossless image compression coder which is optimal under the Bayes criterion for a model class described appropriately. Since the compression coder is optimal for the assumed model class, we are able to focus on the expansion of the model class. To validate the efficiency of the proposed scheme, we construct a lossless image compression coder which achieves approximately 19.7% reduction of average coding rates of previous coders. △ Less

Submitted 15 April, 2019; v1 submitted 13 February, 2018; originally announced February 2018.

Comments: There are serious mistakes in the article

Cumulant Generating Function of Codeword Lengths in Variable-Length Lossy Compression Allowing Positive Excess Distortion Probability

Authors: Shota Saito, Toshiyasu Matsushima

Abstract: This paper considers the problem of variable-length lossy source coding. The performance criteria are the excess distortion probability and the cumulant generating function of codeword lengths. We derive a non-asymptotic fundamental limit of the cumulant generating function of codeword lengths allowing positive excess distortion probability. It is shown that the achievability and converse bounds a… ▽ More This paper considers the problem of variable-length lossy source coding. The performance criteria are the excess distortion probability and the cumulant generating function of codeword lengths. We derive a non-asymptotic fundamental limit of the cumulant generating function of codeword lengths allowing positive excess distortion probability. It is shown that the achievability and converse bounds are characterized by the Rényi entropy-based quantity. In the proof of the achievability result, the explicit code construction is provided. Further, we investigate an asymptotic single-letter characterization of the fundamental limit for a stationary memoryless source. △ Less

Submitted 11 January, 2018; v1 submitted 5 January, 2018; originally announced January 2018.

Comments: arXiv admin note: text overlap with arXiv:1701.01800

Journal ref: IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2113-2119, April 2023

Variable-Length Intrinsic Randomness Allowing Positive Value of the Average Variational Distance

Authors: Jun Yoshizawa, Shota Saito, Toshiyasu Matsushima

Abstract: This paper considers the problem of variable-length intrinsic randomness. We propose the average variational distance as the performance criterion from the viewpoint of a dual relationship with the problem formulation of variable-length resolvability. Previous study has derived the general formula of the $ε$-variable-length resolvability. We derive the general formula of the $ε$-variable-length in… ▽ More This paper considers the problem of variable-length intrinsic randomness. We propose the average variational distance as the performance criterion from the viewpoint of a dual relationship with the problem formulation of variable-length resolvability. Previous study has derived the general formula of the $ε$-variable-length resolvability. We derive the general formula of the $ε$-variable-length intrinsic randomness. Namely, we characterize the supremum of the mean length under the constraint that the value of the average variational distance is smaller than or equal to a constant $ε$. Our result clarifies a dual relationship between the general formula of $ε$-variable-length resolvability and that of $ε$-variable-length intrinsic randomness. We also derive a lower bound of the quantity characterizing our general formula. △ Less

Submitted 3 May, 2018; v1 submitted 5 January, 2018; originally announced January 2018.

Variable-Length Lossy Compression Allowing Positive Overflow and Excess Distortion Probabilities

Authors: Shota Saito, Hideki Yagi, Toshiyasu Matsushima

Abstract: This paper investigates the problem of variable-length lossy source coding allowing a positive excess distortion probability and an overflow probability of codeword lengths. Novel one-shot achievability and converse bounds of the optimal rate are established by a new quantity based on the smooth max entropy (the smooth Rényi entropy of order zero). To derive the achievability bounds, we give an ex… ▽ More This paper investigates the problem of variable-length lossy source coding allowing a positive excess distortion probability and an overflow probability of codeword lengths. Novel one-shot achievability and converse bounds of the optimal rate are established by a new quantity based on the smooth max entropy (the smooth Rényi entropy of order zero). To derive the achievability bounds, we give an explicit code construction based on a distortion ball instead of using the random coding argument. The basic idea of the code construction is similar to the optimal code construction in the variable-length lossless source coding. Our achievability bounds are slightly different, depending on whether the encoder is stochastic or deterministic. One-shot results yield a general formula of the optimal rate for blocklength $n$. In addition, our general formula is applied to asymptotic analysis for a stationary memoryless source. As a result, we derive a single-letter characterization of the optimal rate by using the rate-distortion and rate-dispersion functions. △ Less

Submitted 14 December, 2018; v1 submitted 7 January, 2017; originally announced January 2017.

Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channels

Authors: Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

Abstract: In this paper, we develop a new decoding algorithm of a binary linear codes for symbol-pair read channels. Symbol-pair read channel has recently been introduced by Cassuto and Blaum to model channels with high write resolution but low read resolution. The proposed decoding algorithm is based on a linear programming (LP). It is proved that the proposed LP decoder has the maximum-likelihood (ML) cer… ▽ More In this paper, we develop a new decoding algorithm of a binary linear codes for symbol-pair read channels. Symbol-pair read channel has recently been introduced by Cassuto and Blaum to model channels with high write resolution but low read resolution. The proposed decoding algorithm is based on a linear programming (LP). It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance $d_{fp}$ of a code which is a lower bound on the pair distance. It is proved that the proposed LP decoder will correct up to $\lceil d_{fp}/2\rceil-1$ pair errors. △ Less

Submitted 29 September, 2015; v1 submitted 7 August, 2015; originally announced August 2015.

Comments: 15pages, 2 figures

Information Spectrum Approach to Overflow Probability of Variable-Length Codes with Conditional Cost Function

Authors: Ryo Nomura, Toshiyasu Matsushima

Abstract: Lossless variable-length source coding with unequal cost function is considered for general sources. In this problem, the codeword cost instead of codeword length is important. The infimum of average codeword cost has already been determined for general sources. We consider the overflow probability of codeword cost and determine the infimum of achievable overflow threshold. Our analysis is on the… ▽ More Lossless variable-length source coding with unequal cost function is considered for general sources. In this problem, the codeword cost instead of codeword length is important. The infimum of average codeword cost has already been determined for general sources. We consider the overflow probability of codeword cost and determine the infimum of achievable overflow threshold. Our analysis is on the basis of information-spectrum methods and hence valid through the general source. △ Less

Submitted 8 May, 2012; v1 submitted 6 May, 2012; originally announced May 2012.

Comments: to be presented at ISIT 2012

Bayesian Forecasting of WWW Traffic on the Time Varying Poisson Model

Authors: Daiki Koizumi, Toshiyasu Matsushima, Shigeichi Hirasawa

Abstract: Traffic forecasting from past observed traffic data with small calculation complexity is one of important problems for planning of servers and networks. Focusing on World Wide Web (WWW) traffic as fundamental investigation, this paper would deal with Bayesian forecasting of network traffic on the time varying Poisson model from a viewpoint from statistical decision theory. Under this model, we w… ▽ More Traffic forecasting from past observed traffic data with small calculation complexity is one of important problems for planning of servers and networks. Focusing on World Wide Web (WWW) traffic as fundamental investigation, this paper would deal with Bayesian forecasting of network traffic on the time varying Poisson model from a viewpoint from statistical decision theory. Under this model, we would show that the estimated forecasting value is obtained by simple arithmetic calculation and expresses real WWW traffic well from both theoretical and empirical points of view. △ Less

Submitted 2 December, 2009; v1 submitted 22 June, 2009; originally announced June 2009.

Comments: 8 pages, 6 figures. This paper was published in Proceeding of The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'09) in July, 2009. In version of v4, research grants are included in acknowledgment

ACM Class: D.4.8; G.3; C.2.3