(57)【要約】本発明は、次のメディアフレームの出力品質を設定する方法およびシステムに関するものであり、次のメディアフレームの複数の出力品質のうちから出力品質を与えるよう着想されているアプリケーション手段ならびに前回のメディアフレームの処理時間および出力品質を次のメディアフレームの出力品質を決定するために使う自己学習制御戦略に基づいて次のメディアフレームの出力品質を設定するよう着想された制御手段とを有する。
2006524461.tif 000002
【特許請求の範囲】
【請求項１】
次のメディアフレームの出力品質を設定する方法であって、
該出力品質がメディア処理アプリケーションによって与えられ、
該メディア処理アプリケーションが次のメディアフレームの複数の出力品質を提供するよう設計されており、
前回のメディアフレームの処理時間および出力品質を次のメディアフレームの出力品質を決定するために使う自己学習制御戦略に基づいて次のメディアフレームの出力品質が設定される、ことを特徴とする方法。
【請求項２】
前回のメディアフレームを処理し、
処理済の前回のメディアフレームの相対前倒し値と、
処理済の前回のメディアフレームのスケーリングされた予算枠値と、
処理済の前回のメディアフレームの出力品質と
を有する状態を決定し、
次のメディアフレームの状態およびある可能な出力品質に基づいて報酬を決定する、
ことを有することを特徴とする、請求項１記載の方法。
【請求項３】
前記報酬が期限に遅れた回数、前回のメディアフレームの出力品質、品質変化に基づいていることを特徴とする、請求項２記載の方法。
【請求項４】
有限の数の状態に対する報酬が決定され、該有限の数の状態はスケーリングされた予算枠値の有限集合および相対前倒し量の値の有限集合によって決定されることを特徴とする、請求項２記載の方法。
【請求項５】
処理済の前回のメディアフレームの出力品質においてのみ異なる状態を減らすことによって報酬を決定する状態の数を減らすことを有することを特徴とする、請求項２記載の方法。
【請求項６】
次のメディアフレームについて、複数の出力品質のうちから出力品質を与えることができるよう着想されているアプリケーション手段と、
前回のメディアフレームの処理時間および出力品質を次のメディアフレームの出力品質を決定するために使う自己学習制御戦略に基づいて次のメディアフレームの出力品質を設定するよう着想されている制御手段とを、
有することを特徴とする、次のメディアフレームの出力品質を設定するシステム。
【請求項７】
前回のメディアフレームを処理する処理手段と、
処理済の前回のメディアフレームの相対前倒し値と、
処理済の前回のメディアフレームのスケーリングされた予算枠値と、
処理済の前回のメディアフレームの出力品質とを
有する状態を決定する決定手段と、
次のメディアフレームの状態およびある可能な出力品質に基づいて報酬を決定する報酬手段とを
有することを特徴とする、請求項６記載のシステム。
【請求項８】
処理済の前回のメディアフレームの出力品質においてのみ異なる状態を軽減することによって報酬が決定される状態の数を減らす軽減手段、
を有することを特徴とする、請求項７記載のシステム。
【請求項９】
請求項１記載の方法を実行するよう設計されていることを特徴とする、コンピュータ・プログラム。
【請求項１０】
請求項９記載のコンピュータプログラムを有する記憶装置。
【請求項１１】
請求項６記載のシステムを有するテレビ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、次のメディアフレームの出力品質を設定する方法に関するものである。ここで、前記出力品質はメディア処理アプリケーションによって与えられるもので、該メディア処理アプリケーションは次のメディアフレームについて複数の出力品質を提供するよう設計されている。
【０００２】
本発明はさらに、次のメディアフレームの出力品質を設定するシステムに関するものである。該システムは、次のメディアフレームについての複数の出力品質のうちから前記出力品質を与えるよう着想されたアプリケーション手段を有する。
【０００３】
本発明はさらに、そのような方法を実行するよう設計されたコンピュータプログラムプロダクトに関するものである。
【０００４】
本発明はさらに、そのようなコンピュータプログラムプロダクトを有する記憶装置に関するものである。
【０００５】
本発明はさらに、そのようなシステムを有するテレビに関するものである。
【背景技術】
【０００６】
上述のような方法の実施形態およびシステムは、WO2002/019095において開示されている。ここで、ビデオデッキ、ＤＶＤ−ＲＷ、ハードディスクのようなシステム上、あるいはインターネット接続上でアルゴリズムおよびスケーラブルなプログラム可能な処理装置を走らせる方法が記載されている。アルゴリズムは、たとえばビデオフレームのようなメディアフレームを処理し、該処理について複数の品質レベルを提供するよう設計されている。当該メディアフレームの許容できる出力品質を与えるために、異なる品質レベルに対する異なる要求に応じて、アルゴリズムには利用可能リソースの予算枠が割り当てられている。しかしながら、メディアストリームの内容は時間的に変動があり、当該メディア処理アルゴリズムのリソース要求も時間とともに変わってくる。リソースは有限なので、期限遅れ（deadline  miss）が起こりやすい。これを軽減するため、当該メディアアルゴリズムはデフォルトよりも低い品質レベルで走ることができる。それならそのぶんリソース要求も低いことになる。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明の目的の一つは、冒頭で述べたような、メディアフレームの品質を設定する改良された方法を提供することである。この目的を達成するため、当該方法は次のメディアフレームの出力品質を設定するのを、前回のメディアフレームの処理時間および出力品質を使って次のメディアフレームの出力品質を決定する自己学習制御戦略に基づいて行うことを含んでいる。
【０００８】
本発明に基づく方法の請求項において記載されているある実施形態では、当該方法は、前回のメディアフレームを処理し、処理済の前回のメディアフレームの相対前倒し量の値、処理済の前回のメディアフレームのスケーリングされた予算枠値および処理済の前回のメディアフレームの出力品質を含む状態を決定し、該状態に基づいて報酬および次のメディアフレームの可能な出力品質を決定することを含む。
【０００９】
本発明に基づく方法の請求項において記載されているある実施形態では、期限遅れの回数、前回のメディアフレームの出力品質、品質変化に基づいて報酬が計算される。
【００１０】
本発明に基づく方法の請求項において記載されているある実施形態では、有限の数の状態に対する報酬が決定され、該有限の数の状態はスケーリングされた予算枠値の有限集合および相対前倒し量の値の有限集合によって決定される。
【００１１】
本発明に基づく方法の請求項において記載されているある実施形態は、処理済の前回のメディアフレームの出力品質においてのみ異なる状態を減らすことによって報酬を決定する状態の数を減らすことを含む。
【００１２】
本発明の目的の一つは、冒頭で述べたような、メディアフレームの出力品質を改良された方法で設定するシステムを提供することである。この目的を達成するため、当該システムは次のメディアフレームの出力品質を設定するのを、前回のメディアフレームの処理時間および出力品質を使って次のメディアフレームの出力品質を決定する自己学習制御戦略に基づいて行うよう着想された制御手段を含んでいる。
【００１３】
本発明に基づくシステムの実施形態も請求項において記載されている。
【００１４】
これらのことを含む本発明のさまざまな側面は、以下に図面を援用しつつ説明する実施形態を参照することで明らかとなり、明快に解説されることであろう。
【発明を実施するための最良の形態】
【００１５】
図１は、強化学習におけるエージェント−環境相互作用を示している。強化学習（RL：Reinforcement  Learning）は相互作用による目標志向学習（goal-directed  learning）への計算機によるアプローチである（たとえばR.S.Sutton  and  A.G.Barto,  Reinforcement  Learning:  an  introduction,  MIT  Press,  Cambridge,  MA  1998を参照）。それは、数値的な報酬（revenue）信号を最大化するように、何をなすべきか――状態から行動へのマッピング――を学ぶことである。学習者にして意思決定者はエージェントと呼ばれる。エージェントが相互作用する相手、すなわちエージェントの外部のものすべてをひっくるめたものが環境と呼ばれる。エージェントはどのような行動をすべきかは指示されず、どのような行動が最大の報酬をもたらすかを試行によって発見しなければならない。行動は直接的な報酬に影響するばかりでなく、次の状況にも、そしてそれを通じてその後の報酬全体にも影響する。これら二つの特性――試行錯誤による探索と報酬の遅れ――がＲＬの二つの最も重要な著しい特徴である。
【００１６】
ＲＬは学習方法の指定ではなく、学習問題の指定によって定義される。その問題を解くのに好適ないかなる方法もＲＬ法であると考えられる。ＲＬにおける課題の一つは、探検と冒険の兼ね合いである。多くの報酬を得るためには、ＲＬエージェントは過去にやったことがあり、報酬を生み出すのに有効であるとわかっている行動を優先する必要があるが、そのような行動を発見するためには、以前に選択したことのない行動を試す必要がある。エージェントは報酬を得るためにはすでに知っている経験を利用する必要があるが、将来よりよい行動選択をするためには冒険することも必要なのである。ジレンマは、経験にしろ冒険にしろ一方のみを追求していたのではタスクに失敗するということである。エージェントは多様なアクションを試行し、最良と思えるものを徐々に優先するようにしていく。統計的なタスクに対しては、各行動を何度も試行して報酬の信頼できる期待値を推定する必要がある。
【００１７】
エージェントおよび環境とは別に、ＲＬシステムには三つの主要な下位要素が識別できる。政策、報酬関数、価値関数である。政策は、所与の時点におけるエージェントのふるまい方を規定する。政策とは、環境の状態からその状態においてとるべき行動へのマッピングである。一般に、政策は統計的であってもよい。報酬関数はＲＬ問題における目標を規定する。環境の知覚される状態（または状態−行動の対）のそれぞれを、その状態の内在的な好ましさを示す単一の数値すなわち報酬にマッピングする。ＲＬエージェントの唯一の目的は、長期的に受け取る全報酬額を最大化することである。歳入関数は統計的であってもよい。価値関数は、長期的に何がよいかを規定する。ある状態の価値とは、その状態から開始してエージェントが将来にわたって蓄積すると期待できる報酬の総額である。報酬が環境の状態の直接の内在的な好ましさを決めるのに対して、価値は前記政策を適用したときにその後起こると思われる諸状態やそれらの状態で得られる報酬をも考慮に入れたときの、長期的な意味での状態の好ましさを示すものである。価値は、エージェントがその全寿命にわたってなす一連の観測から評価され、再評価されていかなければならない。
【００１８】
エージェント１００および環境１０２は、エージェント１００が行動を選択し、環境１０２がその行動に反応して新たな状況をエージェントに提示する形で継続的に相互作用している。環境１０２はまた、報酬を発生させる。エージェント１００が時間を通じて最大化しようとする特別な数値である。エージェント１００と環境１０２とは、離散的な一連の時間段階ｔ＝０、１、２、３…において相互作用する。各時間段階ｔにおいて、エージェント１００は環境の状態ｓt∈Ｓ（Ｓは環境の状態の集合）の何らかの表現を受け取り、それに基づいて行動ａt∈Ａ（ｓt）（Ａ（ｓt）は状態ｓtにおいて可能な行動の集合）を選択する。１段階後、部分的には自らの行動の結果として、エージェント１００は数値的な報酬ｒt+1∈Ｒ〔実数〕を、環境の状態ｓt+1の新たな表現とともに受け取る。
【００１９】
各時間段階ｔにおいて、エージェント１００は、諸状態から可能な各行動を選択する確率へのマッピングを実装している。このマッピングはエージェントの政策と呼ばれ、πiによって表される。ここでπi（ｓ，ａ）はｓt＝ｓの場合にａt＝ａとなる確率である。政策は決定論的でもよい。その場合、各状態は単一の行動にマッピングされる。ＲＬ法は、エージェント１００がその経験の結果としてどのように政策を変えるかを規定するものである。大雑把に言えば、エージェントの目標は、長期的に受け取る報酬の総額を最大化することである。
【００２０】
ＲＬにおいて、エージェント１００の目標は、環境１０２からエージェント１００へ渡される特別の報酬信号を用いて定式化される。各時間段階ｔ＞０において、報酬は単なる数ｒt∈Ｒ〔実数〕である。略式な言い方をすると、エージェント１００の目標はそれが受け取る報酬の総額を最大化することである。これは直接の報酬ではなく、長期的な累積的報酬を最大化するということを意味している。エージェント１００が順調に実績を上げると期待されるとしたら、エージェントに報酬が与えられるのは、エージェント１００がそれを最大化することによってその目標をも達成するような仕方でされなければならない。したがって、報酬は目標と対比して考量されなければならない。
【００２１】
エージェントの目標は、長期的に受け取る報酬を最大化することである。一般に、エージェントは期待される利得（return）を最大化することが期待される。ここで、利得Ｒtは報酬の時系列の何らかの特定の関数として定義される。最も単純な場合では、利得は報酬の和
Ｒt＝ｒt+1＋ｒt+2＋ｒt+3＋…＋ｒT      （１）
である。ここで、Ｔは最終時間段階である。このやり方は、エージェント−環境相互作用が複数の部分時系列に自然に分解され、最終時間段階という自然な概念がある用途では理にかなったものである。そのような部分時系列はエピソード（episode）と呼ばれ、ゲームのプレイ、迷路の行程などいかなる種類の反復される相互作用であってもよい。各エピソードは終端状態と呼ばれる特別な状態で終わり、その後リセットされて標準的な開始状態や標準的な開始状態分布から取った標本に戻る。
【００２２】
他方、多くの場合にはエージェント−環境相互作用は識別できるエピソードに自然に分解されることはなく、限りなく継続的に進行する。これは継続タスクと呼ばれる。継続タスクについては、最終時間段階はＴ＝∞となり、よって最大化すべき利得そのものも無限大となりうる。必要となるさらなる概念が割引である。その手法によると、エージェント１００は、将来にわたって受け取る割引された報酬の総和が最大化されるよう行動を選択しようとする。特に、期待される割引された利得
Ｒt＝ｒt+1＋γｒt+2＋γ2ｒt+3＋…＋＝Σγkｒt+k+1      （２）
〔和はk＝0から∞まで〕
を最大化するようにａtを選ぶ。ここで、γは０≦γ≦１のパラメータで、割引率と呼ばれる。この割引率は、将来の報酬の現在における価値を決めるものである。ｋ時間段階未来に受け取る報酬は、すぐ受け取る場合に比べてγk−1倍の価値しかないのである。γ＜１であれば、時系列｛ｒk｝が有界である限り上記の無限和は有限の値をもつ。γ＝０であれば、エージェント１００は直近の報酬を最大化することにしか関心をもたないので「近視眼的」である。γが１に近づくにつれて、目標は将来の報酬をより強く考慮に入れることになり、エージェントはより長期的な視野をもつことになる。
【００２３】
たいていのＲＬアルゴリズムが基礎としているのは価値関数――状態（または状態−行動の対）の関数であり、ある所与の状態にいること（またはある所与の状態においてある所与の行動を実行に移すこと）がエージェント１００にとってどの程度よいことであるかを見積もる指標――を推測することである。「どの程度よいことであるか」の考えは、期待される将来の報酬から、すなわち期待される利得から定義される。エージェントが将来受け取ると期待できる報酬は、どのような行動をとるかに依存する。よって、価値関数は特定の政策に関連して定義される。
【００２４】
政策πとは、各状態ｓ∈Ｓおよび行動ａ∈Ａ（ｓ）から状態ｓにあるときに行動ａをとる確率π（ｓ，ａ）へのマッピングであったことを想起されたい。略式な言い方をすれば、政策πのもとでの状態ｓの価値Ｖπ（ｓ）は、状態ｓから出発してその後政策πに従ったときに期待される利得
Ｖπ（ｓ）＝Ｅπ｛Ｒt｜ｓt＝ｓ｝＝Ｅπ｛Σγkｒt+k+1｜ｓt＝ｓ｝      （３）
〔和はk＝0から∞まで〕
である。同様に、政策πのもとで状態ｓにおいて行動ａをとることの価値Ｑπ（ｓ；ａ）は、ｓから出発して行動ａをとり、その後政策πに従ったときに期待される利得
Ｑπ（ｓ；ａ）＝Ｅπ｛Ｒt｜ｓt＝ｓ，ａt＝ａ｝＝Ｅπ｛Σγkｒt+k+1｜ｓt＝ｓ，ａt＝ａ｝      （４）
〔和はk＝0から∞まで〕
である。Ｑπは政策πについての行動価値関数と呼ばれる。
【００２５】
ある時間段階において状態ｓが与えられたときに行動を選択する一つの方法は、貪欲にふるまう、すなわちＱ（ｓ；ａ）が極大となる行動ａを選択することである。この方法は、直近の報酬を最大化するために現在の知識を利用するが、一見劣った行動が実はよりよい選択ではないかどうかを見極める冒険には全く時間を割かない。単純な代替案は、ほとんどの時点では貪欲にふるまうが、たまに、たとえば確率εで、行動価値推定値には関わりなく、全選択肢から一様に無作為に行動を選択するというものである。この、貪欲に近い行動選択則を使う方法は、ε貪欲法と呼ばれる。
【００２６】
Ｓａｒｓａは時間差分（TD：Temporal  Difference）学習法である。ＴＤ学習法は、環境のダイナミクスのモデルなしに生の経験から直接学習でき、最終結果を待つことなく、他の学習された推定値の一部に基づいて推定値を更新する（ブートストラップ式である）。Ｓａｒｓａでは行動価値の更新規則は
Ｑ（ｓt；ａt）←Ｑ（ｓt；ａt）＋α［ｒt+1＋γ・Ｑ（ｓt+1；ａt+1）−Ｑ（ｓt；ａt）］  （５）
で与えられる。ここで、ｓtは時間段階ｔにおける状態、ａtは時間段階ｔにおいてとられる行動、ｒt+1は次の時間段階ｔ＋１に受け取る報酬、ｓt+1は次の時間ステップにおける状態、ａt+1はとるべき対応する行動、←は左辺値の右辺値による更新を表す。この更新は状態ｓtからの遷移のたびに実行される。この規則は、ある状態−行動対から次の状態−行動対への遷移を構成する五つ組（ｓt，ａt，ｒt+1，ｓt+1，ａt+1）のすべての要素を使う。この五つ組がこのアルゴリズムの名称Ｓａｒｓａの由来となっている。
【００２７】
下記に継続タスクの場合のＳａｒｓａ更新規則に基づく学習アルゴリズムを掲げる。
ＳＡＲＳＡアルゴリズム
ａ．すべてのＱ（ｓ；ａ）を任意に初期化
ｂ．ｓを初期化
ｃ．Ｑ（ｓ；ａ）が極大となる行動ａを選択（ε貪欲）
ｄ．繰り返し
ｅ．行動ａを実行
ｆ．次の時間段階で、結果として得られる報酬ｒ′および新しい状態ｓ′を観測
ｇ．Ｑ（ｓ′；ａ′）が極大となる行動ａ′を選択（ε貪欲）
ｈ．Ｑ（ｓ；ａ）←Ｑ（ｓ；ａ）＋α・（ｒ′＋γ・Ｑ（ｓ′；ａ′）−Ｑ（ｓ；ａ））
ｉ．ｓ←ｓ′、ａ←ａ′
セットトップボックスやデジタルテレビのような消費者端末は、現在は専用ハードウェアコンポーネントを使ってビデオを処理している。近い将来にはプログラム可能なハードウェアにソフトウェア的なビデオ処理を搭載したものが取って代わる見込みである。このいわゆるソフトウェアビデオ処理の特徴の一部として、変動の激しい、データに依存するリソース要求がある。
【００２８】
ビデオ処理に関しては、通例最悪ケースと平均ケースの復号期間の間にギャップがある。さらに、短期的（すなわち統計的）負荷変動と長期的（すなわち構造的）負荷変動の区別がある。構造的負荷変動は、なかんづく、ビデオシーンの複雑性が変動することによって引き起こされる。最悪ケースに基づくリソース割り当ては、通例、コスト圧力が高く容認しにくいため、リソース割り当ては好ましくは平均ケースに近いものとなる。過負荷を避けるために、何らかの形の負荷軽減が欠かせない。
【００２９】
変動のある負荷について時折の期限遅れを容認するなどのソフトなタイミング要求だとか平均的な意味での反応時間要求といったものは、サービスの品質（QoS：Quality  of  Service）すなわち「サービスのユーザーによる満足度を決定するサービスパフォーマンスの集団的効果」の特殊な場合と見なすことができる（ＩＴＵ−Ｔ勧告Ｅ．８００，Ｇｅｎｅｖａ  １９９４参照）。ＱｏＳの抽象化は、不均一なソフトタイミング要求および単一システム内での近似計算やジョブ間引きのような不均一な適応的機能を用いてタスクについて判断し、対処する手段を提供する。
【００３０】
時間的保護のあるリソース予約は、ソフトリアルタイムシステムについての過負荷管理の問題を複数の下位問題に分解し、別個に対処することを可能にする。この方法では、過負荷管理および意味的（すなわち価値に基づいた）意思決定はスケジューラの外に出すことができる。取り組むべき課題としては二つが残る。どのタスクにどの予算枠を割り当てるかを決定すること、そして各タスクの負荷を割り当てられた予算枠に応じて調整することである。第一の課題はグローバルで、統一的なＱｏＳ尺度を必要とする。第二の課題はローカルで、タスク固有のＱｏＳ適応を使うことができる。
【００３１】
ここでは、高品質ビデオ処理のコンテキストにおける、ローカルなＱｏＳ制御、すなわち割り当てられた予算枠の範囲内でローカルなＱｏＳを最適化しようとすることに関心がある。ビデオ処理タスクはスケーラブルである、すなわち、リソース使用との兼ね合いでの画質の調整を個々のフレームレベルで行えることが想定されている。また、タスクは先行して作業する、すなわち直前のフレーム完了後、次のフレームのデータさえあればすぐその処理を開始できることが想定されている。スケーラブルなビデオアルゴリズムは、各フレームに対して選択できるＱｏＳレベルの数を制限する。先行作業を適用する度合いは、遅延とバッファの制約によって決定される。高品質ビデオのＱｏＳは、バランスをとるべき三つの要素を併せ持っている。処理品質、期限遅れ、品質変化である。
【００３２】
バランス制御戦略は二つの種類の負荷変動に関係している――短期（統計的）と長期である。短期的負荷変動を制御するためには、制御問題はマルコフ決定過程としてモデル化される。これは、離散的な統計的決定問題のための一般的なアプローチである（Markov  Decision  Processes:  discrete  stochastic  dynamic  programmming,  Wiley  Series  in  Probability  and  Mathematical  Statistics,  Wiley-Interscience,  New  York,  1994,  M.L.Puterman参照）。構造的負荷変動を扱うためには、予算枠スケーリングが用いられる。現在の構造的負荷に反比例する予算枠に対する元来の静的または動的解を適用するのである。
【００３３】
図２は、基本的なスケーラブルなビデオ処理タスクを表している。単一の、非同期の、スケーラブルなビデオ処理タスク２００を、付随するコントローラ２０２とともに考える。ビデオ処理タスク２００はフレームを離散的ないくつかの数（おそらくは小さい数）の品質レベルにおいて処理することができる。ビデオ処理タスク２００は処理すべきフレームを入力待ち行列２０４から取得し、処理されたフレームを出力待ち行列２１０に与える。便宜上、一連のフレームは１、２…と番号が振られているものとする。入力プロセス２０４（たとえばデジタルビデオチューナー）は周期的にフレームを入力待ち行列に入れ、その周期をＰとする。出力プロセス２０６（たとえばビデオレンダラー）は出力待ち行列にあるフレームを同じ周期Ｐで消費する。ここで、入力フレームレートと出力フレームレートは同じであると想定しているが、異なっていてもよい。入力プロセス２０４および出力プロセス２０６は一定の遅延δで同期している。すなわち、フレームｉが入力待ち行列２０８に時刻ｅi＝ｅ0＋ｉ・Ｐではいったとすると（ｅ0はオフセット）、そのフレームは時刻ｅi＋δに出力２１０から取り出されて消費される。あるフレームを処理する前に、コントローラ２０２はそのフレームを処理する品質レベルを選択する。フレームの処理時間は選択された品質レベルとフレームのデータの複雑さの両方に依存する。平均的には、タスクは周期Ｐごとに１フレームを処理する必要がある。Ｐより大きな遅延δを選ぶことによって、タスクは、先行作業によって変動負荷をならす若干の余地を与えられる。
【００３４】
時刻ｅiに入力待ち行列にはいるフレームｉを考える。明らかに、ｅiはそのフレームを処理する最も早い開始時刻であり、ｄi＝ｅi＋δは可能な最も遅い完了時刻、すなわち期限である。便宜上、仮想期限ｄ0＝ｅ0＋δが定義される。フレームｉの実際の開始時刻、すなわちこのタスクでｉ番目の開始（start）点をｓiとする。フレームｉの実際の完了時刻、すなわちこのタスクでｉ番目の到達目印点（milestone）をｍiとする。フレームの処理時間が０でなければ、ｍi＞ｅiが成立する。もしもｍi＞ｄiであればタスクはフレームｉの期限に遅れたことになる。ｍi−1＜ｅiであれば、ｉ＞１と想定して、タスクはｍi−1からｅiまで中断する。ｉ＞１についてｓi≧ｍａｘ｛ｍi−1，ｅi｝である。
【００３５】
期限に遅れたとしてもフレームがアボートされることはなく、とにかく完了されるという作業保存の原則を想定しているが、他の原則を採用してもよい。今の場合、期限に遅れたフレームは次の期限に対して使用される。このフレームが完了するまでにさらにその後のフレームの期限さえも過ぎてしまうこともあることを指摘しておく。期限に遅れた場合、次の動作が必要になる。第一に、出力プロセスが誤り隠蔽を実行する必要がある。たとえば、ビデオレンダラーが直前に表示されたフレームを再利用するなどである。そのような誤り隠蔽は、特に動きの多いシーンの場合、知覚される品質を低下させることがある。第二に、コントローラは、フレーム番号と期限との間の対応を回復し、入力待ち行列に滞貨がたまることを回避するため、その後のフレームを間引いてエラーからの回復を実行する。スキップするフレームは慎重に選ぶ必要がある。たとえば、ＭＰＥＧ復号の場合、Ｂフレームは安全にスキップできるが、Ｉフレームをスキップするとストリームが停滞してしまう。
【００３６】
図３および図４は、Ｐ＝１、δ＝２、ｓ1＝ｄ0＝０とした場合の二つの時系列の例によってタスクの処理の進行を図解したものである。タスクが処理する必要のあるフレームは５つである。実際に処理されたフレームは図３では参照符号３０１、３０２、３０４、３０５によって、図４では参照符号４０１、４０２、４０３、４０４、４０５によって示されている。図３では期限ｄ2を逃している。コントローラはこの期限遅れに、期限ｄ3に対してフレーム３０２を使い、フレーム３０３をスキップすることによって対処している。図４ではタスクは到達目印点ｍ3で、フレーム４０４が入力待ち行列にないため（ｅ4＝ｄ4）中断している。
【００３７】
ｄ0に始まって、二つの連続した期限にはさまれた期間の間でタスクにはある保証された処理時間の予算枠（budget）ｂ（０≦ｂ≦Ｐ）が割り当てられる。この保証予算枠に基づいて、前倒し量（progress）と呼ばれる尺度が導入される。前倒し量ρiは、開始点ｓiにおいて計算されるもので、ｄi−1までに残されている保証予算枠の総量をｂで割ったものである。この前倒し量は、直前のフレームｉ−１の処理が完了したあと、その予算枠がどのくらい残っているかを示す。前倒し量はコントローラにとって重要な尺度である。というのも、前倒し量が大きければ、これから処理しようとしているフレームについて期限に間に合わない危険が低下するからである。前倒し量は常に非負である。このことは、期限遅れの場合には、完了したフレームをそれよりあとの期限において使うことによって保証される。さらに、待ち行列の大きさにも制限があるので、前倒し量にもρmax＝δ−１という上限がある。ある開始点における前倒し量とは、ちょうど完了したフレームの期限に基づいて計算されることを注意しておく。前倒し量を到達目印点において計算しない理由は、そうでないと中断のため予算枠が無駄になることが前倒し量に織り込めないからである。中断の場合、最初の次の開始点においてコントローラによって使われる前倒し量は大きすぎてしまう（＞ρmax）。
【００３８】
図３および図４では、ｂ＝Ｐと想定されている。これはすなわち、そのタスクがプロセッサを専有しているということである。図３では、一連の開始点における前倒し量は、それぞれρ1＝０、ρ2=０．２５、ρ4＝１、ρ5＝０．５で与えられ、図４ではそれぞれρ1＝０、ρ2=０．５、ρ3＝１、ρ4＝１、ρ5＝０．５で与えられる。
【００３９】
図５および図６はｂ＝Ｐ／２とした場合の二つの時系列の例を示している。タスクが処理する必要のあるフレームは５つである。実際に処理されたフレームは図５では参照符号５０１、５０２、５０４、５０５によって、図６では参照符号６０１、６０２、６０３、６０４、６０５によって示されている。ここでもＰ＝１、δ＝２、ｄ0＝０と想定されている。さらに、ｓlはタスクに初めて予算枠が割り当てられる時点であると想定する。図５では、一連の開始点における前倒し量は、それぞれρ1＝０、ρ2=０．２５、ρ4＝０．７５、ρ5＝０．５で与えられ、図６ではそれぞれρ1＝０、ρ2=０．５、ρ3＝０．７５、ρ4＝１、ρ5＝０．５で与えられる。予算枠は背後にあるスケジューラの決定に従って各期間ごとに異なった時間区間に分配されていることに注意しておく。図６では、ｍ3においてタスクはその期間についての予算枠の半分を消費している。予算枠の残りの半分は中断のため無駄になっている。
【００４０】
前述したように、各開始点においてコントローラは処理にかかるフレームの品質レベルを選択しなければならない。好ましくは、次の三つの目的を満たす最適バランスを見出すような制御戦略が選択される。
・期限遅れと付随するフレーム間引きがあると出力に乱れが生じるので、期限遅れはできるだけ少なくするべきである。期限遅れを防止するため、フレームを品質レベルを下げて処理する必要がある場合もある。
・高品質の出力を得るため、フレームはできるだけ高い品質レベルで処理するべきである。
・品質レベルの変更の数や大きさはできるだけ小さくするべきである。品質レベルの（より大きな）変更は（より）知覚できる乱れを生じうるからである。
【００４１】
最適バランスを見出すために、処理される各フレームに数値的な報酬が割り当てられる。報酬を構成する要素として、フレーム処理中に間に合わなかった期限の数に対して科される（おそらくは高い）ペナルティ、ある特定の品質レベルでフレームを処理したことに対する報償、直前のフレームに使われたのと異なる品質レベルでフレームを処理したことに対するペナルティ、がある。一連のフレームに対して平均的な報酬を最大化するいかなる制御戦略も前記した三つの目的をバランスするものと言える。さらに、前記平均的な報酬はそのタスクに対する調整可能なＱｏＳ指標を提供する。
【００４２】
各品質レベルに対して各フレームの処理時間が前もってわかっていれば、平均的な報酬を最大化する制御戦略を見出すことは計算できる。その場合、最適品質レベルは動的計画法を用いてオフラインで計算できる（Dynamic  Programming,  Princeton  University  Press,  Princeton,  NJ,  1957  R.E.Bellman）。
【００４３】
ランタイムの制御戦略へ向けた第一歩として、システムはマルコフ決定過程（MDP：Markov  Decision  Process）としてモデル化される。ＭＤＰにおいては、いくつかの状態の集合、その各状態に対していくつかの行動の集合を考える。離散的な時点（制御点）において、コントローラは系の現在の状態ｓを観測し、次いである行動ａをとる。この行動が系に影響を与え、その結果、コントローラは次の離散的時点において新しい状態ｓ′を観測する。この新しい状態は、行動と直前の状態によって決定論的に決定されるのではなく、各組み合わせ（ｓ，ａ，ｓ′）が既知の固定的な確率をもつ。数値的な報酬は各状態遷移（ｓ，ｓ′）に関連付けられている。ＭＤＰの目標は、系の寿命の間を通じた全状態遷移にわたっての平均的な報酬を最大化する決定戦略を見出すことである。
【００４４】
ここで、コントローラが系を観測する離散的な時点が前記開始点ｓiである。状態は、その開始点におけるタスクの前倒し量ρiを含む。品質レベルの変更にペナルティが科されるので、状態は直前のフレームに使われた品質レベルも含んでいる（直前の品質レベルｑi−1）。よって、ｓi＝（ρi，ｑi−1）である。最後に、行動とはある品質レベルｑiを選択することであり、各状態変化に対する報酬は上記の記述に従って定義される。
【００４５】
ＭＤＰ戦略と称される第一の戦略では、ＭＤＰはオフラインで解かれる。これは、状態遷移確率Ｐｒ（ｓ，ａ，ｓ′）が前もって必要とされるということを含意する。よって、フレームごとの処理時間がいくつかの代表的なビデオシーケンスについてさまざまな品質レベルで測定され、それらのシーケンスを使って状態遷移確率が計算される。次いでＭＤＰが予算枠ｂの特定の値についてオフラインで解かれる。この結果として（静的な）マルコフ政策が状態−行動の対（ρi，ｑi−1；ｑi）として得られる。ランタイムの間、各開始点において、コントローラはマルコフ政策を単純な探索表として参照してその行動を決定する。
【００４６】
ＭＤＰはまた、前述した強化学習（ＲＬ）によってランタイムで解くこともできる。ＲＬ制御戦略は予備知識なしで開始され、ランタイムの間に得られる経験から最適なふるまいを学習する。状態−行動価値が開始点において品質レベルを選ぶのに適用される。状態が与えられたとき、状態−行動価値を最大にする品質レベル（＝行動）が選択される。このアプローチはＲＬ制御戦略と称される。
【００４７】
先に述べたように、負荷変動には短期的なものと構造的なものがある。構造的な負荷値の間の急激な遷移は全く例外的なものである。一般に、遷移はずっとなめらかである。
【００４８】
ＭＤＰおよびＲＬ制御戦略は、一連のフレームの処理時間が互いに独立であることを暗に想定している。これは短期的な負荷変動についてはほぼあてはまるが、構造的な負荷変動についてはあてはまらない。構造的な負荷変動をも扱うために、ＭＤＰおよびＲＬ戦略に次の改良を適用することができる。
・ランタイムの間、短期的負荷変動をならして構造的負荷を追跡し、それを参照予算枠と比較する。
・この参照予算枠に対する構造的な負荷変動に関して元来のＭＤＰ戦略およびＲＬ戦略を補正する。ただし、割り当てられた予算枠を調整するのではなく、反比例予算（スケーリングされた予算ともいう）に対して導出された政策を適用することによって行う。
これらの改良をした戦略はそれぞれＭＤＰ*およびＲＬ*と記される。
【００４９】
開始点において構造的負荷を追跡するため、ちょうど完了したフレームについての実際の処理時間（actual  processing  time）ａｐｔとフレームについての適用される品質レベルにおいて期待される処理時間（expected  processing  time）ｅｐｔとの比、すなわちｃｆ＝ａｐｔ／ｅｐｔを決定する必要がある。期待される処理時間は各品質レベルごとにオフラインで導出済みである。前記の比のことを複雑化因子（complication  factor）ｃｆと称する。
【００５０】
この複雑化因子は適用される品質レベルにはあまり依存しないものとする。フレームが異なる品質レベルで処理されたとしても、複雑化因子はほぼ同じになるというのである。こうした想定が必要になるのは、完了したフレームを処理した品質レベルについて処理時間を測定できても、その品質レベルは必ずしもその後のフレームに選択される品質レベルとなるとは限らないからである。
【００５１】
複雑化因子は短期的負荷変動と構造的負荷変動の両方を反映している。構造的負荷に対するより適切な尺度を得るため、短期的負荷変動は好ましくはフィルタにより除去されて継続複雑化因子（running  complication  factor）ｒｃｆを得る。この目的のためのフィルタとしては、ＦＩＲ、ＩＩＲ、メジアンフィルタなどいくつか好適なものがある（Digital  Signal  Processing,  Prentice-Hall,  Englewood  Cliffs,  NJ,  1975,  A.V.Oppenheim  and  R.W.Schafer参照）。たとえば、指数関数的に最近のものほど重みを重くする平均でステップサイズパラメータを０．０５としたＩＩＲフィルタを適用することが可能である。
【００５２】
継続複雑化因子ｒｃｆはスケーリングされた予算枠の基本となる。ｒｃｆが１から外れれば、見かけ上、タスクに利用できる処理予算枠が利用可能な予算枠ｂから外れたような効果となる。ｒｃｆ＝１．２であれば、ｂ＝３０ｍｓの予算枠はたったの２５ｍｓの予算枠のように見える。ｒｃｆ＝０．８であれば、同じ予算枠が３７．５ｍｓの予算枠のように見える。このように、スケーリングされた予算枠はｂ／ｒｃｆとして定義される。ランタイムの間、このスケーリングされた予算枠が各開始点において計算される。
【００５３】
ＭＤＰ*戦略は次のようにしてＭＤＰ戦略を改善する。第一に、ＭＤＰを解くために必要な統計量が規格化される。これは、構造的負荷変動がならされることにあたる。こうして短期的な負荷変動が構造的な負荷変動から切り離される。オフライン段階においてＭＤＰは、選択されたスケーリングされた予算枠の集合に対して解かれ、その結果、マルコフ政策の集合が得られる。スケーリングされた予算枠それぞれに対して一つのマルコフ政策が得られるのである。次にランタイムにおいては、開始点において、スケーリングされた予算枠の実際の値に対応する政策から新しい品質レベルが採用される。要求された政策が集合内にない場合には、所望の値はマルコフ政策の空間における線形補間によって得られる。
【００５４】
図７は、マルコフ政策の空間内である特定の直前品質レベルｑ2に対する平面を示すものである。この平面で、スケーリングされた予算枠値２８．２ｍｓにおける垂直線は、スケーリングされた予算２８．２ｍｓに対するマルコフ政策（これはスケーリングされた予算枠２８．０ｍｓおよび２８．５ｍｓに対する政策の補間によって得られる）におけるｑ2列に対応する。
【００５５】
ＲＬ*アプローチにおいては、スケーリングされた予算枠はそのまま状態に追加される。すなわち、スケーリングされた予算枠が状態空間の第三の次元となるのである。開始点において、状態（＝スケーリングされた予算枠、前倒し量、直前品質レベル）が与えられて、最大の状態−行動価値を生じる品質レベル（＝行動）が好ましくは選択される。
【００５６】
ＲＬ*アプローチの範囲内において、図１との関連で先述したように、エージェント１００はコントローラであり、フレームが処理される品質レベルを選択する。環境１０２はスケーラブルなビデオ処理タスクによって与えられる。エージェントが環境と相互作用する離散的な時間段階は前記開始点である。開始点におけるタスクの状態は、スケーリングされた予算枠（scaled  budget）ｓｂ、前倒し量ρ、直前品質レベル（previous  quality  level）ｐｑの組み合わせによって定義される。行動はフレームの処理が行われる品質レベルｑの選択である。状態ｓ＝（ｓｂ，ρ，ｐｑ）および行動ｑに対して、エージェント１００は行動価値Ｑ（ｓ；ｑ）を追跡する。
【００５７】
あるフレームを処理したのち、処理すべき次のフレームの開始点において、エージェントはまずスケーリングされた予算枠を、完了したばかりのフレームの処理時間を使って更新する。スケーリングされた予算枠のこの更新された値は、開始点における状態の一部となる。次に、エージェントは完了したばかりのフレームの報酬を計算する。表記の都合上、完了したばかりのフレームは品質レベルｑで処理され、その前のフレームは品質レベルｐｑで処理されたとする。報酬は、前の開始点以来間に合わなかった期限の数に対する（高い）負のペナルティ、当該フレームが処理された品質レベルｑに対する正の報償、品質レベルをｐｑからｑに変更したことに対する負の品質変更ペナルティ（quality-change  penalty）ｑｃｐ（ｐｑ，ｑ）からなる。エージェントが環境から直接報酬を受け取るのではなく、環境によって提供される情報（期限遅れの回数、品質レベル）に基づいて報酬を計算していることを注意しておく。報酬を使って、エージェントはその行動価値を更新する（学習）。その後、更新された行動価値を使って次のフレーム、すなわち現在の開始点に対応するフレームを処理する品質レベルを選択する。
【００５８】
必要とされる計算の範囲内では、有限個の状態しか考慮できないが、スケーリングされた予算枠も前倒し量もどちらも連続変数である。これに対処するため、スケーリングされた予算枠値の有限集合ＳＢ＝｛ｓｂ1，…，ｓｂn｝および前倒し量値の有限集合Ｒ＝｛ρ１，…，ρm｝が定義される。そして、格子点に当たる状態ｓ、すなわちｓｂ∈ＳＢ，ρ∈Ｒに対する状態ｓ＝（ｓｂ，ρ，ｐｑ）についてのみ、行動価値Ｑ（ｓ；ｑ）の追跡が行われる。格子点上でない状態についての行動価値を近似するには、そのまわりの格子点上の状態の行動価値に対する線形補間が適用される。
【００５９】
図８は３つの品質レベルｑ0からｑ2についての状態空間の例を示している。この状態空間においては、スケーリングされた予算の点は１０ｍｓ、２０ｍｓ、３０ｍｓ、４０ｍｓであり、前倒し量の点は０．２５、０．７５、１．２５、１．７５である。スケーリングされた予算枠２５ｍｓ、前倒し量１、直前品質レベルｑ0に対する行動価値を近似するためには、図８に示すようにそのまわりの４つの格子点上の状態の行動価値に対して線形補間が適用される。
【００６０】
Ｓａｒｓａアルゴリズムの各反復工程において、通常は一つの行動価値が学習（更新）される。結果として、学習には長い時間がかかることがあり、冒険行動の必要もありうる（これはしばしば最適ではない）。本発明によれば、各反復工程において（各開始点において）、すべての格子点上の状態に対する行動価値が更新され、より高速に学習がなされる。さらに、もはや冒険行動の必要がない。これはすでに学習したことがよりよく利用されるということを意味する。開始点において、完了したばかりのフレームの処理時間（processing  time）ｐｔが決定される。このフレームはある特定の品質レベルｑで処理されたものである。そのフレームに対する異なる品質レベルでの処理時間を推定するために、オフラインで決定され、予算枠のスケーリングにも使われたｅｐｔ値（期待される処理時間）が用いられる。たとえば、品質レベルｑ2で処理されたフレームが処理時間２０ｍｓで、ｅｐｔ（ｑ0）＝１５ｍｓ、ｅｐｔ（ｑ2）＝２２ｍｓとすると、品質レベルｑ0に対して推定される処理時間は２０ｍｓ×ｅｐｔ（ｑ0）／ｅｐｔ（ｑ2）＝１３．６ｍｓとなる。推定された処理時間は今のフレームの処理をシミュレートするのに使われる。格子点上の状態ｓiから出発して特定の品質レベル行動ｑiをとり、品質レベルｑiに対して推定された処理時間を使うと、当該フレームを処理したのちに得られる（格子点上でない）状態ｓi+1、対応する貪欲な品質レベル行動ｑi+1および結果として得られる報酬ｒi+1が計算できる。この計算においては、まず予算枠スケーリング（規格化ステップ）について処理時間が補正される。この情報を使って、Ｓａｒｓａ更新規則が適用される。各開始点において、これは好ましくはすべての格子点上の状態およびすべての品質レベル行動に対して実行される。その結果、好ましくは無作為な（貪欲でない）行動を時折とる必要はなくなる。本発明は、下記のアルゴリズムによって実装できる。その際、ｓｂｐはスケーリングされた予算枠が計算される点、すなわちスケーリングされた予算枠点（scaled  budget  point）、ｒｐｐは相対前倒し量が計算される点、すなわち相対前倒し量点（relative  progress  point）、ｐｑは直前の品質（previous  quality）を表す。
アルゴリズム：初期化
１ａ．継続複雑化因子を初期化
ｒｃｆ←１
１ｂ．全状態（ｓｂｐ，ｒｐｐ，ｐｑ）について
１ｃ．全品質行動ｑについて
１ｄ．（状態，行動）価値を初期化
Ｑ（ｓｂｐ，ｒｐ，ｐｑ；ｑ）←０
アルゴリズム：決定品質を取得
入力：相対前倒し量ｒｐ
入力：直前に使われた品質ｐｑ
出力：決定品質（decision  quality）ｄｑ
２ａ．スケーリングされた予算枠を計算
ｓｂ←ｂ／ｒｃｆ
２ｂ．スケーリングされた予算枠ｓｂ、相対前倒し量ｒｐ、直前の品質ｐｑについて、
補間された（状態、行動）価値Ｑivec（ｓｂ，ｒｐ，ｐｑ；ｑ）を可能なすべての品質行動ｑについて計算
２ｃ． Ｑivec（ｓｂ，ｒｐ，ｐｑ；ｑ）の最大値に対応する品質行動ｑを決定品質ｄｑとする
アルゴリズム：（状態，行動）価値を更新
入力：処理時間ｐｔ
入力：処理品質ｑ
３ａ．直前の作業単位の処理前の状況に対応する継続複雑化因子のコピーを作成
ｏｌｄｒｃｆ←ｒｃｆ
３ｂ．ｐｔとｑを使って継続複雑化因子を更新
ｒｃｆ←ｒｃｆ＋α［（ｐｔ／ａｖｇ（ｑ））−ｒｃｆ］
３ｃ．スケーリングされた予算枠を計算
ｓｂ←ｓｂ／ｒｃｆ
３ｄ．全状態（ｓｂｐ，ｒｐｐ、ｐｑ）について
３ｅ．全品質行動ｑ〔原文は「チルダ付きｑ」だが、訳文では表記の都合上「下線付きｑ」で示している〕について
３ｆ．  品質ｑに対する直前の作業単位の処理時間を推定
ｅｐｔ←［ａｖｇ（ｑ）／ａｖｇ（ｑ）］ｐｔ
３ｇ．  品質ｑで直前の作業単位の処理時間をシミュレート
状態（ｓｂｐ，ｒｐｐ，ｐｑ）から始まり、規格化された処理時間ｅｐｔ／ｏｌｄｒｃｆをもつ
３ｈ．  結果として得られる報酬ｒｅｖならびに結果として得られる相対前倒し値ｒｐを観測
３ｉ．  スケーリングされた予算枠（３ｃで導出済み）、相対前倒し値ｒｐ、前回の品質ｑに対して、可能な全品質行動ｑ′について、補間された（状態、行動）価値Ｑivec（ｓｂ，ｒｐ，ｑ；ｑ′）を計算
３ｊ．  Ｑivec（ｓｂ，ｒｐ，ｑ；ｑ′）の最大値をＱ′とする
３ｋ．  ｒｅｖおよびＱ′を使って（状態、行動）価値Ｑ（ｓｂｐ，ｒｐｐ，ｐｑ；ｑ）を更新
Ｑ（ｓｂ，ｒｐｐ，ｐｑ；ｑ′）＝Ｑ（ｓｂ，ｒｐｐ，ｐｑ；ｑ′）＋β（ｒｅｖ＋γＱ′−Ｑ（ｓｂｐ，ｒｐｐ，ｐｑ；ｑ））
計算における状態数を減らすため、次の技術を適用してもよい。ｓx＝（ｓｂ，ρ，ｐｑx）およびｓy＝（ｓｂ，ρ，ｐｑy）を、前回の品質レベルそれぞれｐｑxおよびｐｑyにおいてのみ異なる格子点上の状態とする。あるフレームについての処理時間は、前のフレームに適用された品質レベルには依存しないことから、開始点で、状態ｓxおよびｓyにおいて品質レベルｑが選ばれた場合、結果として次の開始点で得られる状態は同一である。行動価値使って表すと、これはＱ（ｓx；ｑ）−ｑｃｐ（ｐｑx，ｑ）＝Ｑ（ｓy；ｑ）−ｑｃｐ（ｐｑy，ｑ）ということを意味する。この観察は次のようにして計算における状態数を減らすのに用いることができる。行動価値を学習するため、二次元の格子点上の状態、すなわち、集合ＳＢからのスケーリングされた予算枠および集合Ｒからの前倒し値のすべての組み合わせが使われる。三次元の格子点上の状態（ｓｂ，ρ，ｐｑ）において品質レベルｑを選ぶことに対する行動価値Ｑ′（（ｓｂ，ρ，ｐｑ）；ｑ）を得るためには、学習された行動価値Ｑ′（（ｓｂ，ρ）；ｑ）に対してペナルティｑｃｐ（ｐｑ；ｑ）が加算される。言い換えれば、Ｑ′（（ｓｂ，ρ，ｐｑ）；ｑ）＝Ｑ′（（ｓｂ，ρ）；ｑ）＋ｑｃｐ（ｐｑ；ｑ）である。そして行動価値Ｑ′は学習される。このようにして、更新すべき状態数は因子｜Ｑ｜だけ減少する。ここで、Ｑは品質レベルの集合である。
【００６１】
本発明の方法の記載された実施形態の順序は必須ではない。当業者であればステップの順番を変更したり、スレッディングモデルやマルチプロセッサシステム、多重プロセスを使って同時に実行したりすることが、本発明の意図する概念から乖離することなく可能であろう。
【００６２】
図９は、本発明に基づくシステムを概略的に示した図である。システム９００はマイクロプロセッサ９１４、ソフトウェアバス９１２、メモリ９１６を有している。メモリ９１６はランダムアクセスメモリ（RAM：random  access  memory）でありうる。メモリ９１６はソフトウェアバス９１２を通じてマイクロプロセッサ９１４と通信している。メモリ９１６はコンピュータ可読コード９０２、９０４、９０６、９０８、９１０、９１１を有している。コンピュータ可読コード９０２は、次のメディアフレームについて、複数の出力品質のうちから出力品質を与えることができるよう設計されている。コンピュータ可読コード９０４は、前回のメディアフレームの処理時間および出力品質を次のメディアフレームの出力品質を決定するために使う自己学習制御戦略に基づいて次のメディアフレームの出力品質を設定するよう設計されている。コンピュータ可読コード９０６は前回のメディアフレームを処理するよう設計されている。コンピュータ可読コード９０８は、処理済の前回のメディアフレームの相対前倒し値、処理済の前回のメディアフレームのスケーリングされた予算枠値、処理済の前回のメディアフレームの出力品質を有する状態を決定するよう設計されている。コンピュータ可読コード９１０は次のメディアフレームの状態およびある可能な出力品質に基づいて報酬を決定するよう設計されている。コンピュータ可読コード９１１は、処理済の前回のメディアフレームの出力品質においてのみ異なる状態を軽減することによって報酬が決定される状態の数を減らすよう設計されている。当該システムはテレビの内部に含まれることもできる。さらに、コンピュータ可読コードはＣＤまたはＤＶＤのようなコンピュータ可読媒体から読み込むこともできる。
【００６３】
上述した実施形態は本発明を解説するためのものであって、限定するものではなく、当業者であれば付属の請求項の範囲から逸脱することなく数多くの代替実施形態を設計することができるであろうことに注意しておくべきである。請求項において、括弧内に参照符号があったとしてもそれが請求項を限定するものと解釈してはならない。「有する」の語は請求項中に挙げられている要素やステップ以外の存在を排除するものではない。単数形の要素の表現は、そのような要素が複数存在することを排除するものではない。本発明は、いくつかの異なる要素を有するハードウェアによって実装することもできるし、好適にプログラミングされたコンピュータによって実装することもできる。いくつかの手段を列挙しているシステム請求項において、それらの手段のいくつかが同一のコンピュータ可読ソフトウェアまたはハードウェアによって実施されることもできる。単にある種の方策が互いに異なる従属請求項において述べられているという事実をもってしてそれらの方策の組み合わせが有利に用いることができないということを示すものではない。
【図面の簡単な説明】
【００６４】
【図１】強化学習におけるエージェント−環境相互作用を示す図である。
【図２】基本的なスケーラブルなビデオ処理タスクを示す図である。
【図３】例としての時系列によってタスクの処理の挙動を示す図である。
【図４】さらなる例としての時系列によってタスクの処理の挙動を示す図である。
【図５】ｂ＝Ｐ／２に対する例としての時系列を示す図である。
【図６】ｂ＝Ｐ／２に対するさらなる例としての時系列を示す図である。
【図７】マルコフ政策の空間におけるある面を示す。
【図８】３段階の品質レベルの場合の例としての状態空間を示す図である。
【図９】本発明に基づくシステムの主要部分を概略的に示す図である。
【図１】
2006524461.tif 000003
【図２】
2006524461.tif 000004
【図３】
2006524461.tif 000005
【図４】
2006524461.tif 000006
【図５】
2006524461.tif 000007
【図６】
2006524461.tif 000008
【図７】
2006524461.tif 000009
【図８】
2006524461.tif 000010
【図９】
2006524461.tif 000011
【国際調査報告】
2006524461.tif 000012
2006524461.tif 000013