| Presentation | 2014-11-17 Possibilities and limitations of machine learning on unweighted graphs : From the viewpoint of random geometric graph theory Yoshikazu TERADA, LUXBURG Ulrike VON, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i, j) < distance(k, l) for some quadruples (i, j, k, l) of indices, the goal is to construct a point configuration "x^^^_1,...,x^^^_n in R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding (SOE). SOE does not have any parameters that need to be tuned. As our second contribution we prove that in the large sample limit it is enough to know "local ordinal information" in order to perfectly reconstruct a given point configuration. This result shows the possibilities and limitations of machine learning on unweighted graphs from the viewpoint of random geometric graph theory. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Ordinal embedding / Graph embedding / Consistency |
| Paper # | IBISML2014-42 |
| Date of Issue |
| Conference Information | |
| Committee | IBISML |
|---|---|
| Conference Date | 2014/11/10(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information-Based Induction Sciences and Machine Learning (IBISML) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Possibilities and limitations of machine learning on unweighted graphs : From the viewpoint of random geometric graph theory |
| Sub Title (in English) | |
| Keyword(1) | Ordinal embedding |
| Keyword(2) | Graph embedding |
| Keyword(3) | Consistency |
| 1st Author's Name | Yoshikazu TERADA |
| 1st Author's Affiliation | Center for Information and Neural Networks(CiNet), National Institute of Information and Communications Technology, and Osaka University() |
| 2nd Author's Name | LUXBURG Ulrike VON |
| 2nd Author's Affiliation | Department of Computer Science, University of Hamburg |
| Date | 2014-11-17 |
| Paper # | IBISML2014-42 |
| Volume (vol) | vol.114 |
| Number (no) | 306 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |