Language：English   Publishing type：Research paper (international conference proceedings)  

We consider a single machine scheduling problem to minimize total flow time under precedence constraints, which is NP-hard. Matsumoto et al. proposed an exact algorithm that consists of two phases: first construct a Multi-valued Decision Diagram (MDD) to represent feasible permutations of jobs, and then find the shortest path in the MDD which corresponds to the optimal solution. Although their algorithm performs significantly better than standard IP solvers for problems with dense constraints, the performance rapidly diminishes when the number of constraints decreases, which is due to the exponential growth of MDDs. In this paper, we introduce an equivalence relation among feasible permutations and show that it suffices to construct an MDD that maintains only one representative for each equivalence class. Experimental results show that our algorithm outperforms Matsumoto et al.’s algorithm for problems with sparse constraints, while keeping good performance for dense constraints. Moreover, we show that Matsumoto et al.’s algorithm can be extended for solving a more general problem of minimizing weighted total flow time.

DOI： 10.1007/978-3-030-25005-8_30

Language：English   Publishing type：Research paper (international conference proceedings)  

We present a short survey on recent results on combinatorial online prediction in the adversarial setting.

DOI： 10.23919/ISITA.2018.8664224

Language：English   Publishing type：Research paper (scientific journal)  

本論文では，ZDDと呼ばれる圧縮データ構造を用いてデータを圧縮した上で，圧縮したデータ上でブースティングという機械学習手法が効率よく計算できる事を明らかにした．ビッグデータの解析において，省スペースで計算が出来ることは大きな利点である．本研究の興味深い点は，組合せ論的オンライン予測という（一見）全く異なる機械学習分野の知見が圧縮情報処理に活かされたことである．

DOI： https://doi.org/10.1016/j.tcs.2018.11.027

Other Link： https://doi.org/10.1016/j.tcs.2018.11.027

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.

DOI： 10.1587/transfun.E101.A.1334

Language：English   Publishing type：Research paper (scientific journal)  

We prove generalization error bounds of classes of low-rank matrices with some norm constraints for collaborative filtering tasks. Our bounds are tighter, compared to known bounds using rank or the related quantity only, by taking the additional L₁ and L_∞ constraints into account. Also, we show that our bounds on the Rademacher complexity of the classes are optimal.

DOI： 10.1587/transinf.2017EDP7339

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2017EDP7233

Language：English   Publishing type：Research paper (international conference proceedings)  

本論文では，ZDDと呼ばれる圧縮データ構造を用いてデータを圧縮した上で，圧縮したデータ上でブースティングという機械学習手法が効率よく計算できる事を明らかにした．ビッグデータの解析において，省スペースで計算が出来ることは大きな利点である．本研究の興味深い点は，組合せ論的オンライン予測という（一見）全く異なる機械学習分野の知見が圧縮情報処理に活かされたことである．

DOI： 10.1007/978-3-319-75172-6_17

Language：English   Publishing type：Research paper (international conference proceedings)  

Computer-based support for learning of elderly people is now considered as an important issue in the super-aged society. Extra cares are needed for elderly people’s learning compared to younger people, since they might have difficulty in using computers, reduced cognitive ability and other physical problems which make them less motivated. Key components of a better learning support system are sensing the contexts surrounding elderly people and providing appropriate feedbacks to them. In this paper, we review some existing techniques of the contextual bandit framework in the machine learning literature, which could be potentially useful for online decision making scenarios given contexts. We also discuss issues and challenges to apply the framework.

DOI： 10.1007/978-3-319-91131-1_14

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2016.07.033

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-319-46379-7_19

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-319-24486-0_22

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/11894841_25

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023fcp0004

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023edp7023

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2023fcp0005

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/GLOBECOM54140.2023.10437383

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1007/978-3-031-49193-1_2

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/IoTaIS60147.2023.10346048

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/ISI58743.2023.10297252

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2310.12629

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/PIMRC56721.2023.10293924

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1007/978-3-031-45275-8_32

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/MetaCom57706.2023.00150

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2306.15856

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/ACCESS.2023.3244781

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/jac-ecc56395.2022.10043887

Language：Others   Publishing type：Research paper (scientific journal)  

Intelligent reconfigurable surface (IRS) is a competitive relaying technology to widen the WiGig coverage range, as it offers an effective means of addressing blocking issues. However, selecting the optimal IRS relay for maximum attainable data rate is a time-consuming process, as it requires WiGig beamforming training (BT) to tune the phase shifts (PSs) for WiGig base station (WGBS) and IRS relays. This paper proposes a self-learning-based budgeted Thomson sampling approach for IRS relay probing (BTS-IRS) to address this challenge. The BT time cost of probing the IRS relay is incorporated into the main BTS formula, where both payoff and cost posterior distributions are sampled separately, their ratio is estimated, and the arm/IRS relay with the highest ratio is decided. This enables the IRS relay to be chosen with the lowest BT time cost. Numerical results demonstrate the improved performance of the BTS-IRS relaying technique regarding BT time consumption/cost, spectral efficiency, and attainable data rate when compared to other benchmarks.

DOI： 10.3390/electronics12051146

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/CCNC51644.2023.10060437

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s12652-022-04475-8

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/pimrc54779.2022.9978021

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1049/cmu2.12474

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/ACCESS.2022.3195303

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/ACCESS.2022.3202956

Language：Others   Publishing type：Research paper (scientific journal)  

Recently, hybrid band communications have received much attention to fulfil the exponentially growing user demands in next-generation communication networks. Still, determining the best band to communicate over is a challenging issue, especially in the dynamic channel conditions in multi-band wireless systems. In this paper, we manipulate a practical online-learning-based solution for the best band/channel selection in hybrid radio frequency and visible light communication (RF/VLC) wireless systems. The best band selection difficulty is formulated as a multi-armed bandit (MAB) with cost subsidy, in which the learner (transmitter) endeavors not only to increase his total reward (throughput) but also reduce his cost (energy consumption). Consequently, we propose two hybrid band selection (HBS) algorithms, named cost subsidy upper confidence bound (CSUCB-HBS) and cost subsidy Thompson sampling (CSTS-HBS), to efficiently handle this problem and obtain the best band with high throughput and low energy consumption. Extensive simulations confirm that CSTS-/CSUCB-HBS outperform the naive TS/UCB and heuristic HBS approaches regarding energy consumption, energy efficiency, throughput, and convergence speed.

DOI： 10.3390/electronics11111782

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/JSYST.2021.3089536

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/LWC.2022.3164939

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/TVT.2022.3163078

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/JIOT.2022.3162135

Language：Others   Publishing type：Research paper (scientific journal)  

We consider a variant of the online semi-definite programming problem (OSDP). Specifically, in our problem, the setting of the decision space is a set of positive semi-definite matrices constrained by two norms in parallel: the L∞ norm to the diagonal entries and the Γ-trace norm, which is a generalized trace norm with a positive definite matrix Γ. Our setting recovers the original one when Γ is an identity matrix. To solve this problem, we design a follow-the-regularized-leader algorithm with a Γ-dependent regularizer, which also generalizes the log-determinant function. Next, we focus on online binary matrix completion (OBMC) with side information and online similarity prediction with side information. By reducing to the OSDP framework and applying our proposed algorithm, we remove the logarithmic factors in the previous mistake bound of the above two problems. In particular, for OBMC, our bound is optimal. Furthermore, our result implies a better offline generalization bound for the algorithm, which is similar to those of SVMs with the best kernel, if the side information is involved in advance.

DOI： 10.3390/math10071055

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.3390/s22062179

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/mnet.103.2100587

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.3390/s21082835

Language：Others   Publishing type：Research paper (scientific journal)  

Device-to-device (D2D) communication is a promising paradigm for the fifth generation (5G) and beyond 5G (B5G) networks. Although D2D communication provides several benefits, including limited interference, energy efficiency, reduced delay, and network overhead, it faces a lot of technical challenges such as network architecture, and neighbor discovery, etc. The complexity of configuring D2D links and managing their interference, especially when using millimeter-wave (mmWave), inspire researchers to leverage different machine-learning (ML) techniques to address these problems towards boosting the performance of D2D networks. In this paper, a comprehensive survey about recent research activities on D2D networks will be explored with putting more emphasis on utilizing mmWave and ML methods. After exploring existing D2D research directions accompanied with their existing conventional solutions, we will show how different ML techniques can be applied to enhance the D2D networks performance over using conventional ways. Then, still open research directions in ML applications on D2D networks will be investigated including their essential needs. A case study of applying multi-armed bandit (MAB) as an efficient online ML tool to enhance the performance of neighbor discovery and selection (NDS) in mmWave D2D networks will be presented. This case study will put emphasis on the high potency of using ML solutions over using the conventional non-ML based methods for highly improving the average throughput performance of mmWave NDS.

DOI： 10.3390/electronics10020169

Language：Others  

DOI： 10.1007/978-3-030-67731-2_15

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/gcwkshps50303.2020.9367568

Language：Others   Publishing type：Research paper (other academic)  

DOI： 10.1109/wpmc50192.2020.9309495

Language：Others   Publishing type：Research paper (scientific journal)  

We propose a new formulation of multiple-instance learning (MIL), in which a unit of data consists of a set of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a “shapelet” (or pattern), where the similarity of a bag with a shapelet is the maximum similarity of instances in the bag. In previous work, some of the training instances have been chosen as shapelets with no theoretical justification. In our formulation, we use all possible, and thus infinitely many, shapelets, resulting in a richer class of classifiers. We show that the formulation is tractable, that is, it can be reduced through linear programming boosting (LPBoost) to difference of convex (DC) programs of finite (actually polynomial) size. Our theoretical result also gives justification to the heuristics of some previous work. The time complexity of the proposed algorithm highly depends on the size of the set of all instances in the training sample. To apply to the data containing a large number of instances, we also propose a heuristic option of the algorithm without the loss of the theoretical guarantee. Our empirical study demonstrates that our algorithm uniformly works for shapelet learning tasks on time-series classification and various MIL tasks with comparable accuracy to the existing methods. Moreover, we show that the proposed heuristics allow us to achieve the result in reasonable computational time.

DOI： 10.1162/neco_a_01297

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/lcomm.2020.2991535

Language：Others   Publishing type：Research paper (scientific journal)  

Recently, unmanned aerial vehicle (UAV)-based communications gained a lot of attention due to their numerous applications, especially in rescue services in post-disaster areas where the terrestrial network is wholly malfunctioned. Multiple access/gateway UAVs are distributed to fully cover the post-disaster area as flying base stations to provide communication coverage, collect valuable information, disseminate essential instructions, etc. The access UAVs after gathering/broadcasting the necessary information should select and fly towards one of the surrounding gateways for relaying their information. In this paper, the gateway UAV selection problem is addressed. The main aim is to maximize the long-term average data rates of the UAVs relays while minimizing the flights’ battery cost, where millimeter wave links, i.e., using 30~300 GHz band, employing antenna beamforming, are used for backhauling. A tool of machine learning (ML) is exploited to address the problem as a budget-constrained multi-player multi-armed bandit (MAB) problem. In this setup, access UAVs act as the players, and the arms are the gateway UAVs, while the rewards are the average data rates of the constructed relays constrained by the battery cost of the access UAV flights. In this decentralized setting, where information is neither prior available nor exchanged among UAVs, a selfish and concurrent multi-player MAB strategy is suggested. Towards this end, three battery-aware MAB (BA-MAB) algorithms, namely upper confidence bound (UCB), Thompson sampling (TS), and the exponential weight algorithm for exploration and exploitation (EXP3), are proposed to realize gateways selection efficiently. The proposed BA-MAB-based gateway UAV selection algorithms show superior performance over approaches based on near and random selections in terms of total system rate and energy efficiency.

DOI： 10.3390/s20143947

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1587/transinf.2019fcf0001

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2018.11.027

Language：English   Publishing type：Research paper (international conference proceedings)  

We consider the recognition problem of Japanese historical handwritten characters called “Kuzushiji”. Unlike modern characters, Kuzushiji characters are harder to recognize partly because many of them are connected and not separated by spaces without any segmentation information. We propose two methods for segmentation and recognition of Kuzushiji characters. The first method learns segmentation rules and character classifiers simultaneously from data sets with character labels and segmentation information. Second method is for segmentation and can be used with any single character recognizer. Our methods outperform other baselines and achieve the state-of-the-art accuracy on both segmentation and recognition tasks on data sets of three consecutive Kuzushiji characters.

DOI： 10.1145/3352631.3352642

Language：English   Publishing type：Research paper (international conference proceedings)  

Extended learning environments involving system to collect data for learning analytics and to support learners will be useful for all-age education. As the first steps towards to build new learning environments, we developed a system for multimodal learning analytics using eye-tracker and EEG measurement, and inclusive user interface design for elderly learners by dual-tablet system. Multimodal learning analytics system can be supportive to extract where and how learners with varied backgrounds feel difficulty in learning process. The eye-tracker can retrieve information where the learners paid attention. EEG signals will provide clues to estimate their mental states during gazes in learning. We developed simultaneous measurement system of these multimodal responses and are trying to integrate the information to explore learning problems. A dual-tablet user interface with simplified visual layers and more intuitive operations was designed aiming to reduce the physical and mental loads of elderly learners. A prototype was developed based on a cross-platform framework, which is being refined by iterative formative evaluations participated by elderlies, in order to improve the usability of the interface design. We propose a system architecture applying the multimodal learning analytics and the user-friendly design for elderly learners, which couples learning analytics “in the wild” environment and learning analytics in controlled lab environments.

DOI： 10.1007/978-3-030-22580-3_35

Language：English   Publishing type：Research paper (international conference proceedings)  

To improve designs of e-learning materials, it is necessary to know which word or figure a learner felt "difficult" in the materials. In this pilot study, we measured electroencephalography (EEG) and eye gaze data of learners and analyzed to estimate which area they had difficulty to learn. The developed system realized simultaneous measurements of physiological data and subjective evaluations during learning. Using this system, we observed specific EEG activity in difficult pages. Integrating of eye gaze and EEG measurements raised a possibility to determine where a learner felt “difficult” in a page of learning materials. From these results, we could suggest that the multimodal measurements of EEG and eye gaze would lead to effective improvement of learning materials. For future study, more data collection using various materials and learners with different backgrounds is necessary. This study could lead to establishing a method to improve e-learning materials based on learners' mental states.

DOI： 10.1145/3330430.3333648

Language：English   Publishing type：Research paper (international conference proceedings)  

Extended learning support systems for all-age education requires inclusive user interface design, especially for elderly users. A dual-tablet user interface with simplified visual layers and more intuitive operations was proposed aiming to reduce the physical and mental loads of elderly learners. An initial prototype with basic functions of viewing learning material was developed based on a cross-platform framework. Two preliminary user experiments participated by elderly volunteers were carried out for formative evaluations, in order to improve the usability of the interface design iteratively. The prototype was modified based on the participants’ comments and observation of their operations during the experiments. Additional findings of the elderly users’ preference and tendency were discussed for further development.

DOI： 10.1145/3330430.3333650

Language：English   Publishing type：Research paper (international conference proceedings)  

We consider a job scheduling problem under precedence constraints, a classical problem for a single processor and multiple jobs to be done. The goal is, given processing time of n fixed jobs and precedence constraints over jobs, to find a permutation of n jobs that minimizes the total flow time, i.e., the sum of total wait time and processing times of all jobs, while satisfying the precedence constraints. The problem is an integer program and is NP-hard in general. We propose a decision diagram π-MDD, for solving the scheduling problem exactly. Our diagram is suitable for solving linear optimization over permutations with precedence constraints. We show the e ectiveness of our approach on the experiments on large scale artificial scheduling problems.

DOI： 10.4230/LIPIcs.SEA.2018.5

Language：English   Publishing type：Research paper (other academic)  

Extending Learning Analytics Platforms to Support Elderly People

Language：English   Publishing type：Research paper (international conference proceedings)  

As smart technologies pervade our everyday environments, they change what people should learn to live meaningfully as valuable participants of our society. For instance, ubiquitous availability of smart devices and communication networks may have reduced the burden for people to remember factual information. At the same time, they may have increased the benefits to master the uses of new digital technologies. In the midst of such a social and technological shift, we could design novel integrated platforms that support people at all ages to learn, work, collaborate, and co-create easily. In this paper, we discuss our ideas and first steps towards building an extended learning analytics platform that elderly people and unskilled adults can use. By understanding the characteristics and needs of elderly learners and addressing critical user interface issues, we can build pervasive and inclusive learning analytics platforms that trigger contextual reminders to support people at all ages to live and learn actively regardless of age-related differences of cognitive capabilities. We discuss that resolving critical usability problems for elderly people could open up a plethora of opportunities for them to search and exploit vast amount of information to achieve various goals.

DOI： 10.1007/978-3-319-91131-1_6

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-319-49304-6_32

Language：English   Publishing type：Research paper (scientific journal)  

The permutahedron is the convex polytope with vertex set consisting of the vectors (pi (1),..., pi (n)) for all permutations (bijections) pi over {1,...,n} We study a bandit game in which, at each step t, an adversary chooses a hidden weight vector st, a player chooses a vertex pi(t) of the permutahedron and suffers an observed instantaneous loss of Sigma(n)(i=1) pi(t)(i)s(t)(i).
We study the problem in two different approaches. In the two approaches, we assume that st is a point in the polytope dual to the permutahedron. Algorithm CombBand of Cesa-Bianchi et al. (2012) guarantees a regret of 0 (n root T log n) after T steps. Unfortunately, CombBand requires at each step an n-by-n matrix permanent computation, a #P-hard problem. Approximating the permanent is possible in the impractical running time of 0 (n(10)), with an additional heavy inverse-polynomial dependence on the sought accuracy. In the first approach, we provide an algorithm of slightly worse regret 0 (n(3/2)root T) but with more realistic time complexity 0 (n(3)) per step. The technical contribution is a bound on the variance of the Plackett-Luce noisy sorting process's 'pseudo loss', obtained by establishing positive semi-definiteness of a family of 3-by-3 matrices of rational functions in exponents of 3 parameters.
In the second approach, we present and analyze an algorithm based on Bubeck et al.'s (2012) OSMD approach with a novel projection and decomposition technique for the permutahedron. The second algorithm's running time and regret guarantees are similar to our first algorithm, modulo a numerical line search procedure the running time of which we have not been able to analyze. It is interesting that the two approaches are totally different.
The main open problem from this work is whether there exists a bandit algorithm for this problem with both optimal regret of 0 (n root T) and running time of 0 (n(3)) for either regime, or there is an inherent tradeoff between the two performance measures. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2016.07.033

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

We consider the learning problem under an online Markov decision process (MDP) aimed at learning the time-dependent decision-making policy of an agent that minimizes the regret-the difference from the best fixed policy. The difficulty of online MDP learning is that the reward function changes over time. In this letter, we show that a simple online policy gradient algorithm achieves regret O(root T) for T steps under a certain concavity assumption and O(log T) under a strong concavity assumption. To the best of our knowledge, this is the first work to present an online MDP algorithm that can handle continuous state, action, and parameter spaces with guarantee. We also illustrate the behavior of the proposed online policy gradient method through experiments.

DOI： 10.1162/NECO_a_00808

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1162/NECO_a_00808

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-662-44851-9_23

Language：English   Publishing type：Research paper (scientific journal)  

We consider Monte Carlo tree search problem, a variant of Min-Max tree search problem where the score of each leaf is the expectation of some Bernoulli variables and not explicitly given but can be estimated through (random) playouts. The goal of this problem is, given a game tree and an oracle that returns an outcome of a playout, to find a child node of the root which attains an approximate min-max score. This problem arises in two player games such as computer Go. We propose a simple and efficient algorithm for Monte Carlo tree search problem.

DOI： 10.1587/transinf.E97.D.392

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

We propose online prediction algorithms for data streams whose characteristics might change over time. Our algorithms are applications of online learning with experts. In particular, our algorithms combine base predictors over sliding windows with different length as experts. As a result, our algorithms are guaranteed to be competitive with the base predictor with the best fixed-length sliding window in hindsight.

DOI： 10.1587/transinf.E94.D.1917

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

We study the problem of classification when only a dissimilarity function between objects is accessible. That is, data samples are represented not by feature vectors but in terms of their pairwise dissimilarities. We establish sufficient conditions for dissimilarity functions to allow building accurate classifiers. The theory immediately suggests a learning paradigm: construct an ensemble of simple classifiers, each depending on a pair of examples; then find a convex combination of them to achieve a large margin. We next develop a practical algorithm referred to as dissimilarity-based boosting (DBoost) for learning with dissimilarity functions under theoretical guidance. Experiments on a variety of databases demonstrate that the DBoost algorithm is promising for several dissimilarity measures widely used in practice.

DOI： 10.1162/neco.2008.08-06-805

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Kazuyuki Narisawa, Hideo Bannnai, Kohei Hatano, and Masayuki Takeda

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Kazuyuki Narisawa, Hideo Bannnai, Kohei Hatano, and Masayuki Takeda

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Kohei Hatano and Osamu Watanabe ``Learning r-of-k Functions by Boosting", Fifteenth International Conference on Algorithmic Learning Theory(ALT2004),2004

Language：English   Publishing type：Research paper (scientific journal)  

We improve the analysis of the decision tree boosting algorithm proposed by Mansour and McAllester. For binary classification problems, the algorithm of Mansour and McAllester constructs a multi-way branching decision tree using a set of multi-class hypotheses. Mansour and McAllester proved that it works under certain conditions. We give a rigorous analysis of the algorithm and simplify the conditions. From this simplification, we can provide a simpler algorithm, for which no prior knowledge on the quality of weak hypotheses is necessary.

DOI： 10.1007/s00224-003-1064-z

Language：English   Publishing type：Research paper (scientific journal)  

Kohei Hatano, ``A Simple Boosting Algorithm Using Multi-Way Branching Decision Trees'',Theory of Computing Systems 37, 503-518, 2004

Repository Public URL： http://hdl.handle.net/2324/1523960

Language：English   Publishing type：Research paper (international conference proceedings)  

Kohei Hatano and Manfred K. Warmuth,``Boosting versus Covering",Seventeenth Annual Conference on Neural Information Processing Systems(NIPS2003),2003

Language：English   Publishing type：Research paper (international conference proceedings)  

Kohei Hatano,``A Simpler Analysis of The Multi-Way Branching Decision Tree Boosting Algorithm", Twelfth International Conference on Algorithmic Learning Theory(ALT2001), 2001

Event date： 2020.9

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン開催   Country：Japan  

Event date： 2020.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2020.2

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2019.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋市   Country：Japan  

Event date： 2019.9

Language：English   Presentation type：Oral presentation (general)  

Venue：信州大学   Country：Japan  

Event date： 2019.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：北海道大学   Country：Japan  

Event date： 2019.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：理化学研究所革新知能統合研究センター   Country：Japan  

Event date： 2018.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：札幌市   Country：Japan  

Event date： 2018.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：北海道大学   Country：Japan  

Event date： 2018.3 - 2017.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：高松市   Country：Japan  

Event date： 2018.2

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2017.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京大学   Country：Japan  

Event date： 2017.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：山形県天童市   Country：Japan  

Event date： 2017.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京工業大学   Country：Japan  

Event date： 2017.1

Language：Japanese   Presentation type：Symposium, workshop panel (public)  

Venue：九州大学   Country：Japan  

Other Link： http://catalog.lib.kyushu-u.ac.jp/handle/2324/1794496/hatano.pdf

Event date： 2016.7 - 2015.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：沖縄科学技術大学院大学   Country：Japan  

Event date： 2016.7 - 2015.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：沖縄科学技術大学院大学   Country：Japan  

Event date： 2015.6

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：沖縄科学技術大学院大学   Country：Japan  

Event date： 2015.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：統計数理研究所   Country：Japan  

Event date： 2014.12

Language：English   Presentation type：Oral presentation (general)  

Venue：Montreal   Country：Canada  

Event date： 2014.12

Language：English   Presentation type：Oral presentation (general)  

Venue：Montreal   Country：Canada  

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋大学   Country：Japan  

Event date： 2014.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：岩国   Country：Japan  

Event date： 2013.12

Language：English   Presentation type：Oral presentation (general)  

Venue：Technion   Country：Israel  

Event date： 2013.11

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2013.9

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福岡   Country：Japan  

Event date： 2013.9

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：鳥取大学   Country：Japan  

Event date： 2013.4

Language：English   Presentation type：Oral presentation (general)  

Venue：Sendai   Country：Japan  

Event date： 2013.1

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.12

Language：English   Presentation type：Oral presentation (general)  

Venue：Lake Tahoe   Country：United States  

Event date： 2011.12

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2011.12

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2011.11

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2011.11

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2011.8

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2010.9

Presentation type：Oral presentation (general)  

Venue：九州大学   Country：Japan  

Event date： 2009.10

Presentation type：Symposium, workshop panel (public)  

Country：Japan  

Event date： 2008.7

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2008.3

Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Presentation type：Symposium, workshop panel (public)  

Venue：Tokyo   Country：Japan  

Presentation type：Oral presentation (general)  

Venue：福岡   Country：Japan  

Boosting using classifiers with nearly one-sided error

Presentation type：Oral presentation (general)  

Venue：京都   Country：Japan  

Efficient online learning of linear threshold functions with large biases.

Presentation type：Oral presentation (general)  

Venue：京都   Country：Japan  

Online Learning of Maximum p-Norm Margin Classifiers with Bias

Presentation type：Oral presentation (general)  

Venue：京都   Country：Japan  

Online Learning Based On Maximum Entropy Principle

Presentation type：Oral presentation (general)  

Venue：京都   Country：Japan  

Online Rank Aggregation

Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Online Rank Aggregation

Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Learning evaluation functions for Shogi via bipertite ranking learning with SVMs

Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Learning evaluation functions for Shogi via bipertite ranking learning with SVMs

Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Online Rank Aggregation

Presentation type：Oral presentation (general)  

Venue：琉球大学   Country：Japan  

Online Rank Aggregation

Event date： 2024.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：札幌   Country：Japan  

Event date： 2023.10 - 2023.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：小倉   Country：Japan  

Event date： 2023.10 - 2023.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：小倉   Country：Japan  

Event date： 2023.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：函館   Country：Japan  

Event date： 2023.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：函館   Country：Japan  

Event date： 2023.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：定山渓   Country：Japan  

Event date： 2023.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Event date： 2023.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京   Country：Japan  

Event date： 2022.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：つくば   Country：Japan  

Event date： 2022.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：つくば   Country：Japan  

Event date： 2022.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：秋田   Country：Japan  

Event date： 2022.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：秋田   Country：Japan  

Event date： 2022.2

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン開催   Country：Japan  

Event date： 2022.2

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン開催   Country：Japan  

Event date： 2021.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン開催   Country：Japan  

Event date： 2021.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン開催   Country：Japan  

Event date： 2019.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：愛知県蒲郡市竹島海岸   Country：Japan  

Event date： 2019.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福島県磐梯熱海温泉   Country：Japan  

Event date： 2019.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福島県磐梯熱海温泉   Country：Japan  

Event date： 2019.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福岡大学   Country：Japan  

Event date： 2019.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福岡大学   Country：Japan  

Event date： 2019.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：福岡大学   Country：Japan  

Event date： 2018.7 - 2017.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：千葉県山武軍九十九里町   Country：Japan  

Event date： 2017.12

Language：English   Presentation type：Oral presentation (general)  

Venue：ロングビーチ，米国   Country：Japan  

Event date： 2017.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：東京大学   Country：Japan  

Event date： 2017.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：山形県天童市   Country：Japan  

Event date： 2017.2

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2016.12

Language：English   Presentation type：Oral presentation (general)  

Venue：Barcelona   Country：Japan  

Event date： 2016.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2016.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2016.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：かんぽの宿 大和平群   Country：Japan  

Event date： 2016.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：かんぽの宿 大和平群   Country：Japan  

Event date： 2016.1

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：京都大学   Country：Japan  

Event date： 2015.7 - 2014.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：加賀   Country：Japan  

Event date： 2015.7 - 2014.7

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：加賀   Country：Japan  

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：つくば   Country：Japan  

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：つくば   Country：Japan  

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：石垣島   Country：Japan  

Combinatorial MTS problem

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：石垣島   Country：Japan  

Online scheduling of precedence-constrained jobs on a single machine

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2014.3

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2014.3

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2013.11

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2013.11

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2013.7

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2013.3 - 2012.3

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.11

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.7

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.7

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.6

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.2

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2012.1 - 2012.2

Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2008.6

Presentation type：Oral presentation (general)  

Country：Japan  

Presentation type：Oral presentation (general)  

Country：Japan  

Presentation type：Oral presentation (general)  

Venue：九州大学   Country：Japan  

Presentation type：Oral presentation (general)  

Venue：IBM 東京基礎研究所   Country：Japan  

Presentation type：Oral presentation (general)  

Venue：NTTコミュニケーション科学基礎研究所   Country：Japan  

Presentation type：Oral presentation (general)  

Venue：京都大学  

Boosting by filtering using an information-theoretic criterion

Presentation type：Oral presentation (general)  

Venue：京都大学  

An Efficient Boosting by Filtering

Presentation type：Oral presentation (general)  

Country：Japan  

Language：Japanese  

高齢者向け学習支援システムのためのデュアルタブレット・ユーザインタフェースの提案と実現

Language：Japanese  

本研究では講義資料のページ毎の難易度を分析する新たなアプローチを提案する．分析対象としてデジタル教科書システムで配信されている講義資料を用いる．デジタル教科書システムではページの移動操作に加えページのブックマークやマーカーといった操作ログも記録される．今回は14回の講義中(1回90分)に収集されたデジタル教科書の操作ログを使用し，456人の学生からなる計110,894電子書籍操作ログを分析した．本研究では操作ログからページ毎に6種類の特徴量を計算し，分類モデルを作成した．最終的にそのモデルに対して10分割の交差検証によって921ページに関しての評価を行った．本論文では提案手法の詳細について述べ，評価結果を報告する．

Language：Japanese  

自学学習中における脳波・視線の同時計測・分析システムの開発

Language：English  

Combinatorial bandit prediction with relaxation-based approximation algorithm

Language：Others  

Learning theory and algorithms for shapelets and other local features

Language：English  

Time Series Classification Based on Random Shapelets

Language：Japanese  

Bandit Algorithm For k-Sets Based On Projection And Decomposition

Language：Japanese  

低コスト・省力化,軽労化技術等の開発―農家の作業技術の数値化及びデータマイニング手法の開発―第1章「農匠ナビ」全体システム設計・開発・評価 1「農匠ナビ」全体システム設計・実証および農作業連続計測・可視化・データマイニング基盤技術の研究開発

Language：English  

Collaborative ranking based on relative preference (情報論的学習理論と機械学習)

Language：English  

Online Density Estimation of Bradley-Terry Models (情報論的学習理論と機械学習)

Language：Japanese  

Language：Japanese  

メトリカルタスクシステム （Metrical Task System） 問題 （以下，MTS 問題） とは，逐次的な意思決定過程をモデル化したもので，ある固定された距離空間 (C; δ) を決定空間とするプロトコルとして，次のように記述される．各時刻 t=1,2,...,T において，プレイヤーは損失関数 lt:C→R+ を観測したあとある決定 ct∈C を選択し，損失 lt(ct)+δ(ct,ct-1) を被る．プレイヤーの目標は，累積損失に関する競合比を最小化することである．各時刻の計算時間が決定空間のサイズ n=|C| に比例するアルゴリズムがいくつか提案されている．しかし，ルーティングやランキングなど多くの問題は，決定空間が組み合わせ論的に定義された指数サイズの問題として定式化されるため，従来手法はそのままでは効率が悪い．例えばルーティング問題では，ある固定されたグラフの全域木の集合が決定空間になるが，そのサイズ n は一般にグラフのサイズに関して指数的である．本研究では，c≠c′ のとき δ(c,c′)=1 を満たす一様距離空間上の MTS 問題を，決定空間 C 上のサンプリングの問題に還元する手法を提案する．すなわち，効率の良いサンプリングアルゴリズムが存在する決定空間 C に対して，MTS 問題を効率よく解くことができる．実際，全域木の集合や s-t 道の集合など，いくつかの組み合わせ論的な決定空間は，効率の良いサンプリングアルゴリズムを持つことを示す．本手法の競合比の上界は 6e ln n で，従来手法の競合比 O(log n) と同じオーダーを達成している．

Language：Japanese  

メトリカルタスクシステム(Metrical Task System)問題(以下,MTS問題)とは,逐次的な意思決定過程をモデル化したもので,ある固定された距離空間(C,δ)を決定空間とするプロトコルとして,次のように記述される.各時刻t=1,2,...,Tにおいて,プレイヤーは損失関数l_t→R_+を観測したあとある決定c_t∈Cを選択し,損失l_t(c_t)+δ(C_t,C_<t-1>)を被る.プレイヤーの目標は,累積損失に関する競合比を最小化することである.各時刻の計算時間が決定空間のサイズn=|C|に比例するアルゴリズムがいくつか提案されている.しかし,ルーティングやランキングなど多くの問題は,決定空間が組み合わせ論的に定義された指数サイズの問題として定式化されるため,従来手法はそのままでは効率が悪い.例えばルーティング問題では,ある固定されたグラフの全域木の集合が決定空間になるが,そのサイズnは一般にグラフのサイズに関して指数的である.本研究では,c≠c&#039;のときδ(c,c&#039;)=1を満たす一様距離空間上のMTS問題を,決定空間C上のサンプリングの問題に還元する手法を提案する.すなわち,効率の良いサンプリングアルゴリズムが存在する決定空間0に対して,MTS問題を効率よく解くことができる.実際,全域木の集合やs-t道の集合など,いくつかの組み合わせ論的な決定空間は,効率の良いサンプリングアルゴリズムを持つことを示す.本手法の競合比の上界は6eln nで,従来手法の競合比O(log n)と同じオーダーを達成している.

Language：Japanese  

メトリカルタスクシステム(Metrical Task System)問題(以下,MTS問題)とは,逐次的な意思決定過程をモデル化したもので,ある固定された距離空間(C,δ)を決定空間とするプロトコルとして,次のように記述される.各時刻t=1,2,...,Tにおいて,プレイヤーは損失関数l_t→R_+を観測したあとある決定c_t∈Cを選択し,損失l_t(c_t)+δ(C_t,C_<t-1>)を被る.プレイヤーの目標は,累積損失に関する競合比を最小化することである.各時刻の計算時間が決定空間のサイズn=|C|に比例するアルゴリズムがいくつか提案されている.しかし,ルーティングやランキングなど多くの問題は,決定空間が組み合わせ論的に定義された指数サイズの問題として定式化されるため,従来手法はそのままでは効率が悪い.例えばルーティング問題では,ある固定されたグラフの全域木の集合が決定空間になるが,そのサイズnは一般にグラフのサイズに関して指数的である.本研究では,c≠c&#039;のときδ(c,c&#039;)=1を満たす一様距離空間上のMTS問題を,決定空間C上のサンプリングの問題に還元する手法を提案する.すなわち,効率の良いサンプリングアルゴリズムが存在する決定空間0に対して,MTS問題を効率よく解くことができる.実際,全域木の集合やs-t道の集合など,いくつかの組み合わせ論的な決定空間は,効率の良いサンプリングアルゴリズムを持つことを示す.本手法の競合比の上界は6eln nで,従来手法の競合比O(log n)と同じオーダーを達成している.

Language：Japanese  

Learning Evaluation Functions for Shogi Using SVM-Based Bipartite Ranking Learning
近年,将棋の評価関数の設計においては,機械学習を応用してパラメータの自動調整を行う手法が主流となっている.ただし,評価項目(特徴)は作成者の棋力,感覚に基づいて用意されることが多く,これまで,複数の駒同士の関係など,複雑な特徴が数多く考案されてきた.本研究では,明示的に用意する特徴としては局面を表す基本的で単純なもののみとし,多項式カーネルとサポートベクターマシン(SVM)を用いて評価関数の学習を行う手法を提案する.多項式カーネルを用いることにより,単項式で表現できる特徴間のn項関係を,全て高次の特徴として利用することができる.また,評価関数の学習問題を,合法手後の局面を順位づける2部ランキングの問題と捉え,SVMを用いて学習を行う手法(ランキングSVM法)を提案する.対局や棋譜との一致率を調べる実験結果,及び駒組みの観察等から,ランキングSVM法の有効性を示す.

Language：English  

Online Prediction with Bradley-Terry Models and Logistic Models
We consider an online density estimation problem under the Bradley-Terry model which determines the probability of the order between any pair in the set of n teams. An annoying issue is that the loss function is not convex. A standard solution to the avoid the non-convexity is to change variables so that the new loss function w.r.t. new variables is convex. But, then the radius of the new domain might be huge or unknown in general, for which standard algorithms such as OGD and ONS have suboptimal regret bounds. We propose two algorithms with regret O (lnT). Our first algorithm achieves the best regret so far and can be applied to the online logistic regression models as well. As a result, we solve the open problem posed by McMahan and Streeter. Our second algorithm has a weaker regret bound, but performs better in practice.

Language：English  

Online Matrix Prediction with Log-Determinant Regularizer
We consider an online symmetric positive semi-definite matrix prediction problem with convex loss function and Probenius norm of predictions are bounded. FTRL is famous method to deal with online prediction task, which makes prediction by minimizing cumulative loss function and regularizer function. There are three popular regularizer functions for matrices, Probenius norm, quantum relative entropy and log-determinant. The regret bound is already proven in Probenius norm and quantum relative entropy regularizer although in log-determinant regularizer is not proven. We propose a FTRL based algorithm with log-determinant as regularizer and show regret bound of algorithm. We also propose an application of online matrix prediction problem to online metric learning task.

Language：Japanese  

Passive-Aggressive Algorithm with Bias
We consider online binary classification problems by using linear classifiers. Among online learning algorithms for linear classifiers, Passive-Aggressive algorithm is very popular. In order to learn linear classifiers with bias (constant term), Passive-Aggressive algorithm, like many typical online learning algorithms, extends the instance space by adding an extra dimension corresponding to bias and its value is given as a parameter. But, in general, it is not trivial to optimize the extra parameter so as to minimize cumulative losses. In this paper, we propose a version of Passive-Aggressive algorithm which can deal with bias without the extra parameter to tune.

Language：English  

Efficient AUC Maximization by Approximate Reduction of Ranking SVMs

Language：English  

Efficient AUC Maximization by Approximate Reduction of Ranking SVMs
The formulation of Ranking SVMs is popular for maximizing AUC scores. More precisely, the formulation is given as a hard/soft margin optimization over pn pairs of p positive and n negative instances. Directly solving the problem is impractical since we have to deal with a sample of size pn, which is quadratically larger than the original sample size p+n. In this paper, we propose (approximate) reduction methods from the hard/soft margin optimization over pn pairs to variants of hard/soft margin optimization over p+n instances. The resulting classifiers of our methods are guaranteed to have a certain amount of margin over pn pairs.

Language：Japanese  

Polyphonic Music Classification Based on Similarity
In this paper we address the problem of classifying polyphonic music. Especially we use the classification approach based on dissimilarity [1]. We convert polyphonic music into vector sequence in order to apply the dissimilarity function used for string to music. When classified by changing vector sequence and dissimilarity function, classification accuracy was good at any case.

Language：Japanese  

Language：Japanese  

Learning Shogi Evaluation Functions using Kernel Methods
近年,コンピュータ将棋における評価関数は,機械学習を応用したパラメータの自動調整を行う手法が主流となっている.ただし,評価項目(特徴)は,作成者の考え,感覚に基づいて用意されることがほとんどである.本論文では,プロ棋士の棋譜を学習サンプルとして,カーネル法とサポートベクトルマシンを用いて学習を行う手法を提案する.カーネル法を用いることにより,作成者があらかじめ複雑な特徴を用意せずとも,局面を表現する単純な特徴のみから,特徴間のn項関係などのより高次な特徴のが暗に生成され,その特徴空間で学習が行われる.複数の駒の位置関係の考慮が不可欠である囲いの評価実験を行い,カーネル法が有用性を示す結果を得た.また,本手法により得られた評価関数は,定跡などの明示的な知識を導入することなしに得られたにもかかわらず,特に序盤において,人間らしい局面評価を行うことを示す.Recently, automatic optimization of parameters by applying machine learning methods has become a mainstream approach for developing good evaluation functions in shogi. However, the features used in the evaluation functions are prepared by the developer, depending heavily on his/her knowledge and intuition. In this paper, we propose a method for learning evaluation functions from game records of professional players, using kernel methods and Support Vector Machines (SVMs). By using kernels, higher dimensional features such as n-ary relations between simple features can be considered implicitly, and various complex features can be considered without preparation. We apply our method on castle positions, which require consideration of relative positions of pieces, and show that the evaluation functions learned using kernels give better results. We also show that even without knowledge of standard moves, we were able to obtain human-like evaluation functions, especially in the opening.

Language：Japanese  

Learning Evaluation Functions for Shogi Using SVM-based Bipartite Ranking Learning
Recently, automatic optimization of parameters by applying machine learning methods has become a mainstream approach for developing good evaluation functions in shogi. However, the features used in the evaluation functions are prepared by the developer, depending heavily on his/her knowledge and intuition. To date, many complex features, such as relationships between multiple pieces, have been designed. In this paper, we propose an approach using polynomial kernels and Support Vector Machines (SVM), where only very simple features will be prepared explicitly. Polynomial kernels allow us to consider high dimensional, n-ary relations of monomial features. We further regard the problem of evaluation function learning as a bipartite ranking problem of the positions after legal moves, and propose a method which uses SVMs (ranking SVM). We show the effectiveness of our algorithm through computational experiments.

Language：English  

F-037 Sparse Substring Pattern Set Discovery using Linear Programming Boosting
In this paper, we consider finding a small set of substring patterns which classifies the given documents well. We formulate the problem as 1 norm soft margin optimization problem where each dimension corresponds to a substring pattern. Then we solve this problem by using LPBoost and an optimal substring discovery algorithm. Since the problem is a linear program, the resulting solution is likely to be sparse, which is useful for feature selection. We evaluate the proposed method for real data such as movie reviews

Language：English  

F-036 Online Rank Aggregation
We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as the Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We propose algorithms for this problem and prove relative loss bounds with regret only depending on O(n^2). Further, we also prove a matching lower bound of the regret, which shows our algorithms are almost optimal.

Language：Japanese  

Musical data classification and similarity measures on strings

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

A Context Tree Weighting Algorithm with an Adaptive Window
The Context Tree Weighting Method (CTW) [1] is one of the most effective algorithm in the area of universal data compression. On the other hand, when we apply CTW to the non-stationary source, its compression performance descends due to the harmful effect of past data. The Finite Window Context Tree Weighting Method (FWCTW) [4] avoids this problem by introducing a finite window and discarding stale data. But FWCTW has a problem that we must decide the window size, which is difficult to determine appropriately in advance. In this paper, we propose a method detecting change of the source and adapting the window size automatically.

Language：Japanese  

A Context Tree Weighting Algorithm with an Adaptive Window

Language：English  

Online Learning of Approximate Maximum &#36;p&#36;-Norm Margin Classifiers with Bias (Foundations of Theoretical Computer Science : For New Computational View)

Language：Japanese  

Autonomous Learning of Ball Passing Skills Using Thinning-out

Language：Japanese  

Language：English  

An Efficient Smooth Boosting by Filtering(New Trends in Theory of Computation and Algorithm)

Language：English  

Smooth Boosting with An Information-theoretic Criterion (テーマ:特集「シンボルグラウンディング問題」および一般)

Language：English  

Practical Algorithms for Pattern Based Linear Regression (テーマ:特集「シンボルグラウンディング問題」および一般)

Language：English  

Learning r-of-k Functions by Boosting
We investigate further improvement of boosting in the case that the target concept belongs to the class of r-of-k threshold Boolean functions, which answers "+1" if at least r of k relevant variables are positive, and answers "-1" otherwise. Given m examples of a r-of-k function and literals as base hypotheses, popular boosting algorithms (e.g., AdaBoost) construct a consistent final hypothesis in O(K^2logm) iterations. While this convergence speed is tight in general, we show that a modification of AdaBoost (confidence-rated AdaBoost [11] or InfoBoost [1]) can find a consistent final hypothesis in O(krlogm) iterations.

Language：Japanese  

Simplified analysis of a decision tree boosting algorithm with multi - way branching
We show an simpler analysis of a decision tree learning algorithm proposed by Mansour and McAlleter. They extend a binary decision tree learning algorithm to a multi-way branching one and showed that the error of the multi-way branching tree produced by the extended algorithm is bounded with an upperbound of the error of the binary tree of the same size produced by non-extended one. We show that their result holds under a simpler and weaker condition.

Language：Japanese  

Analysis of a decision tree boosting algorithm
We analyze a boosting algorithm for multi-class functions. Boosting is a technique of finding a hypothesis with high accuracy by combining many weak hypotheses, that is only moderately accurate. We focus on an algorithm, TOPDOWN proposed by Takimoto and Maruoka. TOPDOWN constructs a K-branching decision tree in which inner nodes are labeled by weak hypothesis h:X→{1, …, K}for an unknown target function f:X→{1, …, N}(N&amp;ge;2). Takimoto and Maruoka showed that if the number of inner nodes of the output decision tree is larger than(1/ε)^<K/γ>the training error of the tree is less than ε, where γ is the advantage lowerbound of weak hypotheses. We show that this sufficient number of inner nodes is indeed 2(1/ε)^<1nK/γ>.

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：5

Number of peer-reviewed articles in Japanese journals：0

Proceedings of International Conference Number of peer-reviewed papers：48

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：8

Number of peer-reviewed articles in Japanese journals：1

Proceedings of International Conference Number of peer-reviewed papers：59

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：1

Number of peer-reviewed articles in Japanese journals：1

Proceedings of International Conference Number of peer-reviewed papers：61

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：6

Proceedings of International Conference Number of peer-reviewed papers：70

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：8

Number of peer-reviewed articles in Japanese journals：0

Proceedings of International Conference Number of peer-reviewed papers：39

Proceedings of domestic conference Number of peer-reviewed papers：0

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：7

Number of peer-reviewed articles in Japanese journals：1

Proceedings of International Conference Number of peer-reviewed papers：48

Proceedings of domestic conference Number of peer-reviewed papers：0

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Academic society, research group, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Peer review 

Number of peer-reviewed articles in foreign language journals：13

Number of peer-reviewed articles in Japanese journals：0

Proceedings of International Conference Number of peer-reviewed papers：33

Proceedings of domestic conference Number of peer-reviewed papers：0

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc. 

Type：Competition, symposium, etc.