OR トピックス

アノレゴリズムと特許
一ーその 5. カーマーカー特許に対する異議申立て一一

今野浩
11111111111111111111111111111111111""
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111'111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111【カーマーカー特許上陸】

前回報告したとおり，特許庁

人ならば，この内容をもとにして，一応のプログラムがは 9 月 6 日の特許公報 [IJ で，カーマーカー氏と AT&書けるようになっている(ただし，このままで超大型のT から出されていた「最適資源割当て方法」に関する特問題を解くための効率的なプログラムが書けるか，と言許申請を「公告J した.これは特許庁が審判の結果，同えばそれは全く別問題である).

申請への特許付与を認めたもので，公告後 3 カ月以内にいても，前回のやや手軽な基準と違って，双対ギャップ異議申立てがない場合には，カーマーカー特許が日本にをもとにした，より厳粛な方法を採用している.さらにまた収束性の判定につこの方法の応用に関する記述も，米国特許に比べるとかも成立ずることになる.

筆者にとっては予想外の逆転審判であったが，これまなり詳細である.日本特許庁が 91 年に拒絶した申請は，での経過から見て十分予想された事態であった，と受け米国特許のコピーそのものであったから，審判の過程で止める特許関係者も少なくないようである.たとえば，大幅に内容が改善されたことは確かである.

東芝の北口秀美氏は，本年 5 月の時点、で，米国で成立ししかし，われわれ数理計画法の専門家の目から見ると，た特許が日本で成立しない，ということは日米関係の現今回の内容も依然として拒絶審査を覆すに足るものとは状から見て考えに〈く，したがってカーマーカー特許は言い難い.そこで以下では，前号までの繰り返しをなるいずれ日本でも成立する，と予測している [2J.

べく避けながら，この判断の理由を述べることにしよう.

筆者自身も，通産省の不可解な助成金取消し事件 (10 月号参照)【社撰な公告文書】

まず第 1 は，記述が改善されてはいや，完敗したはずの AT&T 関係者が意外に元気(? )だるが，その内容がかなり杜撰だ，と L 、う事実である.たという噂，そして特許庁審査官のこの問題に対するきわ

とえば，アフィン変換法の核心部分に当たる方向ベクト

めて慎重な発言 [3J など，気懸かりなことがないわけで

ル P の式( 8 月号参照)が間違っている，という信じられはなかった.しかし特許成立を予想した人々といえどないミスがあること(公告に示された公式を使うと，線も，今回のような内容のものが公告されると考えていた

形計画問題の最適解はおろか，実行可能解すら得られな人は，少なかったので、はないだろうか.

い! )をはじめ，添字や人名にも誤記が多く，学会水準

そとで今回は，公告された特許の問題点を指摘し今

公告文書は，申請原本を元に印刷業者が作成したもの

後の対応について述べることにしたい.

7.

で，これにミスがあるからといって，直ちに特許取消し

カーマーカー特許の問題点【公告の概略】を大きく下回る内容のものである.になると L 、う性質のものではないが，公文書たるもの，今回合格とされた申請は，アフィン変換もっときっちりした内容チェックを行なってもらいたい法を用いた線形計画問題の解法と，その最適資源配分へものである(もし原本に誤りがあれば大問題である).の応用に関するもので，【新規性の問題】1988年に米国で成立した 3 件の次は，より本質的な“発明の新規性"特許のうちの 1 つ( 8 月号参照)と，本質的に同じ内容のに関する問題である.すなわちここで記述されているアものである.しかし米国特許に比べると，その記述は大フィン変換法は8 月号でも述べたとおり，1967年にデスケーリ

ィキンが提案した方法と同じものであり，新規性を欠くング行列 D ，またステップ・サイズ自の決め方が今回はと L 、う事実である.確かに，この特許が申請された 1986

きちんと記されており，この分野の標準的な知識をもっ年 3 月の時点で，カーマーカ一氏がディキン論文の存在幅に改善されている.具体的には，出発解 X O ，を知っていたと L 、う可能性は少ない.しかし，専門家のこんのひろし東京工業大学工学部人文社会群問で，

宇 152 目黒区大岡山 2-12-1

えると AT&T がこれを知らなかったはずはない.した

1993 年 12 月号

1988年にはこの事実が常識となっていたことを考© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(33)645がって，AT&T は 91 年の審判請求を見合わせるべきであった.とを意味する.

数理計画法の世界では，たとえ公式自体は基本的に同そこで，この事実を裏書きするために88 年当時ーであっても，その細部に工夫を加えることによって，Mathematical Programming 誌の編集長を務めて L 、計算効率がし、ちじるしく改善されることが立証されれた，コーネル大学のトッド

ディば，独創性があるものとして専門誌に採択される場合がキン論文を詳細に検討した上で，この分野の指導的研究(M. Todd) 教授が，ある.したがって，仮りにカーマーカー特許が成立した者たちに送った，

1988年 2 月 9 日付の手紙の内容を紹介としても，上で述べた規準において独創性があるアルゴ

一ここにソ速の数学者ディキン氏から送られた手もの)を使用した場合には，カーマーカー特許の侵害にしよう:

紙の写しと，リズム(すなわちがと D および日の決め方が違っている

Doklady 誌に掲載された原論文，およびその解法の収束性の証明が記述されたControlトableSystem誌掲載の論文を同封します.ここで明らかになったことは，現在カーマーカー法の一変形版として知られるアフィン変換法が，ディキン氏によって20年前に提案されていた，と L 、う事実です.…・このことより，今後アフィン変換法の提案者としては，ディキン氏の名前に言及されるべく，お知らせする次第です.

ならな L 、，ということがはっきりすれば，この特許がもたらすマイナスの影響は局限されたものとなるであろう.

【情喝の材料に使用される危険性】

ディキン論文の存在が明らかになった以上，AT&T は審判請求を取り下げるべきであった.また審判の過程で審判官は，数理計画法の専門家に対して意見聴取を行なうべきであった.筆者はわが国におけるこの分野の専門家集団 RAMP

ここで重要なことは，繰り返すが， 88年に(日本 OR 学会数理計画法研究部会)のトッド教授の判定は，この分野主査を務める関係上，専門家に対するヒアンリグがあっのすべての専門家によって追認されたものであって，専たとすれば，これを知る立場にあったが，そのような事門的な見地からは反論の余地がないこと(ちなみに，こ実は，現在にいたるまで報告されていない.の方法の核心である方向ベクトルの公式は ，

x O, D, aの決め方を除けば両者とも全く同一である)，また 1967年には原論文の英訳が Doklady 誌に掲載されていたという点である.

米国においては，不幸なことにディキン論文発見と相前後して，カーマーカー特許が成立してしまった.そして現在，ほとんどの研究者が，アフィン変換法特許は無効であると考えているが，裁判費用と研究活動への支障【特許侵害の範囲】

特許法は，を考えると，とても裁判には踏み切れないのが実情であ

特許出願前に日本国内，または国外において配布さる.したがって，米国では発効日から 17年間，すなわちれた刊行物に記載されたもの

西暦2005年までこの特許は生き続けるであろう.

は，特許にならないものと規定している.したがって，実際，ことが明らかとなった後も，AT&T は OBl

もし特許庁が，ディキン論文の存在を知りながら，カーから売り上げの 5% を取り立てることに成功している

マーカー特許に新規性ありと認めたとすれば，その意味(1 0 月号参照).これについて OBl の開発者の 1 人であするところは重大である.それは，特許庁が自ら(数学)るシャノ教授は裁判で争えば ，アルゴリズム特許を審査する能力を欠いているというこ許を侵害していないとしづ主張が通ると思うが，裁判にとを認める結果となるか，さもなければ，専門家が基本なった場合の費用と，その期間 OBl の販売が差止めにOBl tJ 'AT&T 特的同ーと判断する程度の内容であっても，特許対象とななる可能性を考えると，和解に応じた方が得策て‘あるとることを認めたかのいずれかだ，と L 、う論理的帰結であ判断した J と述べている.

る.

わが国の場合でも億円単位の裁判費用に加えて，もし後者であるとすれば，カーマーカー以後のあらゆ敗訴した場合のダメージを考えると，中小ソフトウェア

るアフィン変換法の改良版(たとえばステップ・サイズ

会社は，a や，スケーリング行列 D に少々の改善を施したもの)けた段階で，直ちに和解交渉に応じざるを得ないであろOB1 に組み込まれた主・双対内点法や，う.この意味で，裁判に耐えられるのは大企業のみといはもとより，AT&T から特許侵害の疑いありとの通告を受

NUOPT に使われている内点法などは，すべてカーマうことになる.ところが，大企業は AT&T とはクロスーカー特許とは独立であって，特許侵害とはならないこ・ライセンス契約を結んでいるケースが多いから，結局646(34)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

裁判は行なわれないまま，機械，さらには何の装置も使用することなく実施さAT&T は次々と和解金を手れるものである.にする可能性が高い.この和解金は OBl の場合は 5%で済んだが，栢手次第でどのような数字をもち出してく【アルゴリズム特許で E 氏は金持ちになれるか?】るかわからないのが無意味なところである.

号では，アルゴリズム特許に対する代表的な賛成・反対【拒絶審査の妥当性】

意見を紹介し，併せて筆者の個人的な意見を披露した.

すでに述べたとおり，特許庁は，10月1991 年 3 月にこの申請を“純粋に数学であるべという現ここです土，数理計画法の研究者である K 氏が，ある物理由で拒絶している.これに対して AT&T は，電話回路システムの最適化を効率的に実現することができる，革網と L 、う資源の最適配分問題のリアル・タイム処理，と新的なアルゴリズムを“発明した"場合を想定して，アいう技術的課題を解決するものと主張したが，当時は受ルゴリズム特許の虚しさを説明しよう.

け入れられなかったという.

学術的な名誉よりも金銭的報酬を重視する K 氏が，学ところが，今回 AT&T は， Diamond対 Diehr 判決

会での発表もそこそこに，特許申請を行なうことを決意(9 月号参照)において，米国最高裁が数学アルゴリズムし，必要な 60万円の費用を用意したものとしよう.そしを特許認定した事例があることを取り上げ，この発明がて有能な弁護士と審査官に援けられて，いくつもの異議“物理システムを構成あるいは動作するために，現実に申請を蹴飛ばしてめでたくこれが特許になったものとし使用されるべき最適値をリアル・タイムで提供することよう.誰もこのアルゴリズムを使用してくれなければ，にある"とし、う理由で，特許となりうると L 、う主張を行60万円は丸々損失となるのは当然、として，他人が使用しない，特許庁もこれを認めた模様である.また AT&Tた場合はどうだろうか .K 氏が収入を得るためには，まはこの方法の適用範囲として，電話回路網の制御のほかず使用した事実を確認することが必要である.しかし，に，産業プロセスの制御，商業商品を製造するための原ソフトウェアの大半は，注文主対ソフトウェア会社の聞料の配分，製油製品の混合，複数のユーザーへのコンピの契約にもとづく単品生産であるから，外部からこれをュータ資源の割当て等，最適資源配分すべてにこの特許確認するのは容易なことではない.自らこの作業を行なの範囲が及ぶことを主張している.したがって，この特おうとすれば，研究・教育活動に支障をきたすから，こ許が成立すれば，物理システムを伴わない応用(たとえれは実行不可能である.だからといってこれを他人(弁ば，最小絶対偏差あてはめなどの資源配分を伴わない応護士等)に依頼すれば，得られるとも限らない収入の代用や，ポートフォリオ最適化などの人為的な取決めをも償として，かなりの手数料を取られるに違いない.といとに行なう最適化など)を除く，線形計画法の広範な応うわけで K 氏は，コスト負担に耐えられる大ソフトウェ用分野に対する権利をカバーすることになる.線形計画

ア会社に，この特許を売り渡すか共同申請することにな

法は，組合せ最適化や，非線形最適化を含むあらゆる最るが，買う側も実際収入源となる特許は 1000に 3 つ程度適化の基礎となるものであり，これから先も思いもかけであることを熟知しているから，ない応用分野が出現する可能性もある.ここで想い起こ知れたものであろう.かくして K 氏の努力は，期待するされるのは，ほどには報われない結果に終わる公算が大きいのであGottschalk対 Benson裁判( 9 月号参照)

で，米国最高裁が 2 進 10進変換法に対する特許を棄却した際の，誠に説得力のある判決内容である.その判決文

K 氏が手にする収入はる.

一方，ソフトウェアを作成し販売する側から見ても，の í 2 進 10進変換」を「線形計画法j に置き換えた文章

アルゴリズム特許はきわめて不都合なものである，なぜをここに再録して，筆者の主張に代えよう:なら，5000行のプログラムはおそらく 10万の部品(アルここで述べられているプロセスはきわめて抽象的でゴリズム)でできているから，この中に特許侵害に当たあり，線形計画法に関わる既知，未知の使用法をすべるものがあるか否かを調べるのは大変な手間である.してを網羅するものである.この利用法は，かも，このための検索ファイルが整備されていないこと(i) 石油精製法から産業プロセスの制御，商業商品をからして，ソフトウェア作成は地雷原を歩くようなもの(首)製造するための原料の配合，複数ユーザーへのコンとなる可能性がある.大半の特許侵害は不発弾のようなピュータ資源の割当て等，最適資源配分に関するすもので，破裂する可能性は小さいが，特許侵害に伴うベべての分野をカパーする可能性があり，ナノレティーを考えれば現存する機械，もしくは将来発明されるであろう

1993 年 12 月号

3 つの特許を侵害するだけで，すべての利益が吹き飛んでしまう可能性がある.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(35)647

【アルゴズリム特許と技術進歩】に，ここで， 1980年代初頭ワープロにかかわるすべてのアルゴリズムが特許指8. 今後に向けて定された上に，ワープロ自体が 890 万円で売られていた【異議申立て】事態を想定しよう.この場合，クロス・ライセンス契約は，特許庁も多くの異議申立てがあることを予想してい新聞報道によれば，今回の公告に対してを結んだ大企業以外はワープロの改良に乗り出すことはるというが，筆者も，以下の 4 点からこの特許に対するできず，いまも初期の高価で性能が悪いワープロが生き異議申立てが可能であると考えている.

続けていた可能性がある.日本の大電機メーカーはモラ(1) 公告の内容に関する基本的誤り

ルが高 L 、から，このようなことになったとは思わないが，(2) アルゴリズムの新規性に関する疑問

もし AT&T が 1984年にはじめてワープロを発明してい(3) 数学アルゴリズムに対する特許付与の妥当性に関たとすれば，これは十分にありえた話である.特許は完全な独占権を発明者に与えるものであって，その使用をする疑問

但)数学アルゴリズムに限らず，非数学的アルゴリズ

他人に許可するもしないも発明者の自由である.発明者

ムを含む，すべてのアルゴリズムの特許付与の妥当が他人にその使用を認めずに，いまもなお 10年前のワー性に対する疑義

プロがマ}ケットを覆っていたとしたらどうであろう

このうち (1) と (2) に関しては，関係者すべてが異議申立か.それと同様，カーマーカー特許が成立したために，てに賛成するものと思われるが， (3)以下については(日

誰も内点法ソフトウェア開発に取り組めず，

いまも 890

経新聞アンケートや ACM アンケートで見るとおり)専万ドルの KORBX が内点法を窒息させていたかもしれ門家の間でも意見が割れるであろう.しかし，これまでないのである.

述べてきたような疑問点が多くの人々の知るところとな【特許庁の審査能力】

今回の特許公告で明らかになったことは，数学アルゴリズムに関する特許庁の審査能力の限界である.筆者は，日本の審査官は米国の審査官よりれば， (3) の立場からの異議申立てに賛同する人が増えてくれるものと期待したし、(楽観的過ぎるであろうか).

筆者は，数理計画法の専門家数名と連名で，早急に (1)

はるかに能力が高い人々の集まりであるものと信じていと (2)の立場から異議申立てを行なうことを考えているがるが，かねてより，ソフトウェア/アルゴリズム特許の仮りにこれによって特許が無効になったとしても， (3) と審査に関しては，構造的欠陥をもつのではないかと危倶(4) の問題は残ることになる.

していた.なぜなら，ごく最近までソフトウェアやアル【腫書店を良性のままに閉じ込めることは可能か】

ゴリズムが特許の対象外であったことからもわかるとお現在の状況を病気にたとえれば，数理計画法あるいはり，この分野に通暁した審査官はきわめて少数だ，と考数理科学の分野でつの腫場が検出された状況に相当えられるためである.

するであろう.もしカーマーカー特許が無効となれば，特に審判請求を審査する審判官は，少なくとも 15年以煙車事はいったん摘出されたことになる.しかしこの腰前に審査官になった人々であるため，この中でソフトウ湯はきわめて悪性なものに転化する可能性をはらんでいェアをアルゴリズム開発の実態に通じている人々は，きる.実際 AT&T はカーマーカー特許に関連する 6 件のわめて例外的な存在であろう.したがって今後もいった特許を日本特許庁に申請中であると言われており，このん拒絶された申請が，審判に回ったところで逆転成立す

うちの 1 つが 9 月 13 日に公告されている [5J.

これは，カるケースが続発する可能性が高い.これこそ，まさにカーマーカー・アルゴリズムを用いて，大学での時間割編ーヒン(B. Kahin) が指摘した状況 [4J ，すなわち，い成の効率化を行なう方法に関するもので，公告文書を読ったん拒絶された特許が，連邦巡回区控訴裁判所に控訴んだ限りでは，新規性のないものである.またわが闘で、されると，その 60%以上が成立する，と L 、う米国での状も，好機到来とアルゴリズム特許を歓迎する数理科学者

況の到来を予想させるに十分である.審判プロセスにおが L 、るのも事実である.

いて，AT&T 側の主張を聞くだけでなく，ソフトウェ

このように腫腐はすでに体内の数カ所に転移を始めてア/アルゴリズム専門家の意見を汲み上げていれば，こいる.本来は，このような病気に羅らないためには日頃のような新規性のない特許が成立することはなかったはの摂生が肝要で、あることは L 、うまでもない.しかしこのずであるが，専門家からこのような批判に，裁判官はど病気は米国で発生し，不幸なことに日本でもすでに発病のように答えるのであろうか.

してしまったのである.はたしてこの腫療を完全除去す

648 (36)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチるか，さもなくば良性のまま閉じ込めることは可能であた主役たちのほとんど全員と言葉を交わす機会をもてた

ろうか.このためには，誰かが勇気をふるって訴訟を起のは幸運であった.いずれ機会をみてノンフィクシこし，裁判所での公開討論によって決着をつけることがヨン・線形計画法」というタイトルで，この事件を含め必要とされる.その時間も資金もない研究者としてはアて線形計画法にまつわるさまざまなドラマを再現してみルゴリズム専門家，ソフトウェア専門家に対して事態のたし、と考えている.

重大きを訴え，より多くの人々がこの問題を真剣に考え

これまで述べてきたとおり，筆者はアルゴリズム特許ることを期待するしかないのは誠に残念なことである.には反対するものであるが，決してソフトウェアの権利【ソフトウェア保護のための制度】

保護が現行の著作権で十分であると言っているわけではアルゴリズム専門家の多くは，アルゴリズム特許に反対していることはすでない，ということを再確認しておきたい.なお筆者は，に述べたとおりである.しかし，アルゴリズム開発者にこの 5 月に OR 学会の中に設立された，ソフトウェア研対して，単なる名誉だけでなく金銭的報酬があってもよ

究部会の知的財産権分科会の取りまとめ役を引き受けるい，と考える人々がし、ることもまた事実である.このよこととなったが，そこでの議論の進展を見て，いずれ再うな状況の下では，数理計画法学会の「アルゴリズムとびこのような報告をさせていただく機会がめぐってくる法律」委員会が主張するアルゴリズム/ソフトウェア特ことを念じつつ，筆を指くこととする.

許全廃を実現することは難しい.では，すべての人身が謝辞納得するような，ソフトウェア保護のシステムは構築可

この原稿をまとめるにあたって，相田義明(特許庁)，能であろうか.現状に流されず発想、を転換すれば，いく

北口秀美(東芝)，玉井哲雄(筑波大学)，中川淳司(東京

つかの可能性がすでにいくつか提示されている.

工業大学)，山際和久(日本経済新聞社)，

その 1 つは，前回に紹介した OTA の提案にあるソフbinson( ウィスコンシン大学)，

StevenRoｭ

PhanThien Thach

トウェア権法の制定であり，もう 1 つは前田英次郎氏が(東京工業大学)，および日本 OR 学会ソフトウェア研究

提唱する，ソフトウェア売上げに比例するアルゴリズム部会の八巻直一(システム計画研究所)，前田英次郎

使用料徴集制度である.この提案については別の機会に(Terry) をはじめとする諸氏から，貴重な資料およびごゆずるが，考え始めればいろいろな知恵が出るものであ意見をいただいた.もとより本文に記述された内容は，る.カーマーカー特許に対する異議申立ての一方で，特すべて筆者の責任に帰すべきものであるが，上記の諸氏許に替わるべきアルゴリズム/ソフトウェア(開発者)にはこの場を借りて，厚くお礼申し上げたい.また，エ保護の制度に関する模索が始まっている.このようなシンジニアの無謀な冒険に対してそーラル・サポートを賜

ステムを具体化するためには，エンジニアだけでなく法わった，竹内啓先生(東京大学)をはじめとする，科学律専門家との協力が不可欠であることは言うまでもな

研究費重点研究領域「高度技術社会のパースペクティプ jい.幸い，日本の法学者の中にも，この事態を深刻に憂のメンパー諸氏，そしてこのような文章に貴重なスペー慮する人々がおられることは心強い限りである.また問スを提供してくださった，本誌編集長の森雅夫氏(東京

題の性質からして，日本国内だけでなく，世界の(特に工業大学)に，感謝の言葉を棒げる次第である.

米国内の)アルゴリズム研究者とのより強い連帯が必要

筆者は非力ながら，このような可能性を求めて，微力報処理，おわりに情

34(1993) 973‑982.

[3J 相田義明“ソフトウェア特許に関する質疑応答ヘ

5 回にわたるアルゴリズム特許についての連載は，今回をもって終了する.筆者はこれまで、 20数年間にわたって，数理計画法の研究を本業としてきたが，1984年に始まったカーマーカ一事件は，文字どおり血湧き肉踊る大ドラマであった.自らは，ついに内点、法の研究にたずさわる機会がなかったが，その近傍にあって，舞台を彩っ1993 年 12 月号(B2) 平 5-61672 ，日本国特許庁，1993年 9 月 6 日.

[2J 北口秀美“ソフトウェア特許の理想、と現実"，を尽くし T品、と考えている.

9.

参三考文献

[1J 特許公報であることを痛感している.

ソフトウェア情報センター，[4J Kahin , B. ,1993年 5 月.

(今野浩訳)“ソフトウェア特許に反対するぺ第 3 回 RAMP シンポジウム報告集，

141 ,日本 OR 学会，

132‑

1991.

[5J 特許公報 (B 2) 平 5 -63822 ,

日本国特許庁，

1993年 9 月 13 日.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(37)849