A K-Means-Based Multi-Prototype High-Speed Learning System with FPGA-Implemented Coprocessor for 1-NN Searching

• AN Fengwei

  Research Institute for Nanodevice and Bio systems, Hiroshima University

• KOIDE Tetsushi

  Research Institute for Nanodevice and Bio systems, Hiroshima University

• MATTAUSCH Hans Jürgen

  Research Institute for Nanodevice and Bio systems, Hiroshima University

抄録

In this paper, we propose a hardware solution for overcoming the problem of high computational demands in a nearest neighbor (NN) based multi-prototype learning system. The multiple prototypes are obtained by a high-speed K-means clustering algorithm utilizing a concept of software-hardware cooperation that takes advantage of the flexibility of the software and the efficiency of the hardware. The one nearest neighbor (1-NN) classifier is used to recognize an object by searching for the nearest Euclidean distance among the prototypes. The major deficiency in conventional implementations for both K-means and 1-NN is the high computational demand of the nearest neighbor searching. This deficiency is resolved by an FPGA-implemented coprocessor that is a VLSI circuit for searching the nearest Euclidean distance. The coprocessor requires 12.9% logic elements and 58% block memory bits of an Altera Stratix III E110 FPGA device. The hardware communicates with the software by a PCI Express (×4) local-bus-compatible interface. We benchmark our learning system against the popular case of handwritten digit recognition in which abundant previous works for comparison are available. In the case of the MNIST database, we could attain the most efficient accuracy rate of 97.91% with 930 prototypes, the learning speed of 1.3×10^-4s/sample and the classification speed of 3.94×10^-8s/character.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E95.D (9), 2327-2338, 2012

  一般社団法人 電子情報通信学会

キーワード

• multi-prototype learning system
• K-means clustering
• software-hardware cooperation
• one nearest neighbor (1-NN)
• FPGA-implemented coprocessor
• nearest euclidean distance searching

詳細情報

• CRID: 1390282679356388224
• NII論文ID: 10031142849
• NII書誌ID: AA10826272
• DOI: 10.1587/transinf.e95.d.2327
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E95.D/9/E95.D_2327/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可