header

トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS

専攻談話会(セミナー)

2011年度第8回

日時: 2011年11月25日(金)11:00-12:00

会場: 西8号館W棟8階W809号室

講演者: Ellen Hidemi Fukuda 氏 (State University of Campinas & Kyoto University)

題目: Differentiable exact penalty functions for nonlinear second-order cone programs

要旨: We propose a method to solve nonlinear second-order cone programs (SOCPs), based on a continuously differentiable exact penalty function. The construction of the penalty function is given by incorporating a multipliers estimate in the augmented Lagrangian for SOCPs. Under the nondegeneracy assumption and the strong second-order sufficient condition, we show that a generalized Newton method has global and superlinear convergence. We also present some preliminary numerical experiments.

2011年度第7回

日時: 2011年9月21日(水)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Johaness Koebler 氏 (Humboldt Univ. at Berlin)

題目: Canonizing interval and circular arc graphs

要旨: We present logspace algorithms for computing canonical representations for interval and special cases of circular arc graphs. As a consequence, the isomorphism and automorphism problems for these graphs are solvable in logspace.

2011年度第6回

日時: 2011年9月15日(木)16:00-17:30

会場: 西8号館W棟8階W809号室

講演者: Jitamitra Desai 氏 (Nanyang Technological University)

題目: A fractional programming approach for determining the stability number of a graph

要旨: In this talk, a continuous optimization approach for determining the stability number (or independence number) of a graph via a fractional programming formulation is presented. While the problem of finding the independence number of a graph is a well-studied problem in the IP literature, the use of continuous optimization techniques for solving this problem is a relatively new area of research. Using some previously known properties of the stability number, we examine several convexity results of the fractional programming formulation, and prove that the fractional program yields the stability number. Characterizations of the local maxima are described, and tight lower and upper bounds on the stability number are derived. These results are utilized in developing a new global optimization algorithm for solving the fractional programming formulation. Detailed computational results that show the efficacy of this approach along with comparisons to other bounds on the stability number are provided using standard test sets in the literature.

2011年度第5回

日時: 2011年7月6日(水)14:15-

会場: 西8号館W棟8階W809号室

講演者: 岩田具治 氏(NTTコミュニケーション科学基礎研究所)

題目: 確率モデルに基づくデータマイニング

要旨: NTT コミュニケーション科学基礎研究所にて行ってきた確率モデルに基づくデータマイニング研究(定額制サービスのための推薦,クラス構造の可視化,ソーシャルアノテーションの解析)を紹介する.確率モデルを用いることにより,データに内在する不確実性に対応でき,また,確率論の枠組みに従い,多様な情報を統一的に扱うことができる.

定額制サービスのための推薦:定額制サービスを提供しているオンラインストアが収益を上げるためには,ユーザの契約期間をできるだけ延ばすことが必要である.従来推薦法では,購入される確率を最大化するためにユーザの嗜好に合致する商品を提示する.しかしながら,従来法により必ずしも契約期間が延びるとは限らない.そこで,定額制サービスを想定し,契約期間が延びる確率を最大にする推薦法を提案する.提案法では,まず,生存時間解析を応用し,契約期間の長いユーザに特徴的な購買パターンを抽出する.そして,抽出されたパターンと同じような購買行動になるように商品を推薦する.また,効果的な推薦にするため,最大エントロピーモデルを用いてユーザの嗜好を推定する.携帯電話用漫画配信サイトのログを用いた実験を紹介する.

クラス構造の可視化:データをそのクラス構造とともに低次元の可視化空間へ埋め込む非線形次元圧縮手法を紹介する.提案法は,可視化空間において混合正規分布を仮定し,原空間における事後確率と可視化空間における事後確率のKullback-Leibler ダイバージェンスができるだけ小さくなるようにデータとクラスを埋め込む.データ間距離(非類似度) を直接計算しないため,従来法に比べ計算効率がよい.分類済Web ページを用いたクラスラベル付きデータの可視化,手書き文字を用いた分類モデルの可視化,単語群を用いたラベルなしデータの可視化を行い,提案法の有効性を示す.

ソーシャルアノテーションの解析:ソーシャルアノテーションサービスでは,ユーザが任意のタグを付与できるため,しばしば内容に関連しないタグが含まれる.内容に関連するタグを自動的に抽出することにより,情報検索の性能向上や,文書分類や画像認識などの機械学習タスクの精度向上が期待できる.そこで,潜在トピックモデルに基づく内容に関連するタグの抽出法を提案する.提案法では,内容とタグが生成される過程をモデル化し,確率的EMアルゴリズムを用いてモデルを推定することにより,関連するタグを自動的に抽出する.人工データ,および,Web ページと画像を対象とするソーシャルアノテーションサービスのデータを用いて提案法の有効性を示す.

2011年度第4回

日時: 2011年5月27日(金)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Neil Immerman 氏 (University of Massachusetts Amherst)

題目: P versus NP: Approaches, Rebuttals, and Does It Matter?

要旨: NP contains all those problems that we could efficiently solve if "guessing were free", i.e., all those problems whose solutions we could recognize as correct if they were given to us in an appropriate format and context. We've known since 1971 that a large class of important combinatorial problems including boolean satisfiablity (SAT) are NP complete, i.e, hardest problems in NP. If any of these had a solution in P, then so would all other problems in NP.

How hard is SAT, or any other NP-complete problem? It is well believed that P is not equal to NP and that SAT requires exponential time on some hard instances. However, SAT solvers are now in practical use as general problem solvers, currently working even on instances with a million variables.

I will explain some of these issues, laying out what we do know, what we do not know, and what we hope to understand once the P versus NP question, together with many similar but less famous open questions, are finally resolved. At the same time, this talk will present a survey of descriptive complexity -- the logical approach to compexity that I have been pursuing for years.

連絡先:渡辺治 watanabe(at)is.titech.ac.jp

2011年度第3回

日時: 2011年5月18日(水)13:30-14:30

会場: 西8号館W棟10階W1008号室

講演者: 梅原雅顕 氏 (東京工業大学 数理・計算科学専攻)

題目: 変曲点を持たない平面閉曲線について

要旨:

平面上の正則閉曲線は,交点数が有限で高々2重点しかもたないとき,「一般的」であるという.一般的な平面正則閉曲線が与えられたとき,その閉曲線の変曲点の個数を下から評価する不変量を構成する.この不変量は,与えられた閉曲線の組み合わせ論的な情報から有限回の手段で計算可能なもので,与えられた交点数の閉曲線の中で,変曲点を持たないものを特徴づけるのにきわめて有効である.実際,この不変量を用いて,5交点以下の変曲点をもたない一般的な正則閉曲線の分類を与える.また,変曲点と2重接線との関係など,現段階で未解決の問題をいくつか紹介したい.今回話す内容は,名城大学の小沢哲也氏と,一昨年前に私が指導した現在高校教師の大野君との共同研究です.

2011年度第2回

日時: 2011年5月11日(水)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Valentine Kabanets 氏(Simon Fraser Univ., Computing Science)

題目: Direct Product Codes: Decoding and Testing

要旨:

※ Kabanets 先生は数理計算科学専攻の客員教授として5月〜8月まで滞在され,計算の複雑さの理論(平均時計算量)の講義を行います.(数理計算科学特別講義第三,5月16日より)

本講演はそれに先駆けて行う関連分野の(講義より少し高度な)最近の研究トピックスに関するお話です.ふるってご参加ください.

Abstract. Given a Boolean function f, and parameter k (natural number), we define f^k to be a function mapping k-tuples of inputs x_1,...,x_k to the k-tuple of values f(x_1),...,f(x_k). If we think of the truth table of f as a message, then the truth table of f^k can be viewed as an encoding of f using the Direct-Product Code. This encoding is useful in complexity and cryptography for hardness amplification: if f is somewhat hard on average to compute by certain efficient algorithms, then f^k is much harder on average to compute by a related class of efficient algorithms.

Over the past several years, together with Impagliazzo, Jaiswal, and Wigderson, we gave tight results about both decodability (actually, list-decodability) and testability of such Direct Product codes. Here decodability is the task: given a corrupted version of f^k, recover (a small list of candidates for) a message close to the original message f. The testability is the task: given an oracle F, decide if F is close to being (approximately equal to) f^k, i.e., if F is a Direct-Product codeword. Somewhat surprisingly, the testability result uses the ideas developed for the decodability result, even though there is no formal connection between these two tasks. Finally, the testability result allows us to prove a version of Parallel Repetition Theorem for certain 2-player games, basically showing that the ability to win in k copies of a game decreases exponentially with k.

2011年度第1回

日時: 2011年4月27日(水)14:30-15:30

会場: 西8号館W棟8階W809号室

講演者: 一杉裕志 氏 (産業総合研究所産 ヒューマンライフテクノロジー研究部門)

題目: 脳とベイジアンネット

要旨:

大脳皮質は脳の中で知能にもっとも深く関係する重要な組織である。計算論的神経科学という分野において、大脳皮質の本質的な機構がベイジアンネットであると理解する研究者が少しづつ増えている。ベイジアンネットに基づくモデルは大脳皮質の複雑で多様な振る舞いを、少ない仮定で計算論的にきれいに説明する。それだけではなく、脳がどのようなアルゴリズムやデータ構造を用い、それらをどのような神経回路で実現しているかについても、ベイジアンネットを鍵として徐々に具体的に理解されつつある。大脳皮質の情報処理原理が明らかになることで、人間のような高い知能の計算機による再現も、もはや夢ではなくなりつつある。