(57)【要約】歌のプレイリストのような複数のユーザ定義された制約に従って選択された複数のエレメントのターゲットシーケンスを自動的に生成する方法及び装置に関する。本装置は、複数のユーザ定義された制約を入力するユーザインタフェース１０２、複数のエレメント又はミュージックファイルを記憶するストレージデバイス１０６、ユーザ定義された制約に最良にフィットするソリューションシーケンスがそれぞれの繰り返しで発見される繰り返しプロセスによりターゲットシーケンス又はプレイリストを自動的に発生するプロセッサ１０４を有する。小さな、ランダム又はバイアスチェンジが発見されたシーケンスに行われ、これがソリューションを改善する場合、次の繰り返しについて新たなソリューションが使用される。バイアスチェンジは、通常は満足するのが困難なユーザ定義された制約について良好な結果を予測するのを助けるために使用される。
2009500670.tif 000002
【特許請求の範囲】
【請求項１】
複数のユーザ定義された制約に従って選択された複数のエレメントのターゲットシーケンスの生成の方法であって、
当該方法は、
（ａ）選択されたエレメントの第一のシーケンスを発生するステップと、
（ｂ）第一のシーケンスの選択されたエレメントが複数のユーザ定義された制約に一致するかに関して、第一のシーケンスのペナルティを評価するステップと、
（ｃ）第二のシーケンスを生成するため、第一のシーケンスの少なくとも１つのエレメントに対して変更をなすステップと、前記変更は、（ｉ）ランダムな変更、及び（ｉｉ）バイアスされた変更の少なくとも１つを含み、前記バイアスされた変更は、複数のユーザ定義された制約のうちの少なくとも１つのペナルティを低減し、
（ｄ）第二のシーケンスの選択されたエレメントが複数のユーザ定義された制約に一致するかに関して、第二のシーケンスのペナルティを評価するステップと、
（ｅ）前記ステップ（ｃ）でランダムな変更が行われた場合、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択され、前記ステップ（ｃ）でバイアスされた変更が行われた場合、第二のシーケンスがターゲットシーケンスとして選択されるか、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択されるステップと、
（ｆ）前記ステップ（ｃ）〜（ｅ）を繰り返し、前記ステップ（ｅ）で発見されたターゲットシーケンスは、少なくとも１つの繰り返しがバイアスされた変更をなすことを含むように、それぞれの繰り返しについて前記ステップ（ｃ）の第一のシーケンスを置き換えるステップと、
を含む方法。
【請求項２】
前記ステップ（ｆ）において、ターゲットシーケンスのペナルティが最小になるまで、前記ステップ（ｃ）〜（ｅ）が繰り返される、
請求項１記載の方法。
【請求項３】
前記ステップ（ｆ）おいて、前記ステップ（ｃ）〜（ｅ）は予め決定された回数で繰り返される、
請求項１記載の方法。
【請求項４】
バイアスされた変更は、ユーザ定義された制約の投票により決定される、
請求項１乃至３の何れか記載の方法。
【請求項５】
第一のシーケンスのうちの少なくとも１つのエレメントを変更するステップは、シーケンスにおける少なくとも１つのエレメントのポジションを変えるステップ、前記少なくとも１つのエレメントを新たなエレメントで置き換えるステップ、エレメントを削除するステップ、新たなエレメントを挿入するステップ、のうちの少なくとも１つを含む、
請求項１乃至４の何れか記載の方法。
【請求項６】
少なくとも１つのエレメントの新たなポジションは、複数のユーザ定義された制約の投票により選択される、
請求項５記載の方法。
【請求項７】
新たなエレメントは、複数のユーザ定義された制約の投票により選択される、
請求項５記載の方法。
【請求項８】
複数のユーザ定義された制約の予め決定されたサブセットは投票する、
請求項６又は７記載の方法。
【請求項９】
複数のユーザ定義された制約の予め決定されたサブセットは、ランダムな変更により満足することができないユーザ定義された制約のタイプを有する、
請求項８記載の方法。
【請求項１０】
複数のユーザ定義された制約は、ユーザ定義された制約のペナルティが重み付けされた制約に基づいて計算されるように、重み付けされる、
請求項１乃至９の何れか記載の方法。
【請求項１１】
エレメントはライブラリに記憶され、当該方法は、ライブラリから第一及び第二のシーケンスのそれぞれのエレメントを選択するステップを更に含む、
請求項１乃至１０の何れか記載の方法。
【請求項１２】
ライブラリから選択されたエレメントは、少なくとも１つのユーザ定義された制約により定義されるライブラリのサブセットから選択される、
請求項１１記載の方法。
【請求項１３】
第一のシーケンスのエレメントは、シードエレメントへの類似性に基づいて選択される、
請求項１乃至１１の何れか記載の方法。
【請求項１４】
ターゲットシーケンスは、少なくとも１つのユーザ定義された制約に従って予め決定された順序で配置されるエレメントのシーケンスを有する、
請求項１乃至１３の何れか記載の方法。
【請求項１５】
ターゲットシーケンスは音楽のプレイリストであり、エレメントは音楽ファイルである、
請求項１乃至１４の何れか記載の方法。
【請求項１６】
複数のユーザ定義された制約に従って選択された複数のエレメントのターゲットシーケンスを自動生成する装置であって、
当該装置は、
ターゲットシーケンスの複数の制約を入力し、前記制約を複数のユーザ定義された制約に変換するユーザインタフェースと、
複数のエレメントを記憶する記憶装置と、
ターゲットシーケンスを自動生成するプロセッサとを有し、
前記プロセッサは、
（ａ）選択されたエレメントの第一のシーケンスを発生し、
（ｂ）第一のシーケンスの選択されたエレメントが複数のユーザ定義された制約に一致するかに関して、第一のシーケンスのペナルティを評価し、
（ｃ）第二のシーケンスを生成するため第一のシーケンスの少なくとも１つのエレメントに対する変更をなし、前記変更は、（ｉ）ランダムな変更、及び（ｉｉ）バイアスされた変更の少なくとも１つを含み、バイアスされた変更は、複数のユーザ定義された制約のうちの少なくとも１つのペナルティを低減し、
（ｄ）第二のシーケンスの選択されたエレメントが複数のユーザ定義された制約に一致するかに関して、第二のシーケンスのペナルティを評価し、
（ｅ）前記ステップ（ｃ）でランダムな変更が行われる場合、第一及び第二のシーケンスのペナルティを比較し、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方をターゲットシーケンスとして選択し、前記ステップ（ｃ）でバイアスされた変更が行われた場合、第二のシーケンスがターゲットシーケンスとして選択するか、第一及び第二のシーケンスのペナルティを比較し、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択し、
（ｆ）前記ステップ（ｃ）〜（ｅ）を繰り返し、少なくとも１つの繰り返しがバイアスチェンジをなすことを含むように、前記ステップ（ｅ）で発見されたターゲットシーケンスが、それぞれの繰り返しについて前記ステップ（ｃ）の第一のシーケンスを置き換える、
ステップに従って動作する装置。
【請求項１７】
前記プロセッサは、ターゲットシーケンスのペナルティが最小になるまで、前記ステップ（ｃ）〜（ｅ）を繰り返す、
請求項１６記載の装置。
【請求項１８】
前記プロセッサは、前記ステップ（ｃ）〜（ｅ）を予め決定された回数だけ繰り返す、
請求項１６記載の装置。
【請求項１９】
前記プロセッサは、少なくとも１つのユーザ定義された制約により定義されるライブラリのサブセットからエレメントを選択する、
請求項１５乃至１８の何れか記載の装置。
【請求項２０】
請求項１乃至１５の何れか記載の方法を実行する複数のプログラムコード部分を有するコンピュータプログラム。
【請求項２１】
請求項１５乃至２０の何れか記載の装置を有する自動プレイリスト発生器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレメントのシーケンスの発生の方法に関する。より詳細には、限定するものではないが、本発明は、音楽ファイルのようなマルチメディアファイルのプレイリストの自動生成の方法に関する。
【背景技術】
【０００２】
多くの人々は、音楽のようなマルチメディアファイルをＭＰ３又はＷＭＡフォーマット等でそれらのコンピュータに記憶する。これらのファイルは、全体のコレクションから選択された順序で再生することができる。これらのマルチメディアファイルは、コンピュータ、ＤＶＤプレーヤ、カーステレオ、及び専用のＭＰ３プレーヤのような他のポータブルプレーヤで再生される場合がある。
【０００３】
典型的に、どのマルチメディアファイル（たとえば歌）をどのような順序で再生すべきかを定義するリストであるリストを作成することが望まれる。かかるリストは、１つ毎にプレイリストに手動的に歌を追加することで作成することができる。しかし、これは、特に、音楽ファイルのコレクションが広範囲にわたる場合には非常に面倒である。プレイリストを作成する非常にシンプルなやり方は、音楽コレクションの全体又は一部から歌をプレーヤにランダムに再生させることである。しかし、通常のプレイリストは、たとえばリラクゼーションの間又は自動車の運転の間に聞く等といった特定の目的で作成される。これらのケースでは、リスナは、変わることなしに、どのタイプの音楽が再生されるかを更に正確に特定可能であることを望む。したがって、音楽プレーヤがプレイリストを自動的に生成するか、リスナの特定の望みに従ってプレイリストの作成においてリスナを少なくとも支援することが望まれる。
【０００４】
幾つかの公知のタイプの自動プレイリスト生成器がある。１つの公知のシステムは、歌についてユーザの好みを学習し、その後、ユーザが楽しむとシステムが考える歌のセットを生成する。どの歌をユーザが望むかを判定することにおいて、２つの異なるアプローチが存在する。コンテンツに基づいた学習は、歌自身を見て、特にそれらの歌の属性を見て、それらの属性に従って類似する歌を整合させる。考えは、ユーザが特定の歌を好む場合、ユーザは、それに類似した歌を好む。これらのシステムについてユーザからの入力は、通常、１以上のシードソングから構成され、次いで、システムは、そのシードソングに類似した歌のセットを出力する。歌の順序は考慮されず、リストにおける歌がシードソングに類似すること以外の制約をユーザは特定することができないので、このシステムは非常に制限された使用を有する。
【０００５】
コラボレートフィルタリングは、特定のユーザに歌を整合させるために明示的な好みを利用するマルチユーザアプローチである。それぞれのユーザは、歌のセットについてそれらの好みを表現する。次いで、システムは、音楽における類似の好みを有するユーザを発見し、これらのユーザが好きであると示した歌を推薦することで、この好適な歌のセットを拡張するのを試みる。このシステムにより生成されたプレイリストは、歌の順序が考慮されないか、重要度の低い問題であると考えられるので実際にプレイセットされ、システムは、制限された使用を有する。
【０００６】
上記システムの主要な目的は、新たな音楽をユーザに導入することであり、これらシステムは、特定の状況について特定のプレイリストを作成することにおいて、ユーザ支援を提供しない。
【０００７】
別の公知の方法は、満足される必要があり、ネットワークで動作される必要があるユーザにより定義される制約に基づいてソリューションプレイリストを提供することである。ネットワークにおけるそれぞれのノードは、歌、コスト、及び満足される必要がある制約を表す重みを表す。目的は、最小のコストを有し、同時に制約された重みを有するソース及びシンク（プレイリストにおける最初と最後の歌、ダミーソングとなる）を接続する連続的な経路を発見することである。そのモデルでは、歌は、定義することができる属性及び制約を制限する、バイナリ値のベクトルとして表される。
【０００８】
別の公知のプレイリスト発生器は、ＣＳＰ（constraint  satisfaction  programming）方法を使用する。ＣＳＰは、制約された変数をプレイリストにおけるそれぞれの位置と関連付けし、それぞれの変数のドメインは音楽コレクションである。考えは、歌のシーケンスに対応する、それぞれの変数にドメインからの値を割り当てることである。しかし、プレイリストにおける歌の数がＣＳＰにおける変数を定義することで固定され、したがって、たとえば彼らが望むプレイリストの期間をユーザが定義するのを可能にしない。ソリューションをサーチするアルゴリズムは、ソリューションに導くか、又はソリューションを発見するのを失敗するまで、互いにそれぞれのドメインを減少することからなる。値がドメインから除かれるたびに、このドメインに作用する制約は、別のドメインに属する別の値禁止されたことを制約が含むかをチェックするために調査される。その場合、制約もまた除かれ、プロセスは再帰的に繰り返される（制約の伝播）。次いで、ドメインの減少は、選択によるか（値を変数に割り当てる）、又はある制約の満足のために必要とされる伝播の結果として生じる。失敗に応じて（ドメインは空になる）、アルゴリズムは、なされた最後の判定にバックトラックし、異なる判定をとり、再び試みる。ソリューションが存在しない場合、アルゴリズムは、１つのステップを更にバックトラックし、ソリューションがないか、又はソリューションを発見することを証明するまで、判定のスタックを下から上に調べる。したがって、ソリューションプレイリストは、歌をプレイリストに繰り返し追加し、プレイリストが完了されるかをテストすることで構築される。したがって、部分的なプレイリストのみがそれぞれの繰り返しで利用可能であり、これは、アルゴリズムが永続的に停止される場合に問題となる。したがって、このＣＳＰアルゴリズムは、複雑であり、結果として、制限されたスケーラビリティを有する。さらに、ＣＳＰアルゴリズムは、プレイリストの発生のために望まれる最適性の概念を組み込んでいない。
【０００９】
自動プレイリスト生成のための別の公知の技術は、ローカルサーチ方法である。この方法は、ランダムな歌のリストで開始し、（ｉ）歌の追加、（ｉｉ）歌の削除、（ｉｉｉ）歌の新たな歌での置き換え、及び（ｉｖ）プレイリストにおける２つの歌のスワッピング、のような小さな変化をなすことで、このプレイリストに応じて改善することを繰り返し試みる。これを達成するため、コストは、プレイリスト、プレイリストにより違反された（満足されない）多くの制約に関連され、違反が大きくなると、コストが高くなる。
【００１０】
ローカルリサーチは、繰り返しのプロセスであり、それぞれの繰り返しで、前及び現在の繰り返しの結果的なプレイリストが比較され、低いコストをもつ結果的に得られるプレイリストは、現在の繰り返しの結果となる。したがって、任意の時間で、完全なソリューションとなるプレイリストが存在し、これまで発見された最良のプレイリスト、すなわち最も遅い結果をリターンするために、任意の時間でアルゴリズムを停止することが可能である。アルゴリズムは、全ての可能なプレイリストを調べないが、ソリューションをプログレッシブにリファインし、結果的に、良好なスケーラビリティを有し、最適性を組み込む。
【００１１】
しかし、特定の制約が満足することが困難である場合、新たなソリューションをランダムに発生すること（小さなランダムな変化をなすこと）、及び違反が減少されたかをチェックすることは、現在のソリューションの拒否につながる可能性があり、サーチアルゴリズムは、殆ど進行せず、極端に低速になる。
【００１２】
オリジナルのソリューションをランダムに変化することで満足することが困難である制約の例は、現在のソリューションが２つの歌を有するとき、所定のアーティストの３つの歌を有することを望む制約である。ある歌を他の歌で置き換えることは、正しいアーティストである非常に低い可能性を有し、新たなソリューションは、このアーティストの３つの歌を有さない。
【発明の開示】
【課題を解決するための手段】
【００１３】
本発明は、高速、効果的かつ効率的なエレメントのシーケンスを発生する更に効果的な方法に関する。理想的に、本発明に係るエレメントのシーケンスを発生する方法及び装置は、全ての制約を満足するプレイリストが存在しないことを必要とする、コンフリクトする制約が存在する場合に、アルゴリズムが、できるだけ多くの制約を満足するプレイリストを発生するような最適化を有するものであり、ユーザがソリューションのシーケンスを検索し、シーケンスを変更することが可能なように、及びアルゴリズムが、効率、ターゲットシーケンスの品質、最小の遅延を改善するために新たなシーケンスの構築における前の繰り返しを使用可能であるようにインクリメンタルな計算を含むものであり、さらに、ターゲットシーケンスの長さ、エレメントがターゲットシーケンスについて選択されるソースエレメントの数、又はユーザ定義された制約の数における増加が、実行時間における指数関数的な増加とならないようにスケーラビリティを含むものである。
【００１４】
本発明の態様によれば、複数のユーザ定義された制約に従って選択された複数のエレメントのターゲットシーケンスの生成のための方法が提供され、当該方法は、（ａ）選択されたエレメントの第一のシーケンスを発生するステップ、（ｂ）第一のシーケンスの選択されたエレメントが複数のユーザ定義された制約に合致するかに関して、第一のシーケンスのペナルティを評価するステップ、（ｃ）第二のシーケンスを生成するため第一のシーケンスの少なくとも１つのエレメントに対する変更を行うステップ、この変更は、（ｉ）ランダムチェンジ、及び（ｉｉ）バイアスチェンジの少なくとも１つを含み、バイアスチェンジは、複数のユーザ定義された制約のうちの少なくとも１つのペナルティを低減し、（ｄ）第二のシーケンスの選択されたエレメントが複数のユーザ定義された制約に合致するかに関して、第二のシーケンスのペナルティを評価するステップ、（ｅ）ステップ（ｃ）でランダムチェンジが行われる場合、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択され、ステップ（ｃ）でバイアスチェンジが行われた場合、第二のシーケンスがターゲットシーケンスとして選択されるか、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択されるステップ、（ｆ）ステップ（ｃ）〜（ｅ）を繰り返し、ステップ（ｅ）で発見されたターゲットシーケンスは、少なくとも１つの繰り返しがバイアスチェンジをなすことを含むように、それぞれの繰り返しについてステップ（ｃ）の第一のシーケンスを置き換える。ステップ（ｅ）において、最も低いペナルティをもつシーケンスが選択されるが、シミュレートされたアニーリングは、極大値を脱出するために使用される場合がある。
【００１５】
本発明の第二の態様によれば、複数のユーザ定義された制約に従って選択された複数のエレメントのターゲットシーケンスを自動生成する装置が提供される。当該装置は、ターゲットシーケンスの複数の制約を入力し、制約を複数のユーザ定義された制約に変換するユーザインタフェース、複数のエレメントを記憶する記憶装置、以下のステップに従ってターゲットシーケンスを自動生成するプロセッサを有する。（ａ）選択されたエレメントの第一のシーケンスを発生するステップ、（ｂ）第一のシーケンスの選択されたエレメントが複数のユーザ定義された制約に合致するかに関して、第一のシーケンスのペナルティを評価するステップ、（ｃ）第二のシーケンスを生成するため第一のシーケンスの少なくとも１つのエレメントに対する変更を行うステップ、この変更は、（ｉ）ランダムチェンジ、及び（ｉｉ）バイアスチェンジの少なくとも１つを含み、バイアスチェンジは、複数のユーザ定義された制約のうちの少なくとも１つのペナルティを低減し、（ｄ）第二のシーケンスの選択されたエレメントが複数のユーザ定義された制約に合致するかに関して、第二のシーケンスのペナルティを評価するステップ、（ｅ）ステップ（ｃ）でランダムチェンジが行われる場合、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択され、ステップ（ｃ）でバイアスチェンジが行われた場合、第二のシーケンスがターゲットシーケンスとして選択されるか、第一及び第二のシーケンスのペナルティが比較され、前記ペナルティに依存して、第一及び第二のシーケンスのうちの一方がターゲットシーケンスとして選択されるステップ、（ｆ）ステップ（ｃ）〜（ｅ）を繰り返し、ステップ（ｅ）で発見されたターゲットシーケンスは、少なくとも１つの繰り返しがバイアスチェンジをなすことを含むように、それぞれの繰り返しについてステップ（ｃ）の第一のシーケンスを置き換える。
【００１６】
このように、上記態様に係る本発明の方法及び装置の繰り返しプロセスは、最適化、インクリメンタル計算及びスケーラビリティを提供する。バイアスされたチェンジは、ランダムチェンジにより満足することが困難なユーザ定義された制約のための繰り返しプロセスにより要される時間を減少するものであり、プロセスの待ち時間が改善される。
【００１７】
好ましくは、ターゲットシーケンスのペナルティが最小にされるか、予め決定された回数だけ繰り返されるまで、ステップ（ｃ）〜（ｅ）が繰り返される。
【００１８】
したがって、ランダムチェンジを行うことで満足されることが困難であるユーザ定義された制約について、本発明の好適な実施の形態の詳細な説明を参照して以下に説明される。バイアスチェンジのため、ソリューションのエレメントシーケンスは、ランダムチェンジを使用する場合に困難かつ時間がかかることがわかる。これを達成することができる１つの方法は、バイアスチェンジのユーザ定義された制約の投票の判定である。
【００１９】
第一のシーケンスの少なくとも１つのエレメントを変えることは、シーケンスにおける少なくとも１つのエレメントの位置を変えること、少なくとも１つのエレメントを新たなエレメントで置き換えること、エレメントを削除すること、新たなエレメントを挿入すること、のうちの少なくとも１つを含む。少なくとも１つのエレメントの新たな位置は、複数のユーザ定義された制約の投票により選択され、及び／又は新たなエレメントは、複数のユーザ定義された制約の投票により選択される場合がある。複数のユーザ定義された制約の予め決定されたサブジェクトのみが投票する場合がある。たとえば、ランダムチェンジ方法を使用して満足することが困難なユーザ定義された制約である。
【００２０】
ユーザ定義された制約は、重み付けされた制約に基づいてユーザ定義された制約のペナルティが計算されるように重み付けされる。
【００２１】
好ましくは、エレメントは、ライブラリに記憶され、第一及び第二のシーケンスについて選択されたそれぞれのエレメントは、ライブラリから選択される。ライブラリから選択されたエレメントは、少なくとも１つのユーザ定義された制約により定義されるライブラリのサブセットから選択される。
【００２２】
第一のシーケンスのエレメントは、シードエレメントに対する類似性に基づいて選択される場合がある。  
ターゲットシーケンスは、少なくとも１つのユーザ定義された制約に従って予め決定された順序で配置されるエレメントのシーケンスを有する。  
ターゲットシーケンスは、音楽プレイリスト及びエレメントミュージックファイルである場合がある。  
【発明を実施するための最良の形態】
【００２３】
本発明の更に完全な理解のため、添付図面と共に行われる以下の詳細な説明が参照される。  
本発明の好適な実施の形態は、図１を参照して以下に記載される。好適な実施の形態は、音楽プレイリストの生成を記載しているが、本発明はマルチメディアファイル等のようなエレメントのシーケンスの発生について利用することができることが理解される。
【００２４】
ユーザがどの歌をリストにおくべきかを表現したいとき、それぞれの歌のタイトル及びアーティストを与える。しかし、人々は、どの特定の歌を彼らは聞きたいかを常に知らない。これは、彼らが歌のタイトルを思い出せないか、彼らが所定の状況で聞きたい歌を明示的に表現することができないためである。かかるリスニングの状況は、たとえば、人物のムード（楽しい又は悲しい）、環境（リビングルームで一人座っているか、庭でパーティを行っている）、又はリスニング目的（リラックス又は扇動される）により決定される。したがって、より一般的なやり方でユーザの音楽の好みをユーザが表現するのを可能にするため、歌に関する多くの情報を有することが必要である。“Golden  Earring”による“Radar  Love”を聞きたいという代わりに、ユーザは、“fast  rock  song”を望むことを表現することができる。
【００２５】
以下の表１は、歌を説明する可能な属性の例を示す。
【００２６】
【表１】
2009500670.tif 000003
たとえば“ABBA”による“Dancing  Queen”には値が与えられる。それぞれの属性は、その属性の値がどのように比較されるか定義するタイプを有する。属性は、公称（nominal）、カテゴリ（categorical）、順序（ordinal）、数値（numerical）、又はこれらのタイプのセットである。歌のＩＤ、アーティスト、タイトル、及びアルバムは、公称の属性の例である。これらの属性は、等価（たとえば、これら２つの歌は同じアーティストによる）及びセットメンバーシップ（たとえば、その歌はオランダ人アーティストによる）の観点で定義される。幾つかのヒエラルキーは、カテゴリの属性の値に関して定義される。したがって、等価及びセットメンバーシップに加えて、このヒエラルキーは、値に関して“partial  order  relationship”を可能にする。ジャンル及びムードは、カテゴリの属性の例である。たとえば、ジャンル“Britpop”は、“Popular”のサブジャンルであり、“Britpop”に属する歌も“Popular”に属する。等価及びセットメンバーシップに加えて、公称の属性に関して、“total  order”は、順序の値に関して定義される。これは、順序が部分的であるカテゴリの属性と対照的である。全体の順序は、ある値が別の値よりも小さいことを表現するために使用される。たとえば、テンポマーキングについて、“slow”のマーキングを持つ歌は、“fast”のマーキングをもつ歌よりも低速である。数値のタイプは、値の間の差“difference”により順序のタイプを拡張する。リリースの年及び期間は、数値の属性の例である。たとえば、ユーザは、ある歌は別の歌よりも１０年古いことを特定することができる。
【００２７】
プレイリスト内の歌の順序も重要である。たとえば、ＤＪは、ある歌から他の歌へのスムーズな遷移をなすように、クラブでの再生のための歌を選択する。したがって、歌のテンポは、余りに異なるべきではない。プレイリストにおける歌の順序の重要性の別の態様は、バランスである。たとえば、同じアーティストによりプレイリストにおける多数の歌が存在する場合、よりバランスされたプレイリストは、これらの歌を次々と再生させない。代わりに、異なるアーティストにより一組の歌を含むことが望まれる場合がある。ユーザは、音楽における所定のプログレッションを示したい場合がある。たとえば、ユーザは、幾つかの低速の歌をもつシーケンスをスタートオフにし、テンポを増加したい場合がある。
【００２８】
さらに、ユーザは、歌の数又はプレイリストの全体の期間を分又は時間といった観点でプレイリストの長さを特定したい場合がある。たとえば、ユーザは、約１時間のプレイリストを望む場合があり、それは、どの位の長さでドライブが機能する要するかであるためである。別の可能性は、ポータブルＭＰ３プレーヤは、制限された記憶容量を有することである。そのケースでは、ユーザは、たとえば２５６ＭＢといったプレイリストが装置で占有する記憶量を示したい場合がある。
【００２９】
したがって、プレイリスト発生器が、できるだけフレキシブル及び使用可能となるように、異なるタイプのユーザの好み又は制約を含むことが望まれる。ユーザの好み又は制約は、ユーザ定義された制約として好適な実施の形態のシステムで形式化される。
【００３０】
図１で例示されるように、好適な実施の形態の自動プレイリスト生成システム１００は、アルゴリズムプロセッサ１０４及びストレージデバイス１０６に接続されるユーザインタフェース１０２を有する。
【００３１】
ユーザインタフェース１０２は、ストレージデバイス１０６からデータを検索し、それをディスプレイスクリーン等でユーザに表示する。ユーザは、ジャンル、アーティスト及びアルバムのような歌の属性によりソートされる、ストレージデバイス１０６に記憶されたファイル（音楽ファイル）を通してブラウジングする。このように、特定の歌又は特定の属性は、容易に見つけることができる。これらの属性は、プレイリストの発生のための制約を特定するために使用される。たとえば、ユーザは、特定のアーティストを選択し、プレイリストにおける歌の少なくとも５０％は、そのアーティストによるべきことを示すことができる。
【００３２】
ユーザにより入力される制約（又は好み）は、ユーザインタフェース１０２によりユーザ定義される制約に変換され、この制約は、ユーザインタフェース１０２を介してユーザに与えるためにストレージ装置１０６に記憶されるファイルからプレイリストを導出するために使用されるアルゴリズムプロセッサ１０４に入力される。
【００３３】
ストレージデバイス１０６は、ユーザが所有する、デジタルフォーマットで全ての歌又はマルチメディアファイルから構成される。歌を含むファイルに加えて、たとえば先の表１に列挙されるような、それら関連する属性が記憶される。
【００３４】
ユーザインタフェース１０２は、どの歌を保持し、どの歌を変えるかを特定することで、プレイリストをリファインすることができるように、生成されたプレイリストに関するフィードバックを提供する。
【００３５】
本発明の好適な実施の形態に係るアルゴリズムのステップを説明するため、自動プレイリスト生成器のフォーマルモデルが以下に記載される。
【００３６】
表１に列挙されるように、先の属性は、それぞれの歌と関連付けされる。ある歌は、属性値からなる有限のベクトルにより与えられる。
【００３７】
【数１】
2009500670.tif 000004
ここで、歌（song）ｓはｋ番目の属性について値νk（∈Ｄk）を有し、ｋ＝１，．．．，Ｋである。Ｋは属性の数を示し、Ｄkは、ｋ番目の属について全ての可能性のある値を含む有限のセットである、ｋ番目の属性のドメインを示す。ｋは、属性の番号である。
【００３８】
音楽コレクションは、有限のセットにより与えられる。
【００３９】
【数２】
2009500670.tif 000005
プレイリストは、有限の歌のシーケンスであり、所与の音楽コレクションＭについて、プレイリストは、以下にベクトルにより与えられる。
【００４０】
【数３】
2009500670.tif 000006
この場合、
【００４１】
【数４】
2009500670.tif 000007
及び
【００４２】
【数５】
2009500670.tif 000008
である。したがって、歌ｐiは、プレイリストにおけるｉ番目のポジションでの歌である。歌ｐiは、Ｋの属性値のベクトルである。ｐikは、プレイリストｐにおけるｉ番目の歌のｋ番目の属性の値を示す。Ｍnは、Ｍからのｎ個の歌の全ての可能性のあるプレイリストのセットを示す。
【００４３】
ユーザ定義された制約は、どの歌が、プレイリストにおけるどのポジションで同時に生じるのが可能であるかを判定するプレイリストでの制約である。プレイリストは、その制約により定義される制約に合致する場合に、制約を「満足する“satisfy”」と呼ばれる。
【００４４】
ｕｎａｒｙ，ｂｉｎａｒｙ及びｇｌｏｂａｌの制約といった、３つの特徴のあるタイプの制約が、それらが定義されるポジションの数に基づいて存在する。先に記載されたように、プレイリストは、歌のシーケンスであり、ポジションは、そのシーケンスにおける歌の位置である。Ｕｎａｒｙ制約は、プレイリストの単一の位置で生じることが許容される歌を制限する。
【００４５】
歌はその属性により定義されるので、これらの属性の観点で制約を定義することが論理的である。プレイリストにおいて歌を固有に識別する属性が存在することが想定される。
【００４６】
属性に基づいて制約を定義することで、ユーザは、歌のレベルでユーザの望みを特定することができ、たとえば、第一の歌は、“ABBA”による“Dancing  Queen”である。したがって、一般性を失うことなしに、ｕｎａｒｙ制約が、プレイリストの単一の位置で生じることが許容される属性値を制約することが述べられる。
【００４７】
ｂｉｎａｒｙ制約は、２つのプレイリストの位置で定義される。この制約は、特定された位置での歌の間の２進の関係を表す。これらの制約は、プレイリストにおける歌に対する順序又は歌の間の一致を特定するために使用される。例は、プレイリストの最初の２つの歌が同じアーティストによらないこと、又は、第一の位置での歌のテンポが第二の位置での歌のそれよりも高いことである。
【００４８】
最後に、ｇｌｏｂａｌ制約は、多数の位置に基づいて定義される。例は、プレイリストにおける歌の半分以上がジャンル“Popular”に属するか、プレイリストの全体の期間が１時間となることである。
【００４９】
ユーザ定義された制約に基づいて、本発明の好適な実施の形態に係るアルゴリズムは、「ベストフィット」のソリューションのプレイリストを発見する。しかし、全てのユーザ定義された制約を満足するプレイリストを発見することは実施可能ではない場合があり、又は、ソリューションが存在する場合に、実行可能なソリューションを発見することが難しい場合がある。したがって、本発明の実施の形態に係るアルゴリズムは、アルゴリズムプロセッサ１０４により実行され、ユーザ定義される制約の「ベストフィット」であるソリューションを発見する。これは、制約が違反される範囲を確立することで達成される。したがって、プレイリストが制約を満足するか、違反することを単に説明する代わりに、プレイリストの品質が比較される。これは、パナルティ関数ｆpenである関数として表現される。制約のセット及びプレイリストに関してｆpenを評価することは、プレイリストがこれらの制約をどの位多く違反しているかを示す０と１の間の値が得られる。０の値は、プレイリストが全ての制約を満足することを意味し、１の値は、制約の最大の可能性のある違反を意味する。ペナルティ関数の値は、制約のそれぞれについてペナルティを結合することで計算されるｆcon。ｆpenに関して、ｆconの値は、０と１の間で正規化され、この場合、高い値は、制約の大きな違反を示す。ｆpenは、Ｃにおける全ての制約にわたりｆconの平均として定義される。
【００５０】
【数６】
2009500670.tif 000009
しかし、この定義は、全ての制約が同様に重要であると考えられることを想定している。制約の間の優先度の意味を導入するため、負ではない値を生じる制約に関する制約重み関数ｗconは、Ｃにおけるそれぞれの制約の重要度を表現するために導入される。
【００５１】
Ｃにおける制約のそれぞれについての標準的なペナルティ関数は、以下のように変換される。
【００５２】
【数７】
2009500670.tif 000010
τconは、制約の変換関数である。たとえば、関数τconは、制約の小さな違反が比較的申告であることを示すために使用される。そのケースでは、
【００５３】
【数８】
2009500670.tif 000011
である。アイデンティティ関数
【００５４】
【数９】
2009500670.tif 000012
変換関数として使用して、変換なしに制約のペナルティが得られる。
【００５５】
ある制約のセットＣ及びプレイリストｐに関するペナルティ関数ｆpenは、Ｃにおける全ての制約にわたる重み付け平均として定義される。
【００５６】
【数１０】
2009500670.tif 000013
式（１０）におけるｆpenの定義を使用して、所与の音楽コレクションＭ、制約のセットＣ、制約重み関数ｗcon、制約変換関数τcon、及び２つの正の整数ｎmin及びｎmaxについて本発明のアルゴリズムは、ｆpen（Ｃ,ｐ）が最小にされるように、Ｍから少なくともｎminの歌及び多くともｎmaxの歌のプレイリストｐを発見する。
【００５７】
制約ペナルティ関数ｆconの最もささいな選択は、プレイリストにより制約が満足される場合に０に等しくなるようにし、その他の場合に１に等しくなるようにすることである。しかし、これは、制約を満足するプレイリストと制約に違反するプレイリストである、２つのプレイリストのセットのみが見つけられることを意味する。プレイリストが違反する程度を示すため、制約は、プレイリストの更に包括的な比較を必要とする。以下を例として考える。
【００５８】
制約は、プレイリストにおいて“ABBA”による歌がないことを示す。次いで、“ABBA”による歌のみを含むプレイリストは、他のアーティストによる幾つかの歌と共に“ABBA”による１つの歌のみを含むプレイリストよりも高いペナルティが得られる。
【００５９】
したがって、本発明の実施の形態に係るアルゴリズムでは、制約ペナルティ関数ｆconは、それぞれのタイプの制約について定義される。これらの制約では、属性値は、実数及び整数のような他の値と同様に比較される。これらの比較をパナルティ値に変換するため、属性のドメインＤkにおける２つの値の間の差を示す０と１との間の値をリターンする差の関数Θkが導入される。属性の番号ｋをもつ公称の属性、及びその属性のドメインにおける２つの値ａ，ｂ∈Ｄkについて、差の関数Θkは、
【００６０】
【数１１】
2009500670.tif 000014
により与えられる。
【００６１】
全体の順序が定義される属性について、すなわち、順序及び数値の属性について、ｍｉｎk及びｍａｘkのそれぞれにより示される最小及び最大の値が定義され、ｋは属性の属性番号である。値ｍｉｎkは、
【００６２】
【数１２】
2009500670.tif 000015
として定義され、値ｍａｘkは、
【００６３】
【数１３】
2009500670.tif 000016
として定義される。
【００６４】
ドメインが有限であるため、属性領域におけるこれら最小及び最大の値の存在が保証される。
【００６５】
数値属性に関して、インフィックス表記法“−”により示される差が既に定義される。しかし、この差は、０と１の間の範囲を有さず、従って、その絶対値をとり、その絶対値をその範囲で割ることで正規化する。２つの数値の間の最小の差は０であり、最大の差は、ｍａｘk−ｍｉｎkであり、この最大の差は、厳密に正であることが想定される。
【００６６】
したがって、属性番号ｋをもつ数値属性、及びその属性のドメインにおける２つの値ａ，ｂ∈Ｄkについて、差の関数Θkは、
【００６７】
【数１４】
2009500670.tif 000017
により与えられる。
【００６８】
標準の差“−”は、順序の属性に関して定義されない。しかし、全体の順序は、幾つかの値が他よりも互いに近いことを示す。たとえば、値ａ，ｂ及びｃについて、ａ＜ｂ＜ｃである場合、ｂはａとｃの間にあるので、ａはｃよりもｂに近い。同じ差の関数は、公称の属性に関して使用される。しかし、良好な分解能につながるので、全体の順序を使用することが好ましい。したがって、２つの可能性のある関数値（０又は１）を有する代わりに、公称の属性と同様に、差の関数は、０と１の間の値の多数の値をとる。この結果、順序の属性は、以下の特性を有するように、属性の番号ｋにより、関数ｎａｔk：Ｄk→Ｎによる自然数にマッピングされる。それぞれａ，ｂ∈Ｄkについて、この場合ａ＜ｂであり、ａ＜ｃ及びｃ＜ｂであるようにｃ∈Ｄk｛ａ,ｂ｝が存在せず、ｎａｔk（ｂ）−ｎａｔk（ａ）＝１が保持される。これにより、属性のドメインにおけるそれぞれの値は、その順序の番号にマッピングされる。ｎａｔk（ｍａｘk）−ｎａｔk（ｍｉｎk）が厳密に正であると仮定すると、属性の番号ｋをもつ数値属性、及びａ，ｂ∈Ｄkについて、差の関数Θkは、
【００６９】
【数１５】
2009500670.tif 000018
により与えられる。
【００７０】
カテゴリの属性は、全体の順序を有さないが、部分的な順序を有する。したがって、関数ｎａｔkを有することが可能ではない。カテゴリの属性について、幾つかの類似の関数を使用することができる。類似性の関数は、コントラストモデル又はラジオモデル又はプロダクトルールモデルに基づく。しかし、ソリューションをシンプルに保持するため、カテゴリの属性について、式１１における公称の属性について使用したのと同じ差の関数を使用する。最後に、値のセットを表す属性、たとえば歌を実行するために使用されるインスツルメントが存在する。２つの値のセットの間の差について、レシオモデルが適用される。しかし、レシオモデルは、２つのセット間の類似性を計算するために使用され、差を計算するために使用されない。したがって、セットが共通して有する比例のエレメントの数が増加するときに、差の値が減少するように、この類似性の値の補足が利用される。したがって、属性の番号ｋをもつそのドメインにおける属性値のセットを有する属性、及びＡ，Ｂ∈Ｄkについて、差の関数Θkは、
【００７１】
【数１６】
2009500670.tif 000019
により与えられる。
【００７２】
本発明の好適な実施の形態に係るアルゴリズムは、２つのブランチを有しており、第一のブランチでは、発見された第一のソリューションのシーケンスに対してランダムチェンジが行われ、第二のブランチでは、第一のソリューションのシーケンスに対してバイアスチェンジが行われる。アルゴリズムのランダムブランチは、近似的な結合の最適化を使用する。結合の最適化の問題の例は、ソリューション空間とも呼ばれる、有限又はカウント可能なソリューションのセットＳ、及びそれぞれのソリューションとコストを関連付けるコスト関数
【００７３】
【数１７】
2009500670.tif 000020
により特定される。アルゴリズムプロセッサ１０４で実行されるアルゴリズムは、最適なコストをもつソリューションを発見する。このアルゴリズムの特徴は、周辺構造
【００７４】
【数１８】
2009500670.tif 000021
であり、それぞれのソリューションと、ある意味でその近くにある周辺のソリューションのセットを関連付けする。本発明のアルゴリズムは、この周辺構造を使用して、ソリューションスペースを効率的に進行する。ソリューションは、良好なコストをもつ周辺のソリューションが存在しない場合にローカルに最適（locally  optimum）と呼ばれる。ソリューションは、良好なコストをもつ全体のソリューションスペースにおけるソリューションが存在しない場合にグローバルに最適（globally  optimum）と呼ばれる。アルゴリズムの目的は、かかるグローバルに最適と呼ばれる。
【００７５】
本発明の好適な実施の形態に係るアルゴリズムのランダムなブランチは、繰り返しプロセスを使用して、ソリューションスペースを進行する。それぞれの繰り返しでは、アルゴリズムは、以下のように、良好なコストをもつソリューションについて現在のソリューションの周辺をサーチする。
【００７６】
【表２】
2009500670.tif 000022
かかるソリューションが発見された場合、現在のソリューションを置き換える。さもなければ、アルゴリズムのランダムブランチは停止し、現在のソリューションに戻る。これは、ローカルの最適であるが、必ずしもグローバルに最適ではない。手段として、アルゴリズムは、別のローカルに最適なソリューションを生成する異なる初期のソリューションで再始動される。この手順が十分な回数で繰り返される場合、グローバルに最適なソリューションを常に発見する。しかし、多くのローカルに最適なソリューションが存在し、初期のソリューションが少なく選択される場合、必要とされる再始動の数は、非常に高い。
【００７７】
ローカルに最適を脱出し、再始動の必要を除くため、先の繰り返しは、統計学的な基準により決定論的な（厳密な改善）受け入れの基準を置き換えることで変更され、これにより、更に効率的な近隣を構築するか、更に仕立てられたアルゴリズム（変更されたアルゴリズム）を設計するため、問題の構造の詳細な研究の必要を回避することができる。
【００７８】
この変更されたアルゴリズムのフォームは、固体の物理的なアニーリングに対する類似性に基づいており、この場合、固体が融解するような所定の温度に固体が加熱される。その粒子は、それ自身をランダムに配置し、システムのエネルギーは高い。次いで、温度は、固体のグランド状態を得るために徐々に低くされる。粒子は高度に構造化され、システムのエネルギーは最小である。
【００７９】
アルゴリズムは、アニーリングプロセスから状態、エネルギー、及び温度のコンセプトを包み込む。ソリューションは、状態に対応し、ソリューションのコストは、状態のエネルギーに対応する。制御変数ｔが導入され、これは温度に対応する。
【００８０】
ソリューションｓが与えられ、周辺のソリューションｓ’を許容するチャンスは、この制御変数に依存する許容確率
【００８１】
【数１９】
2009500670.tif 000023
により定義される。制御変数のそれぞれの値について、ソリューションのシーケンスが発生及び評価され、その後、制御変数が低下される。これらのシーケンスのサイズ、制御パラメータの初期値、制御変数のデクリメント関数、停止基準は全て、以下のランダムブランチアルゴリズムが適用される前に決定される必要がある。
【００８２】
【表３】
2009500670.tif 000024
さらに、先の繰り返しは、クーリングスケジュールの定義を必要とする。理論的なスケジュールがある。最適なソリューションに向かってアルゴリズムの無症候性の集束を保証する理論的なスケジュールが存在する。しかし、これらスケジュールは、無限の計算時間を必要とするので実用的ではない。これは、何故、最適なソリューションを保証しないとしても、非常にシンプルなスケジュールが実際に好まれるかという理由である。これらシンプルなクーリングスケジュールのうちの１つは、幾何学的なスケジュールである。このスケジュールでは、全てのシーケンス長Ｌkは等しく、制御パラメータの初期値ｔ0は、２つの隣接するソリューション間のコストにおける最大の差であり、制御変数のデクリメントは、
【００８３】
【数２０】
2009500670.tif 000025
により計算され、ここでαは、１よりも小さいが１に近い正の定数である。
【００８４】
本発明のアルゴリズムを適用するため、ソリューションＳ、コスト関数ｆ及び周辺の構造Ｎの適切なセットを定義する必要がある。ソリューションスペース及びコスト関数の選択は、所与の音楽コレクションＭ、制約のセットＣ、制約重み関数ｗcon、制約変換関数τcon、及び２つの正の整数ｎmin及びｎmaxについて、ｆpen（Ｃ，ｐ）が最小にされるように、Ｍからの少なくともｎmin及び多くともｎmaxの歌のプレイリストを発見する、本発明のアルゴリズムの定義から続く。ソリューションスペースとして、Ｍからの少なくともｎmin及び多くともｎmaxの歌からなる全てのプレイリストが選択され、すなわち、
【００８５】
【数２１】
2009500670.tif 000026
である。
【００８６】
次いで、それぞれのソリューションは、プレイリストに対応する。先に定義された、制約のセットＣ及びプレイリストに関するペナルティ関数ｆpenは、本発明のアルゴリズムにおけるソリューションに関するコスト関数ｆとしての役割を果たす。
【００８７】
本発明の好適な実施の形態に係るアルゴリズムは、動きが局所的な衝撃のみを有する周辺構造を有する。周辺における動きは、ある周辺におけるあるソリューションから別のソリューションへの切り替えを意味する。ある周辺におけるある動きは、あるプレイリストから別のプレイリストへの変化となる。
【００８８】
周辺は、異なるプレイリストにスイッチするために許容される変化により定義される。考えは、小さな変化をプレイリストに適用することにより、ペナルティ関数は、小さな量だけ変化することである。これらのペナルティの変化は、インクリメント的に、したがって更に効率的に計算される。本発明のアルゴリズムでは、４つの周辺が定義される。最初の３つの周辺は、どの歌がプレイリストで生じるかを変える動きにより定義される。第四の周辺は、プレイリストにおける歌の順序を変える動きにより定義される。
【００８９】
第一の周辺は、プレイリストポジション及び音楽からの歌といった、２つのパラメータとの置き換えの周辺（replace  neighbors）である。
【００９０】
したがって、音楽コレクションＭが与えられた場合、プレイリストｐ∈Ｍnの置き換えの周辺は、
【００９１】
【数２２】
2009500670.tif 000027
により定義され、この場合、以下が成り立つ。
【００９２】
【数２３】
2009500670.tif 000028
周辺の数、又は置き換えの周辺のサイズは、プレイリストにおける歌の数に依存し、音楽コレクションのサイズに依存する。周辺は、全てのプレイリストからなり、あるポジションにある歌のみがＭからの歌により置き換えられ、したがってｎｍの周辺が存在し、ｍ＝｜Ｍ｜である。
【００９３】
式（２３）によれば、ｐにおけるｉ番目のポジションにある歌は、ｐiであり、これは歌ｓにより置き換えられる。これにより、プレイリストｐ’が得られ、この場合、ｐによる差は、ｉ番目のポジションにある歌である。
【００９４】
置き換えの周辺における全てのプレイリストは、同じ数の歌を有する。この周辺のみがアルゴリズムで使用される場合、アルゴリズムは、最初のプレイリストに対して等しい数の歌をもつプレイリストを含むソリューションスペースの一部を調査する必要がある。
【００９５】
第二の周辺は、プレイリストにおけるポジション及び音楽コレクションからの歌といった２つのパラメータをもつ挿入の周辺である。結果的に得られるプレイリストは、オリジナルのプレイリストよりも１曲多い歌を含む。結果的に得られるプレイリストがソリューションスペースにあることを保証するため、これらの動きは、ｎmaxの歌よりも少ない歌を有するプレイリストで許容される。
【００９６】
したがって、音楽コレクションＭが与えられると、ｎ＜ｎmaxによるプレイリストｐ∈Ｍnの挿入の周辺は、
【００９７】
【数２４】
2009500670.tif 000029
により定義され、この場合、
【００９８】
【数２５】
2009500670.tif 000030
【００９９】
【数２６】
2009500670.tif 000031
である。
【０１００】
挿入の周辺のサイズは、プレイリストにおける歌の数に依存し、音楽コレクションのサイズに依存する。周辺は、全てのプレイリストからなる。Ｍからの唯一の歌が１つのポジションに挿入され、したがってｎ＜ｎmaxの場合に（ｎ＋１）ｍの周辺を有し、その他の場合に周辺を有さない。
【０１０１】
歌ｓがｉ番目のポジションでプレイリストｐに挿入される挿入の動きによりプレイリストｐ’が得られ、この場合、歌ｓはｉ番目のポジションにあり、全ての後続する歌は、挿入を行うために１つのポジションを右にシフトする。プレイリストｐ’は、ｐよりも１曲多い歌を含む。
【０１０２】
第三の周辺は、プレイリストにおけるポジションといった１つのパラメータによる削除の周辺である。結果的に得られるプレイリストは、オリジナルのプレイリストよりも１曲少ない歌を含む。結果的に得られるプレイリストがソリューションスペースにあることを保証するため、これらの動きは、ｎminの歌を超える歌を有するプレイリストでのみ許容される。
【０１０３】
したがって、音楽コレクションＭが与えられると、ｎ＞ｎminによるプレイリストｐ∈Ｍnの削除の周辺は、
【０１０４】
【数２７】
2009500670.tif 000032
により定義され、この場合、
【０１０５】
【数２８】
2009500670.tif 000033
である。
【０１０６】
削除の周辺のサイズは、プレイリストにおける歌の数に依存する。周辺は、１つのポジションから除かれた唯一の歌を有する全てのプレイリストからなり、したがって、ｎ＞ｎminの場合にｎの周辺を有し、その他の場合に周辺を有さない。
【０１０７】
プレイリストｐのｉ番目のポジションにある歌は除かれる。これにより、プレイリストｐ’が得られ、この場合、ポジションｉ後の全ての歌は、削除を行うために１つのポジションを右にシフトしている。プレイリストｐ’は、ｐよりも１曲少ない歌を含む。
【０１０８】
前の３つの周辺を定義した動きはプレイリストで生じた歌のセットを変えるが、最後の周辺は、プレイリストで歌が現れる順序を変える動きにより定義される。この周辺は、スワップされるべきプレイリストにおける２つのポジションといった、２つのパラメータを有する。
【０１０９】
したがって、音楽コレクションＭが与えられると、プレイリストｐ∈Ｍnのスワップの周辺は、
【０１１０】
【数２９】
2009500670.tif 000034
により定義され、この場合、
【０１１１】
【数３０】
2009500670.tif 000035
である。
【０１１２】
スワップの周辺のサイズは、プレイリストにおける歌の数に依存する。周辺は、２つのポジションにある歌が交換される全てのプレイリストからなる。
【０１１３】
ｐにおけるｉ番目のポジションにある歌は、ｐiであり、これは、ｐjであるｊ番目のポジションにある歌により置き換えられ、逆も然りである。これにより、プレイリストｐ’が得られ、この場合、ｐによる差は、ポジションｉ及びポジションｊにある歌が場所を変えている。
【０１１４】
４つの周辺は、以下のように結合される。
【０１１５】
【数３１】
2009500670.tif 000036
挿入と削除の動きにより、動きにおけるポジションに従うプレイリストのポジション上で歌がシフトされ、置き換え及びスワップの動きにより、動きにおけるプレイリストのポジションに影響を及ぼす。したがって、ペナルティにおける差は、置き換え及びスワップの動きについて更に効果的に計算することができる。したがって、ユーザ定義された制約のペナルティを評価する効率を改善するため、確率の重みｗreplace、ｗinsert、ｗdelete及びｗswapは、周辺Ｎreplace、Ｎinsert、Ｎdelete及びＮswapのそれぞれについて導入され、ここで０≦ｗi≦１であり、Σiｗi＝１である。これらの重みは、特定の周辺から周辺を生成する確率を決定する。
【０１１６】
本発明のアルゴリズムの性能を高めるため、すなわち、良好なプレイリストを早く発見するため、特に、満足することが困難なユーザ定義された制約について、バイアスチェンジが使用される。
【０１１７】
ｕｎａｒｙ制約に関して、これらは、プレイリストの単一の位置で生じることが許容される属性値を制限する。これらｕｎａｒｙ制約を処理するため、プレイリストのポジションの歌のドメインのコンセプトが導入される。
【０１１８】
アルゴリズムの例について、ポジションｉの歌のドメインＭiは、音楽コレクションのサブセットＭi⊆Ｍであり、そのポジションで許容される可能性のある歌を定義し、プレイリストｐについて、ｐi∈Ｍiが保持される。したがって、アルゴリズムのサーチスペースは、歌のドメインを減少することで減少される。
【０１１９】
ｕｎａｒｙ制約は、これらの制約が定義されるポジションの歌のドメインを減少することで扱われる。ｕｎａｒｙ制約Ｕｎａｒｙ（ｉ，ｋ，Ｄ）は、ポジションｉの歌の属性ｋがセットＤにあるべきこと、すなわちｐik∈Ｄであることを規定する。たとえば、アーティストが第三の属性であるとすると、ｕｎａｒｙ制約Ｕｎａｒｙ（１，３，｛ＡＢＢＡ｝）は、プレイリストが“ＡＢＢＡ”による歌で開始すべきことを規定する。
【０１２０】
したがって、このＵｎａｒｙ制約が満たされることを保証するため、“ＡＢＢＡ”以外のアーティストによる全ての歌は、最初のポジションの歌のドメインから除かれる。歌のドメインの低減は、ｕｎａｒｙ制約を使用して定義されるグローバル制約のうちの幾つかを扱うために使用される。かかる制約は、全てのｌ1≦ｉ≦ｌ2についてｐik∈Ｄを特定する、ForEachGlobal(l1,l2,Unary(.,k,D))として与えられる。
【０１２１】
したがって、所与の音楽コレクションＭ及び制約のセットＣについて、プレイリストのポジションｉのｕｎａｒｙ（単項）制約された歌のドメインは、
【０１２２】
【数３２】
2009500670.tif 000037
により定義され、この場合、
【０１２３】
【数３３】
2009500670.tif 000038
及び
【０１２４】
【数３４】
2009500670.tif 000039
である。
【０１２５】
セットＵi∩Ｇiが空であるケースでは、ポジションｉは、ｕｎａｒｙ制約により過剰に制約される。そのケースでは、そのポジションの歌のドメインの低減が省略され、ｕｎａｒｙ制約は、上述されたアルゴリズムによりそのポジションで扱われる。
【０１２６】
あるポジションがｕｎａｒｙ制約により過剰に制約されないケースでは、そのポジションでｕｎａｒｙ制約を違反するプレイリストは、もはや考慮されない。したがって、周辺構造が低減される。置き換えの周辺では、新たな歌は、あるプレイリストのポジションの歌の置き換えとなるように選択される必要がある。ｕｎａｒｙ制約された変数では、音楽コレクションからの全ての歌がサーチされるわけではないが、特定のポジションの歌のドメインからの歌のみがサーチされる。
【０１２７】
したがって、音楽コレクションＭ及び制約のセットＣが与えられると、プレイリストｐ∈Ｍnのｕｎａｒｙ制約された置き換えの周辺は、
【０１２８】
【数３５】
2009500670.tif 000040
により定義され、ｒｅｐｌａｃｅ（ｉ,ｓ,ｐ）は、式（２３）により定義されるのと同じである。
【０１２９】
挿入の周辺では、ある歌は、あるプレイリストポジションに挿入されるために選択される。さらに、そのポジションの歌のドメインからの歌のみが特定のポジションにあるプレイリストに挿入されることが許可される。しかし、特定のポジションで開始するプレイリストの部分にあった歌は、あるポジションをプレイリストの終了に全てシフトするため、それらのポジションを考慮する必要がある。したがって、歌が、それらがシフトするポジションの歌のドメインに実際にあることを保証することが必要である。その結果、プレイリストは、ポジションの歌のドメインに依存して、２つの部分に分割される。第一の部分は、プレイリストのヘッドであり、異なる歌のドメインを有するポジションからなる。このプレイリストの部分のサイズｎheadは、Ｃにおけるｕｎａｒｙ制約の定義で生じる最大のプレイリストのポジションである。
【０１３０】
したがって、制約のセットＣについて、プレイリストｐのヘッドは、（ｐ1，．．．，ｐnhead）として定義され、この場合、
【０１３１】
【数３６】
2009500670.tif 000041
である。
【０１３２】
ポジションｎhead＋１で開始するプレイリストの第二の部分は、その歌のドメインが同一である連続するポジション、プレイリストのテールからなる。テールにおけるポジションの歌のドメインは、第二のアーグメントとして∞をもつForEachGlobal制約により制限されるのみである。これは、全ての歌の領域が同じ制約により制限され、従ってそれらが同一であることを意味する。ここで、歌のドメインの減少のために許可されないポジションに歌があることを心配する必要なしに、プレイリストのテールにおけるポジションに挿入の動きを実行することができる。
【０１３３】
したがって、音楽コレクションＭ及び制約Ｃのセットが与えられると、ｎ＜ｎmaxによるプレイリストｐ∈Ｍnのｕｎａｒｙ制約された挿入の周辺は、
【０１３４】
【数３７】
2009500670.tif 000042
により定義され、この場合、ｉｎｓｅｒｔ（ｉ，ｓ，ｐ）は式（２５）により定義されたのと同じである。ｎ＝ｎmaxである場合、
（外１）
2009500670.tif 000043
である。
【０１３５】
第三に、削除の周辺における動きは、削除の動きの結果としての歌のシフトは、歌のドメインの減少により既に対処されたｕｎａｒｙ制約を違反する場合がある点で、挿入の動きと同じ問題を引き起こす。さらに、これは、削除の動きがプレイリストのテールにおけるポジションで実行されるのを可能にすることで解決される。
【０１３６】
したがって、音楽コレクションＭ及び制約のセットＣが与えられた場合、ｎ＞ｎmaxによるプレイリストｐ∈Ｍnの制限された削除の周辺は、
【０１３７】
【数３８】
2009500670.tif 000044
により定義され、この場合、ｄｅｌｅｔｅ（ｉ，ｐ）は式（２８）で定義されたのと同じである。ｎ＝ｎminである場合、
（外２）
2009500670.tif 000045
である。
【０１３８】
最後に、スワップの周辺では、２つのポジションが選択され、これら２つのポジションの歌がスワップされる。ｕａｒｙ制限された変形では、２つの規定されたポジションの歌が両方のポジションの歌のドメインに現れる場合に、スワップの動きのみが許容される。
【０１３９】
したがって、音楽コレクションＭ及び制約のセットＣが与えられた場合、プレイリストｐ∈Ｍnのｕｎａｒｙ制限されたスワップの周辺は、
【０１４０】
【数３９】
2009500670.tif 000046
により定義され、この場合、ｓｗａｐ（ｉ，ｊ，ｐ）は式（３０）で定義されたのと同じである。
【０１４１】
歌のドメインの低減の量に依存して、周辺は先のやり方で低減される。これらｕｎａｒｙ制限された周辺を結合することは、アルゴリズムで使用されるｕｎａｒｙ制限された周辺の構造
（外３）
2009500670.tif 000047
を導出する。
【０１４２】
【数４０】
2009500670.tif 000048
更なる改善では、そのプレイリストのペナルティがそのプレイリストにおける歌の順序を変えることによってのみ影響される制約と、そのペナルティが順序を変えることで影響されない制約との間で区別が行われる。後者の良好な例は、全体のプレイリストに関するＳｕｍＧｌｏｂａｌ制約である。プレイリストで生じる属性値の総和は、プレイリストで生じる歌のセットが変化しないので、順序のみが変わったときに同じままである。上述されたように、区別が行われる。置き換え、挿入及び削除の周辺は、プレイリストで生じた歌のセットを変える動きをもつ周辺であり、スワップの周辺は、プレイリストにおける歌の順序のみを変える動きをもつ周辺である。
【０１４３】
したがって、本発明のアルゴリズムの例が与えられたとき、少なくともｎmin及び多くともｎmaxの歌からなるプレイリストｐが存在する場合（存在するときに限り）、定数ｃはオーダリング定数であり、ｆcon（ｃ，ｐ）≠ｆcon（ｃ，ｐ’）によるプレイリストｐ’∈Ｎswap（ｐ）が存在する。
【０１４４】
基本的に、全てのｕｎａｒｙ（単項）及びｂｉｎａｒｙ（二項）制約は、これらが１又は２のプレイリストのポジションでそれぞれ定義されるので、オーダリング制約である。したがって、スワップの動きを実行することでこれらの位置の歌を変え、続いてペナルティを変えることが可能である。同じ考え方を使用して、全体のプレイリストで定義されない全てのグローバル制約もオーダリング制約である。最後に、グローバル制約のなかには、それらが定義されるポジションに関わらず、オーダリング制約であるものがある。
【０１４５】
本発明の好適な実施の形態に係るアルゴリズムは、２つの個別の周辺を使用して、オーダリング制約を処理する。考えは、上述された制約及び周辺における区別を使用して、サーチを分離することである。一方の部分では、プレイリストに現れる歌が変わり、他方の部分では、現在の歌のセットについて最適な順序が発見される。第一の部分であるリセレクトの部分では、置き換え、挿入及び削除の周辺からなる周辺が利用される。したがって、プレイリストｐについて、以下が成り立つ。
【０１４６】
【数４１】
2009500670.tif 000049
このリセレクトの周辺は、確率の重みｗswapは０に等しいｕｎａｒｙ制限された周辺の構造
（外４）
2009500670.tif 000050
の特別のケースである。したがって、リセレクト部分では、プレイリストで生じる歌を変えることで制約が満足される。次いで、サーチの第二の部分である、リオーダリング部分が実行され、ここでは、スワップの周辺が利用されて、サーチのリセレクトの部分の結果である、プレイリストにおける歌のセットについて最適な順序を発見される。スワップの動きのみがこの部分で利用されるので、オーダリング制約のペナルティのみが考慮される必要がある。しかし、歌のセットの最適な順序を発見することは、困難なことがある。
【０１４７】
これを達成するため、以下に列挙されるシンプルな手順が後続され、現在のプレイリストにおける歌の順序を改善する。この手順は、ＮＤＲ（non-deteriorating  reordering）と呼ばれ、固定された数のスワップの動きを試み、プレイリストの高いペナルティにつながらない場合にそれらを受け入れる。オーダリングの制約のみがこのペナルティに帰する。これは、オーダリングの制約のみが、そのペナルティがスワップの動きにより影響される制約であるからである。ＮＤＲ手順は、実行される繰り返しの回数を制限し、現在のソリューションに等しいペナルティをもつ周辺が受け入れられる。考えは、先の２つの部分の間で交互にし、リセレクト部分におけるプレイリストで生じる歌の最適なセットを発見し、ときどき、リオーダリング部分におけるそのセットのオーダリングを最適化しようとする。
【０１４８】
【表４】
2009500670.tif 000051
ここで
（外５）
2009500670.tif 000052
はオーダリング制約のセットである。
【０１４９】
先の変更されたアルゴリズムを適用することにおいて、以下のアルゴリズムが得られる。パラメータβは、リオーダリング手順の連続するコールの間で調べられるリセレクトの周辺における動きの量を設定するために使用される。パラメータγは、リオーダリング部分で調べられるスワップの動きの量を制御するために使用される。
【０１５０】
【表５】
2009500670.tif 000053
先のアルゴリズムは、高速につくることができる。制約のなかには、満足することが困難であり、プロセスの速度を落とすことが困難なものがある。たとえば、これらの制約は、アルゴリズムの実行時間の５秒内で満足されない。これは、これらの制約のペナルティにおける変化を招く音楽コレクションにおける幾つかの歌が存在するためである。たとえば、ユーザ定義された制約が、“ABBA”による歌の所定の数が存在することを特定する場合、その制約のペナルティを変えるやり方は、“ABBA”により歌をプレイリストに加えること、又は、プレイリストからそのアーティストによる歌を除くことである。これらの制約の満足を助けるため、バイアスチェンジは、バイアスの別の程度を変更されたアルゴリズムの周辺の生成方法に提供するために導入される。所定の程度にまで、確率の重みｗreplace、ｗinsert及びｗdeleteの使用により、アルゴリズムのランダムチェンジのブランチでバイアスが使用される。更なるバイアスは、アルゴリズムのバイアスブランチに組み込まれる。バイアスチェンジを選択することは、制約による投票により達成される。
【０１５１】
ランダムな動きの選択では、第一のステップは、確率の重みｗreplace、ｗinsert及びｗdeleteによりバイアスされる、リセレクトの周辺を有する周辺のうちの１つを選択することである。現在のプレイリストがｎmaxの歌よりも少ない場合にのみ挿入の周辺が選択され、現在のプレイリストがｎminの歌を超える場合にのみ削除の周辺が選択される。次いで、一様にランダムなやり方で動きのためのプレイリストの位置が選択される。置き換えの動きについて、そのポジションは、プレイリストにおけるポジションであり、挿入の動きについて、ポジションは、少なくともｎhead＋１及び多くともｎ＋１である必要があり、削除の動きについて、位置は、ｎhead＋１よりも低いか、ｎよりも高くなることが許容されない。削除の周辺が第一のステップで選択された場合、動きが完了する。置き換えの動き又は挿入の動きのケースでは、歌を選択することが必要である。
【０１５２】
ある動きが投票により選択された場合、周辺は、第一のステップでバイアスされたランダムなやり方で選択されるが、ポジションを選択することにおいて投票の方法が適用され、置き換え又は挿入の周辺のケースでは、歌である。Ｃにおける制約のそれぞれは、動きの可能性のあるプレイリストのポジションを支持するか、反対する。あるポジションに動きがある制約のペナルティを増加するために期待される場合、その制約は、そのポジションについて否定的な投票を投じる。しかし、あるポジションの動きがある制約のペナルティを減少する可能性がある場合、制約は、肯定的な投票を投じる。様々な投票のストラテジが採用される場合がある。これらは本明細書では記載されない。全ての制約からの投票が合計され、プレイリストのポジションは、これらの投票によりバイアスで選択される。したがって、多数の肯定的な投票及び少ない否定的な投票をもつポジションは、少ない肯定的な投票と多くの否定的な投票をもつポジションよりも選択される可能性が高い。置き換え又は挿入の周辺が選択された場合、プレイリストに追加する歌も選択される必要がある。これは、投票により行われるが、全ての制約が投票するわけではない（部分的な制約の投票）。満足するのが困難な制約のみが投票される。これは、これらが、アルゴリズムの通常のランダムにされたブランチにより満足するのが困難な制約であるためである。さらに、これらの制約の投票のストラテジは、音楽コレクションにおける幾つかの歌のみが制約のペナルティに影響を及ぼすため、むしろ効率的である。したがって、これらの歌のみが、音楽コレクションにおける全ての歌をチェックして、それらがどの位制約に影響を及ぼすかを見る代わりに投票される。
【０１５３】
ここで、動きが完了し、（部分的な制約）投票による現在のプレイリストの周辺が生成される。この動きの生成手順は、変更されたアルゴリズムの受け入れの基準の評価により後続される。これにより、以下に列挙されるアルゴリズムが得られる。投票による動きの選択はランダムな動きの選択よりも多くの回数を要するため、さらに、大部分の制約がアルゴリズムのランダムなブランチにより効率的に満足されるため、部分的な制約の投票は、δで示される周辺の生成の所定のフラクション（たとえば１０％）に適用される。
【０１５４】
【表６】
2009500670.tif 000054
ランダムチェンジとバイアスチェンジからなる先の組み合わせは、ランダムチェンジにより容易に扱われる制約が効果的に扱われるという利点を有し、「困難な」制約は、バイアスチェンジの使用により効果的に扱われる。
【０１５５】
本発明の方法及び装置の好適な実施の形態が添付図面で例示され、上述された詳細な説明で記載されたが、本発明は、開示された実施の形態に限定されるものではないが、特許請求の範囲で述べたような本発明の範囲から逸脱することなしに様々な変形、変更が可能であることが理解される。
【図面の簡単な説明】
【０１５６】
【図１】本発明の好適な実施の形態に係る自動プレイリスト発生器を例示する図である。
【図１】
2009500670.tif 000055
【国際調査報告】
2009500670.tif 000056
2009500670.tif 000057
2009500670.tif 000058