Nakamura Atsuyoshi

Faculty of Information Science and Technology　Computer Science and Information Technology　Knowledge Software ScienceProfessor
Research Institute for Electronic Science　Research Center of Mathematics for Social CreativityProfessor
Last Updated :2025/12/04

■Researcher basic information

Researchmap personal page

Home Page URL

Researcher number

  • 50344487

J-Global ID

Research Keyword

  • アルゴリズム
  • 汎化性能
  • Online Leaning
  • Active Learning
  • Computational Learning Theory
  • 機械学習
  • データマイニング

Research Field

  • Informatics, Intelligent informatics
  • Informatics, Intelligent robotics
  • Informatics, Perceptual information processing

Educational Organization

■Career

Career

  • Apr. 2021 - Present
    Hokkaido University, Graduate School of Information Science and Technology, Professor
  • Jul. 2002 - Mar. 2021
    Hokkaido University, Graduate School of Information Science and Technology, Associate Professor
  • Apr. 1988 - Jun. 2002
    NEC Corporation

Educational Background

  • Feb. 2000, Tokyo Institute of Technology, Graduate School of Science and Engineering, 博士（理学）
  • Apr. 1986 - Mar. 1988, Tokyo Institute of Technology, 大学院理工学研究科, 情報科学専攻
  • Apr. 1982 - Mar. 1986, Tokyo Institute of Technology, School of Science, Department of Information Science

■Research activity information

Awards

  • 2013, 電子情報通信学会, 情報・システムソサイエティ査読功労賞　　　　　　　　　　　　　　　
    中村篤祥
  • 2013, 電子情報通信学会, 情報・システムソサイエティ活動功労賞　　　　　　　　　　　　　　　
    中村篤祥

Papers

Other Activities and Achievements

  • 単調増加制約のあるレベルセット推定
    田畑 公次, 中村 篤祥, 高見 亮佑, Joshua Arenson, 和田 弥生, Walker Peterson, 合田 圭介, 園下 将大, 小松崎 民樹, 人工知能学会研究会資料 人工知能基本問題研究会, 124, 25, 30, 06 Mar. 2023
    一般社団法人 人工知能学会, Japanese
  • 与えられたデータに無矛盾なコンパクトな多出力二分決定グラフの質問学習
    中村 篤祥, 人工知能学会研究会資料 人工知能基本問題研究会, 123, 31, 36, 05 Jan. 2023
    一般社団法人 人工知能学会, Japanese
  • Estimation of Propagation Graph by Pairwise Alignment of Time Series Data
    林 達也, 中村 篤祥, 人工知能基本問題研究会, 114, 1, 6, 20 Nov. 2020
    人工知能学会, Japanese
  • Effect and Application of Branching Condition Sharing of Decision Forests
    NAKAMURA Atsuyoshi, SAKURADA Kento, Proceedings of the Annual Conference of JSAI, 2020, 2I1GS201, 2I1GS201, 2020

    Min_DBN is an algorithm that minimizes the number of distinct branching conditions in a decision forest by sharing variable's thresholds assigned to different branching nodes under the condition that decision paths of given feature vectors must not be changed more than a specified percentage at each branching node. This simplification is effective for compact hardware implimentation of a decision forest with comparator sharing. In this paper, we experimentally investigate how effective the algorithm is for decision forests constructed by various ensemble learning methods (random forest, extremly random trees, AdaBoost, gradient boosting) in classification and regression. Futhermore, we improve the algorithm by using the feature vectors only used in a bagging-based learning for applying its path condition to each component tree of the ensumbles, and check its effectiveness experimentally.

    , The Japanese Society for Artificial Intelligence, Japanese
  • A Fast Approximate Algorithm for k-Median Problem on a Graph　　　　　　　　　　　　　　　
    Keisuke Todo, Atsuyoshi Nakamura and Mineichi Kudo, Proceedings of the 15th International Workshop on Mining and Learning with Graphs (MLG), Aug. 2019, [Peer-reviewed]
    Summary international conference
  • Reduction on the Number of Distinct Branch Nodes of a Random Forest Classifier
    櫻田 健斗, 中村 篤祥, 人工知能基本問題研究会, 109, 62, 67, 13 Mar. 2019
    人工知能学会, Japanese
  • バンディット問題の方策を用いたモンテカルロ木探索による最適属性集合探索
    中村篤祥, ペリシエ オレリアン, 田畑公次, 小松崎民樹, 日本細胞生物学会大会(Web), 71st, ROMBUNNO.1SEp‐07 (WEB ONLY), 2019
    Japanese
  • Algorithms for Checking Existence of a Bad Arm Utilizing Asymmetry
    田畑公次, 中村篤祥, 小松崎民樹, 電子情報通信学会技術研究報告, 118, 284(IBISML2018 44-104)(Web), 353‐360 (WEB ONLY), 29 Oct. 2018
    Japanese
  • Bad Arm Existence Checking Algorithms with Small Sample Complexity
    田畑 公次, 中村 篤祥, 本多 淳也, 小松崎 民樹, 人工知能基本問題研究会, 106, 94, 99, 16 Mar. 2018
    人工知能学会, Japanese
  • Feature selection as Monte-Carlo Search in Growing Single Rooted Directed Acyclic Graph by Best Leaf Identification.
    Aurelien Pelissier, Atsuyoshi Nakamura, Koji Tabata, CoRR, abs/1811.07531, 2018
  • 音響的に自然なつなぎ目の発見による楽曲ループ検出
    安井拓未, 中村篤祥, 中村篤祥, 田中章, 田中章, 工藤峰一, 工藤峰一, 情報処理学会研究報告(Web), 2017, MUS-116, Vol.2017‐MUS‐116,No.15,1‐4 (WEB ONLY), 17 Aug. 2017
    Japanese
  • Algorithms for Bad Arm Existence Checking Problem
    中村 篤祥, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 117, 110, 49, 54, 23 Jun. 2017
    電子情報通信学会, Japanese
  • Enumeration of Interspersed Repeats from the Human Genome
    中村 篤祥, 人工知能基本問題研究会, 103, 45, 50, 13 Mar. 2017
    人工知能学会, Japanese
  • Extended KL-UCB Policy for the Budgeted Multi-Armed Bandits
    渡辺 僚, 中村 篤祥, 工藤 峰一, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115, 323, 167, 174, 26 Nov. 2015
    電子情報通信学会, Japanese
  • Noise Free Multi-Armed Bandit Game (特集 「人工知能・機械学習」および一般)
    Helmbold David P, Nakamura Atsuyoshi, Warmuth Manfred K, 人工知能基本問題研究会, 98, 16, 21, 07 Aug. 2015
    人工知能学会, English
  • A Bridge between Hedge and Exp3 Algorithms
    中村 篤祥, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115, 112, 81, 86, 23 Jun. 2015
    電子情報通信学会, Japanese
  • An Extension of UCB to the Stochastic Multi-armed Bandits with Action-dependent Processing Time
    渡辺 僚, 中村 篤祥, 工藤 峰一, 人工知能基本問題研究会, 96, 29, 34, 13 Jan. 2015
    人工知能学会, Japanese
  • A Study on UCB-type Collaborative Filtering
    中村 篤祥, 人工知能基本問題研究会, 93, 45, 48, 07 Mar. 2014
    人工知能学会, Japanese
  • An Algorithm for Influence Maximization Problem on a Two-Terminal Series Pararell Graph
    田畑 公次, 中村 篤祥, 工藤 峰一, 人工知能基本問題研究会, 92, 35, 40, 30 Jan. 2014
    人工知能学会, Japanese
  • A New UCB-based Algorithm for the Matching-Selection Multi-armed Bandit Problem
    渡辺 僚, 中村 篤祥, 工藤 峰一, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113, 198, 9, 16, 03 Sep. 2013
    電子情報通信学会, Japanese
  • Balanced Binary Search Tree with Constant-Time Insertions at the End
    花田 博幸, 中村 篤祥, 工藤 峰一, 人工知能基本問題研究会, 89, 25, 30, 28 Feb. 2013
    人工知能学会, Japanese
  • An Efficient Algorithm for Multi-Armed Bandit Problems with Matching Selection
    渡邊 僚, 中村 篤祥, 工藤 峰一, 人工知能基本問題研究会, 86, 0, 29, 34, 09 Aug. 2012
    人工知能学会, Japanese
  • Fast Approximation Algorithm for the 1-Median Problem
    田畑 公次, 中村 篤祥, 工藤 峰一, 人工知能基本問題研究会, 86, 0, 77, 82, 09 Aug. 2012
    人工知能学会, Japanese
  • Finding Approximate Frequent Patterns from DNA Sequences
    中村 篤祥, 瀧川 一学, 戸坂 央, 人工知能基本問題研究会, 85, 23, 28, 02 Feb. 2012
    人工知能学会, English
  • Fast Algorithm for Finding a Graph Node with High Closeness Centrality
    TABATA Koji, NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Theoretical foundations of Computing, 111, 256, 7, 14, 14 Oct. 2011
    The Closeness Centrality is one of centrality measures of a node in a graph. It is calculated as the reciprocal of the sum of distances to all other nodes. In this paper, we propose a fast approximate algorithm that finds the node to maximize its closeness centrality in an undirected graph. Given a node v, the algorithm repeatedly find a node with higher closeness centrality by making use of a shortest path tree of the previous node. According to out experiment, our algorithm can find a node with almost maximum closeness centrality with high probability., The Institute of Electronics, Information and Communication Engineers, Japanese
  • A note on Capped Hedge algorithm
    中村 篤祥, 人工知能基本問題研究会, 82, 1, 6, 04 Aug. 2011
    人工知能学会, Japanese
  • Efficient Implementation of Greedy Cover Learning by Hyper-Rectangles and Its Classification Performance Evaluation Using Real Data
    OUCHI Koji, NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report, 110, 265, 99, 104, 28 Oct. 2010
    Blumer et al. showed that the class of concepts represented by finite unions of hyper-rectangles in d-dimensional Euclidean space is polynomial-time PAC learnable for a fixed natural number d. In their proof, they constructed an algorithm which conducts a greedy covering of a given positive instances by hyper-rectangles that never cover any one of given negative instances. In this paper, we discuss the efficient implementation of their algorithm. According to our experimental results on n-class classification problems using UCI datasets, Blumer's covering algorithm, in most cases, outputs a..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Adversarial Bandit Problems with Multiple Plays
    UCHIYA Taishi, NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Theoretical foundations of Computing, 109, 195, 13, 20, 07 Sep. 2009
    Adversarial bandit problems studied by Auer et al. are the multi-armed bandit problems in which no stochastic assumption is made on the nature of the process generating the rewards for actions. In this paper, we extend their theories to those in the case when k(≧1) actions are selected at each time step. We analyze the problems in two settings of multiple plays, that is, in the settings of selections with and without repetition. In the both settings, we generalize the Exp3 family algorithms developed by them and give the generalized upper bounds on the regrets for the best fixed set of acti..., The Institute of Electronics, Information and Communication Engineers, English
  • On effect of balancing investment in nonstochastic multi-armed bandit problems
    UCHIYA Taishi, NAKAMURA Atsuyoshi, KUDO Mineichi, Technical report of IEICE. PRMU, 108, 363, 213, 218, 11 Dec. 2008
    The multiarmed bandit problem is a problem in which a gambler chooses one arm of K nonidentical slot machines to play in a sequence of trials so as to maximize his reward. Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. On the other hand, Auer et al. made no statistical assumption whatsoever about the nature of the process generating the payoffs of the slot machine. They gave solutions to the bandit ploblem in which an adversary has complate control over the payoffs. In this paper, we extend this problem to the proble..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Classifier selection in a family of polyhedron classifiers
    TAKAHASHI Tetsuji, KUDO Mineichi, NAKAMURA Atsuyoshi, Technical report of IEICE. PRMU, 108, 363, 37, 41, 11 Dec. 2008
    It is an efficient way to approximate a class region by convex hulls of samples. However, the convex hull is computationally hard to be constructed in high dimensions. In this paper, we propose a way to construct an approximate convex hull in a linear time of dimension. In addition, we discuss on selecting an optimal classifier from a family of polyhedron classifiers derived from approximate convex hulls., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Packing Alignment and Its Application to Music Mining
    NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Theoretical foundations of Computing, 108, 237, 9, 16, 03 Oct. 2008
    We propose packing alignment as an alignment for sequences of lengthened symbols like musical notes. Furthermore, we consider sequences of symbols with length and end position as a model of a general musical piece in which notes can overlap, and we extend our packing alignment to that for such sequences. Using packing alignment, it might be possible that parts that you feel similar somehow are extracted automatically. According to our experiment using MIDI files of Bach's popular musical pieces, actually, parts that are non-trivially similar but are felt similar somehow were extracted., The Institute of Electronics, Information and Communication Engineers, English
  • Notes on Enumeration of Concepts in a Sperner Family Concept Class Using Subconcept Queries (Foundations of Theoretical Computer Science : For New Computational View)
    Nakamura Atsuyoshi, Kudo Mineichi, RIMS Kokyuroku, 1599, 0, 162, 169, May 2008
    Kyoto University, English
  • Finding Subforest Patterns with Frequent Occurrence of Similar Subforests
    戸坂 央, 中村 篤祥, 工藤 峰一, 人工知能学会全国大会論文集, 22, 1, 4, 2008
    人工知能学会, Japanese
  • Complexity and Enumeration of Subclasses
    NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Theoretical foundations of Computing, 107, 219, 35, 42, 13 Sep. 2007
    Representing a complicated region by union of simple regions is often preferred in various study areas because each component simple region is easy to understand and easy to deal with. Kudo et al. [2], [4] considered the following problem called subclass problem: given positive and negative examples in multidimensional real space, enumerate all maximal sets of positive examples for which there exists a hyper-rectangle that contains the set and does not contain any negative example. However, a randomized method that can find as many important subclasses as possible has been used so far becau..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Finding of Frequent Similar Subtrees in Tree-Structured Data
    TOSAKA Hisashi, NAKAMURA Atsuyoshi, KUDO Mineichi, Technical report of IEICE. PRMU, 107, 115, 7, 12, 21 Jun. 2007
    We study a novel problem of mining subtrees with frequent occurrence of similar subtrees, and propose an efficient algorithm for this problem. According to our problem setting, frequency of a subtree is counted not only for equivalent subtrees but also for similar subtrees. Our experiment showed that our algorithm is enough fast for practical use. Preliminary experiment for data record extraction using our mining method also showed encouraging result., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Finding of Frequent Similar Subtrees in Tree-Structured Data
    TOSAKA Hisashi, NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Data engineering, 107, 114, 7, 12, 21 Jun. 2007
    We study a novel problem of mining subtrees with frequent occurrence of similar subtrees, and propose an efficient algorithm for this problem. According to our problem setting, frequency of a subtree is counted not only for equivalent subtrees but also for similar subtrees. Our experiment showed that our algorithm is enough fast for practical use. Preliminary experiment for data record extraction using our mining method also showed encouraging result., The Institute of Electronics, Information and Communication Engineers, Japanese
  • 不特定サイトからのキーワード関連情報の抽出 (テーマ:特集「ウェブデータの知的処理」および一般)
    中村 篤祥, 人工知能基本問題研究会, 63, 0, 33, 38, 08 Sep. 2006
    人工知能学会, Japanese
  • LA_001 Algorithm for Minimizing Repetition Representation Trees
    Saito Tomoya, Nakamura Atsuyoshi, Kudo Mineichi, 情報科学技術レターズ, 5, 0, 1, 4, 21 Aug. 2006
    Forum on Information Technology, Japanese
  • 繰返し構造をもつラベル付順序木の簡潔な表現法(計算理論とアルゴリズムの新展開)
    斉藤 智哉, 中村 篤祥, 工藤 峰一, 数理解析研究所講究録, 1489, 0, 216, 222, May 2006
    京都大学, Japanese
  • How Easy to Learn Linear Ranking Functions
    NAKAMURA Atsuyoshi, IEICE technical report. Theoretical foundations of Computing, 105, 273, 49, 53, 08 Sep. 2005
    In this paper, we study how easy to learn the class of linear ranking functions from n-dimensional Euclidean space to {1, 2, …, k}. We show its graph dimension, which is considered to indicate how easy to learn, is Θ(n+k). This graph dimension is significantly smaller than the graph dimension Θ(nk) of the class of k-valued decision-list functions naturally defined using k - 1 linear discrimination functions., The Institute of Electronics, Information and Communication Engineers, English
  • ランキング関数のオンライン学習について (計算機科学基礎理論とその応用)
    中村 篤祥, 数理解析研究所講究録, 1426, 0, 51, 56, Apr. 2005
    京都大学, Japanese
  • On NK-Community Problem (Theoretical Computer Science and its Applications)
    Nakamura Atsuyoshi, Shigezumi Takeya, Yamamoto Masaki, RIMS Kokyuroku, 1426, 0, 71, 77, Apr. 2005
    Kyoto University, English
  • Detection of Wrong Characters by Probability Transitional Patterns of Two-Directional N-gram Probabilities
    KAWATA Takehiro, KUDO Mineichi, TOYAMA Jun, NAKAMURA Atsuyoshi, The transactions of the Institute of Electronics, Information and Communication Engineers. D-II, 88, 3, 629, 635, 01 Mar. 2005
    OCRなどを通して得られる日本語文の認識結果において, N-gram確率を利用した高速な誤認識文字検出法を提案する.日本語のように単語が分かち書きされず大規模な語彙を対象とした場合, 誤り個所の指摘に文字N-gramは有効な方法である.本論文ではまず, 通常のN-gram確率の拡張として両方向N-gram確率を提案し, その有効性を情報量の点から考察する.次に, 両方向N-gram確率と文脈確率を用いて1文字の誤字を検出する方法を提案する.シミュレーション実験では, 適合率80%において従来法よりも10%以上高い約75%の再現率を達成できた.また, 誤り範囲の指摘という点では, 適合率80%で再現率90%が達成された., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Mining Frequent Trees with Node-Inclusion Constraints
    NAKAMURA Atsuyoshi, KUDO Mineichi, IPSJ SIG Notes, 2004, 101, 67, 74, 14 Oct. 2004
    In this paper, we propose an efficient algorithm enumerating all frequent subtrees containing all special nodes that are guaranteed to be included in all trees belonging to a given data. Our algorithm is a modification of TreeMiner algorithm [9] so as to efficiently generate only candidate subtrees satisfying our constraints. We also propose a space saving method for a set of trees with a lot of nodes having the same label. We report mining results obtained by applying our algorithm to the problem of finding frequent structures containing the name and reputation of given restaurants in Web ..., Information Processing Society of Japan (IPSJ), English
  • Mining Frequent Trees with Node-Inclusion Constraints
    NAKAMURA Atsuyoshi, KUDO Mineichi, IEICE technical report. Theoretical foundations of Computing, 104, 339, 7, 14, 08 Oct. 2004
    In this paper, we propose an efficient algorithm enumerating all frequent subtrees containing all special nodes that are guaranteed to be included in all trees belonging to a given data. Our algorithm is a modification of TreeMiner algorithm [9] so as to efficiently generate only candidate subtrees satisfying our constraints. We also propose a space saving method for a set of trees with a lot of nodes having the same label. We report mining results obtained by applying our algorithm to the problem of finding frequent structures containing the name and reputation of given restaurants in Web ..., The Institute of Electronics, Information and Communication Engineers, English
  • Detection of Wrong Character Using Probability Transitional Patterns of Both-Direction N-gram Probabilities
    KAWATA Takehiro, NAKAMURA Atsuyoshi, TOYAMA Jun, KUDO Mineichi, Technical report of IEICE. PRMU, 103, 295, 1, 5, 01 Sep. 2003
    The method of detecting the wrong characters and correction is proposed to improve recognition precision in character recognition. We pay attention to a technique in which N-gram probabilities are used, and propose a method which detects misspelled characters by both direction N-gram probabilities. Context probability is also introduced to be incorporated with estimated probabilities transitional patterns in both direction N-gram probabilities and context probabilities at the misspelling point. Moreover, we discuss the causes why some misspelled characters are not detected in this method. I..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Relationship between Rule Accuracy and a Degree of Interest
    SHIDARA Yohji, NAKAMURA Atsuyoshi, KUDO Mineichi, Technical report of IEICE. PRMU, 103, 295, 7, 11, 01 Sep. 2003
    The methods which extract rules from database are useful for mining because of their human-readable output. Various methods have been proposed which construct some accurate classifiers and extract the rules from these classifiers. However, these accurate classifiers do not always provide the interesting rules. We propose the rule-mining method based on abstraction of attribute values and screening technique to extract rules with high readability. We also discuss the relationship between the discrimination accuracy and the degree of interest of the rules, The Institute of Electronics, Information and Communication Engineers, Japanese
  • Automatic Recommendation(Data/Text Mining)
    Nakamura Atsuyoshi, 応用数理, 12, 4, 401, 410, 25 Dec. 2002
    We explain automatic recommendation techniques by which computer systems can automatically select goods or documents preferred by each user based on his/her buying or accessing history. Especially, we focus on the collaborative filtering method using weighted majority prediction algorithm developed by the authors. From both theoretical and experimental points of view, we explain how excellent the method is compared to the method using correlation coefficient, which is the most popular collaborative filtering method. We also address issues that we should consider in order to make our method ..., The Japan Society for Industrial and Applied Mathematics, Japanese
  • 自動リコメンデーション
    中村 篤祥, 応用数理, 12, 4, 401, 410, 25 Dec. 2002
    日本応用数理学会, Japanese
  • Targeting Techniques for Web Advertising
    LANGHEINRICH Marc, KAMBA Tomonari, NAKAMURA Atsuyoshi, IPSJ Magazine, 40, 8, 807, 812, 15 Aug. 1999
    Information Processing Society of Japan (IPSJ), Japanese
  • 0.特集「能動学習」の編集にあたって (<特集>能動学習)
    中村 篤祥, 情報処理, 38, 7, 557, 588, 15 Jul. 1997
    一般社団法人情報処理学会, Japanese
  • Introduction to Active Learning
    ABE Naoki, NAKAMURA Atsuyoshi, IPSJ Magazine, 38, 7, 558, 561, 15 Jul. 1997
    Information Processing Society of Japan (IPSJ), Japanese
  • Research on Active Learning in Computational Learning Theory
    ABE Naoki, NAKAMURA Atsuyoshi, IPSJ Magazine, 38, 7, 575, 582, 15 Jul. 1997
    Information Processing Society of Japan (IPSJ), Japanese
  • Learning personal preference functions using boolean-variable real-valued multivariate polynomials
    Nakamura Atsuyoshi, Mamitsuka Hiroshi, Toba Hiroyasu, Abe Naoki, 全国大会講演論文集, 第52回平成8年前期, 1, 55, 56, 06 Mar. 1996
    ニュース記事などに対する個人の嗜好を、記事中の出現単語から予測する方法において、各単語にlつのブール変数を割り当て、その実数係数多項式で嗜好関数を表現する方法を提案し、その係数の学習アルゴリズムについて考察及び実験を行う。特に、計算論的学習理論において盛んに研究されているオンライン学習における重みの逐次更新法を、実数係数の学習に適用する。具体的には、Kivinen & Warmuthが提案・解析した加法的更新法GDと乗法的更新法EG^±に加え、新しく「誤差比例修正法」と呼ぶ重み更新アルゴリズムを提案し、その乗法的更新法であるDPMUについて、ある被験者の実データを用いて実験的に予測性能を評価・比較する。実験結果によればDPMUは、既存の方式と同等以上の予測性能を有する。, Information Processing Society of Japan (IPSJ), Japanese
  • On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms
    Naoki Abe, Hang Li, Atsuyoshi Nakamura, Proc. of The 12th Int. Conf. on Machine Learning, 1995, 24 Jul. 1995
    We consider the problem of learning a certain type of lexical semantic

    knowledge that can be expressed as a binary relation between words, such as the

    so-called sub-categorization of verbs (a verb-noun relation) and the compound

    noun phrase relation (a noun-noun relation). Specifically, we view this problem

    as an on-line learning problem in the sense of Littlestone's learning model in

    which the learner's goal is to minimize the total number of prediction

    mistakes. In the computational learning theory literature, Goldman, Rivest and

    Schapire and subsequently Goldman and Warmuth have consider..., Technical report
  • Learning d-nary Relations
    Nakamura Atsuyoshi, IEICE technical report. Theoretical foundations of Computing, 94, 181, 93, 102, 25 Jul. 1994
    We study the learning problem in which the learner predicts the value of each entry of d-dimensional{0,1}-valued matrix one by one. According to the agent who selects the next prediction entry,we consider this problem in two different models,self-directed and adversary-directed.In self-directed model,in which the learner selects entries,we show an efficient algorithm which makes at most Π^d_j=1>k_j+Σ^d_j=1>(n_j-k_j)log k_j mistakes when the target m atrix has n_j elements for its j-th direction and those elements are classified into at most k_j types by the values of matrix entries.In adver..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • PAC learning of planar rectangles of arbitrary orientaion
    Nakamura Atsuyoshi, IEICE technical report. Theoretical foundations of Computing, 93, 249, 53, 58, 24 Sep. 1993
    We investigate PAC learnability of planar rectangles of arbitrary orientation.We show an algorithm which outputs a hypothesis rectangle consistent with given m examples in time Ο(ml ogm).Since the class of planar rectangles of arbitrary oprientation has finite VC dimension,by the famous theorem of Blumer et al.,this algorithm is a distribution-free PAC learning algorithm whose sample complexity is Ο(1, εlog1/(εδ))for the ac curacy parameter ε and the confidence parameter δ.We also show th at the algorithm which outputs the minimum area rectangle containing all positive examples,which is kno..., The Institute of Electronics, Information and Communication Engineers, Japanese
  • Learning Multidimensional Euclidean Resions Representable by DNF.
    Nakamura Atsuyoshi, 全国大会講演論文集, 第46回平成5年前期, 3, 35, 36, 01 Mar. 1993
    n次元実数領域[0,1)^n上の部分領域を、[0,1)^n上の一様分布に従って得られる点及びその点が部分領域の内外どちらかという情報から部分領域を学習する問題を扱う。但し、部分領域は次の条件を満たすものに制限する。([0,1)^n上の点を(x_1,x_2,・・・,x_n)とする。)1)原子論理式が(x_i&isins;R)という形のDNF(積和標準形)の論理式で表現される。2)Rは区間[0,1)を高々k(固定)個の領域に分割するような領域∪^l_<i=1>[a_i,b_i)とする。3)各x_iは論理式の中で高々1度しか現れない。[2]では、分布を一様分布に固定したPAC(Probably Approximately Correct)学習モデルにおいてμDNF(各変数が高々1度しか現れないDNF)プール式で表現されるプール関数が学習可能であることが示されている。本稿は上記2)の制約の下で彼らの結果の定義域を{0,1}^nから[0,1}^nに拡張したものである。, Information Processing Society of Japan (IPSJ), Japanese

Books and other publications

Courses

  • 計算基礎特論　　　　　　　　　　　　　　　
    大学院情報科学研究科コンピュータサイエンス専攻
  • 統計学　　　　　　　　　　　　　　　
    全学教育
  • 情報理論　　　　　　　　　　　　　　　
    情報エレクトロニクス学科
  • アルゴリズムとデータ構造　　　　　　　　　　　　　　　
    情報エレクトロニクス学科コンピュータサイエンスコース

Affiliated academic society

  • THE JAPANESE SOCIETY FOR ARTIFICIAL INTELLIGENCE　　　　　　　　　　　　　　　
  • THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS　　　　　　　　　　　　　　　
  • INFORMATION PROCESSING SOCIETY OF JAPAN　　　　　　　　　　　　　　　

Research Themes

  • 漸近的最適かつ実用的な純粋探索バンディット方策の開発
    科学研究費助成事業
    01 Apr. 2024 - 31 Mar. 2029
    中村 篤祥, 田畑 公次, 畑埜 晃平, 寺本 央
    日本学術振興会, 基盤研究(A), 北海道大学, 24H00685
  • Online Desision Making Methods for Various Problems and Criteria
    Grants-in-Aid for Scientific Research
    01 Apr. 2022 - 31 Mar. 2026
    畑埜 晃平, Hashima Sherief, 瀧本 英二, 中村 篤祥
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyushu University, 23K24905
  • MARE: Recognition and Discovery Techniques for Giving Awarenesss
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2019 - 31 Mar. 2024
    工藤 峰一, 今井 英幸, 中村 篤祥
    今期は、不頻出事象の予測を抽象化したロングテール問題について基礎的検討を重ねた。ロングテールの特徴づけとして、極度にインバランス（サンプル数がクラスによって大きく異なる）であること、マルチラベル分類が多いこと、から、マルチラベル分類とインバランス問題の解決に注力した。さらに、実世界の不頻出事象に関連して、希少疾患予測の検討および独居老人の異変行動シミュレーションを行った。詳細を以下に示す。


    ・インバランスが顕著なマルチクラス問題を扱うため、2種類のクラス決定木（葉が一つクラスである決定木）を検討した。クラス集合対としてバランスをとるよう木を構成することでサンプル数の少ないクラスの検出精度を高めることに成功した。さらに、サンプルの少ないクラスが「次元の呪い」を受けやすいことを考慮して、特徴選択を少なくするようにクラス決定木を構成することで少数クラスのみならず全体の性能を向上させられることを示した。解釈可能性も大きく改善した。
    ・希少疾患の診断において、１）医者の”希少疾患見過ごし”を防ぐために可視化手法を利用することを提案した、さらに、２）特徴選択により希少疾患の診断精度を向上させられることを確認した。
    ・不頻出事象の予測に関して、極値論とサポートベクターマシンを利用した未知クラスの発見手法を提案し、これまでの手法よりよい性能を達成した。
    ・独居老人の異変検知手法を開発する前段階として、異変を含む仮想住人の行動シミュレータを開発した。高齢者を実際のスマートホームに住まわせ、転倒などの異変が起きるのを待つわけにはいかないため、シミュレータは必須である。また、長期間に渡るセンサデータの採取や多様な生活行動を扱う上でも有効である。残念ながらこれまでの方式で複数の異変を適切に扱えるものがなかったため、確率モデルを利用したシミュレータを新たに開発した。
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 19H04128
  • バンディット問題の方策の実用化のための理論の深化
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2019 - 31 Mar. 2023
    中村 篤祥, 田畑 公次, 工藤 峰一
    昨年度から始めた分類バンディット問題のアルゴリズムの開発において、k-腕設定のトンプ ソンサンプリングをベースとしたアルゴリズム、および実験的な性能評価を国際学会のワークショップで発表した。更に指定した信頼度で正しく判定するためのサンプル数の理論的評価を始めた。連続腕設定に拡張した問題においては、ガウス過程を事前分布とする方式において、全腕の正負(報酬の期待値が閾値以上か未満か）を答える既存法より少ないサンプル数の上界が得られるアルゴリズムを開発した。また、正腕の割合の推定値から分類結果を予測し、その予測が正しい場合に分類の精度が上がる方の腕を引く方式を考案し、有効性を実験により確かめた。ラマン分光による細胞診断の実データにも適用し、グリット分割によるk腕設定のトンプソンサンプリングより、ガウス過程を仮定した連続腕設定の提案方式の方が少ないサンプル数（計測数）で正しく判定できることを確認した。
    小ノイズ敵対的バンディットの研究においては、以前の成果である「ノイズフリーバンディット 問題」を小さなノイズを許す問題に拡張し、それに有効なアルゴリズムを開発することを目指している。ノイズフ リー条件(1回も誤らない腕が存在するという条件)を「誤る回数が高々k回の腕が存在する」という条件に緩めた問題定式化で研究を進めている。昨年度に引き続き、その問題設定 の下、腕の数が3本以上でk>2の条件でも動作するもっと一般的なアルゴリズムの開発を進めた。
    精度効率保証大規模探索の研究においては、昨年度に引き続き属性選択アルゴリズム[Aurelien, Nakamura, Tabata 2019]のアルゴリズムの探索木の拡張法の検討を行った。
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 19H04161
  • Development of Data-driven Mathematical Analysis for Single Cells and Singularity Cells
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    29 Jun. 2018 - 31 Mar. 2023
    小松崎 民樹, 中村 篤祥, 小野 峻佑
    ある細胞と別の細胞の主従関係を推定する場合，それら2つの細胞の軌跡データなどを用いて評価されているが，2つの細胞の振る舞いを決める因子が，その2つの細胞以外にも，第3の細胞が介在する状況なども考えられる。主従関係や因果関係における“原因”と“結果”を解析するためには，単純な対の組み合わせで表現できない多体の相互作用から成り立っている。そのため，多体のあいだの因果関係を推定することは要素間の組み合わせの数が膨大になる。2対の軌跡データを変数とする移動エントロピーを細分化した新しい相乗情報量に着眼し，改良Vicsekモデルに基づいてこの問題を考察し、移動エントロピーに含まれる相乗情報量の振る舞いを解析することで，要素間の多体の相互作用が推定できることを見いだした（Sci Adv 2022）。
    昨年度開発した、細胞毎の発火状態時系列からの伝搬時差推定をギャップを挿入する文字列のアライメントで行い伝搬グラフを構築する手法を発展させ、DTW(Dynamic Time Warping)ベースの実数値列アライメントを用いて伝搬グラフを構築する方法を開発した。位置情報を用いないで伝搬関係を推定できるため、細胞間の信号の伝搬のみでなく、株価の他の株価への影響の伝搬関係など曖昧な伝搬関係の抽出にも使えることを株価データを用いて確認した。
    シンギュラリティ成分検出の前処理としてイメージングデータからノイズや外乱を取り除くための正則化手法について研究を進めた。具体的には、イメージングデータに内在するスパース性を引き出す変換を構成し、スパース性を評価するノルムと組み合わせて正則化関数を設計した。加えて、この正則化を含む最適化問題としてノイズ・外乱除去問題を定式化し、これを解くアルゴリズムを開発した。最後に、実際のハイパースペクトルイメージングデータを用いた大規模な比較実験によって有効性を実証した。
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Hokkaido University, 18H05413
  • eXtFS:Feature Selection and Exploration in extremly large multi-label classification problems
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2015 - 31 Mar. 2018
    Kudo Mineichi
    We have dealt with "multi-label classification" problems where an object is assigned multiple labels. This study aimed at raising the classification performance and speeding up without degradation of performance. Our achievement is three of the following. First, we have pointed out the importance of the correlation between labels and showed several ways using it. Second, to keep a realistic processing time, we showed that the problem division of samples on the basis of their features or labels in some experimental results. Last, we pointed out the necessity of a special treatment on labels that appear rarely or have been forgotten to assign.
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 15H02719
  • Analysis of Repetition Structure in Huge Sequences
    Grants-in-Aid for Scientific Research
    2013 - 2015
    Nakamura Atsuyoshi, KUDO Mineichi, TAKIGAWA Ichigaku, MAMITSUKA Hiroshi, KIDA Takuya, OKUBO Yoshiaki
    We developed an algorithm for enumerating frequent approximate string patterns, and proposed a method of extracting occurrence regions of the enumerated patterns as a method of extracting interspersed repetitive elements in a huge sequence like a DNA sequence. Patterns of proposed methods have occurrences of clear boundaries, so there is little chance to count essentially the same region more than once. Furthermore, our enumeration algorithm runs very fast and with small memory. According to our empirical results using human chromosome 21, a half of the known Alu regions, which are famous interspersed repetitive elements, is extracted as occurrence regions of 100 representative patterns that were selected from enumerated frequent approximate patterns.
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, Principal investigator, Competitive research funding, 25280079
  • A Study on Data-Dependent Complexities
    Grants-in-Aid for Scientific Research(基盤研究(C))
    2009 - 2011
    Atsuyoshi NAKAMURA, Mineichi KUDO, Jun TOYAMA
    As a data-dependent complexity measure, we proposed data-dependent VC dimension of Sperner family, and in hyper-rectangle subclass problem, we developed a fast algorithm for datasets with small such VC dimension. We also empirically showed efficiency of the algorithm using real data. Furthermore, as a complexity measure of contiguous repetition structure of a string, we proposed the size of a minimum repetition representation string (MRRS) for a given string. We developed a fast algorithm for constructing an MRRS and analyzed the repetition structure of DNA sequences using the algorithm.
    Ministry of Education, Culture, Sports, Science and Technology, 基盤研究(C), 北海道大学, Principal investigator, Competitive research funding, 21500128
  • Feature Extractions and Recognition Methods for Concept Recognition and its Applications.
    Grants-in-Aid for Scientific Research(基盤研究(C))
    2006 - 2007
    Jun TOYAMA, 工藤 峰一, 中村 篤祥
    1) Classification of Features: The knowledge that is necessary for judgments are not numerical score like a real number but rough categories. A new concept "granularity" based on the rough categories was introduced. We interpreted discrete data as a grouping problem. Therefore an algorithm for discovering semi-optical answer for a grouping problem was proposed.2) Discovering Prototype: The features that is necessary for judgments are not all knowledge and experiments but some abstract data. From this point of view, an algorithm that discover typical prototype in enormous data was proposed. ...
    Ministry of Education, Culture, Sports, Science and Technology, 基盤研究(C), 北海道大学, Coinvestigator not use grants, Competitive research funding, 18500124
  • Development of Classification Systems for Large-Scale Pattern Recognition Problems and Its Application
    Grants-in-Aid for Scientific Research(基盤研究(B))
    2002 - 2005
    Mineichi KUDO, 林 裕樹, 天元 宏, 外山 淳, 今井 英幸, 村井 哲也, 田中 章, 中村 篤祥, 天元 宏, 林 裕樹
    In this study, we classified the scaling problems of pattern recognition tasks into three of the following. The results are shown below, respectively.1.Scaling problem as for data number : We have changed the problem setting from the problem to achieve as high (predictive) performance as possible to the problem to attain as least computational time as possible keeping no large damage in performance. Especially, 1)a fast k-nearest neighbor was invented, and 2)a one-pass algorithm for prototype acquisition was discussed, though they are still under progress.2.Scaling problem as for dimensiona...
    Ministry of Education, Culture, Sports, Science and Technology, 基盤研究(B), 北海道大学, Coinvestigator not use grants, Competitive research funding, 14380151

Industrial Property Rights