optseq2 アルゴリズム

数式のところは重い（精神的に）ので，いずれ…

ALGORITHM OVERVIEW

optseq2 randomly searches the space of schedules given the constraints
on the command-line and keeps the ones that maximize the given cost
function. Each search iteration begins by creating a random order of
events with the appropriate number of repetitions for each event
type. First order counter-balancing optimization, if done, is
performed here. Next, the timing is generated by inserting random
amounts of NULL stimulus so that the total stimulation time plus null
time is equal to the total scan time.

optseq2は，コマンドライン上に与えられた制約のスケジュールの空間をランダムにサーチし，与えられたコスト関数が最大になるものを保存する．各々のサーチの反復は，各々のイベントタイプの繰り返しの適切な数のイベントのランダム順の作成によってはじまる．一次のカウンターバランス最適化は，もしされれば，ここでなされる．次に，タイミングはNULL刺激のランダム量の挿入によって生成される．つまり，全刺激時間＋null時間＝全スキャン時間となる．

Event onset times are
constrained to be integer multiples of dPSD. An FIR design matrix is
created from this schedule. The FIR peristimulus window begins at
PSDMin and ends at PSDMax and is incremented by dPSD. If polynomial
regressors are specified, they are appended to the FIR matrix to give
the final design matrix, hereafter referred as X. The various costs
are computed from X. The forward model is then y = XB+n, which has the
solution Bhat = inv(XtX)Xy. A contrast is Ghat = C*Bhat, where C is the
the contrast matrix.

イベントのオンセット時間は，dPSDの整数倍として制約される．FIRデザインマトリクスは，このスケジュールから作成される．FIR周辺刺激（peristimulus)窓は，PSDMinからはじまり，PSDMaxで終わる．そして，dPSDによって増大させられる．もし多項式回帰が特定されれば，最後のデザインマトリクスを与える為のFIRマトリクス に関わり，その後，Xとして参照される．この変数コストは，Xから計算される．次のモデルは，y = XB + n，解のBhat = inv(XtX)Xyである．コントラストはGhat = C*Bhatで，Cはコントラストマトリクスである．

CONTRAST MATRIX

By default, the contrast matrix is the identity over all task-related
components. The contrast matrix can be changed by specifying --evc
(and possibly --sumdelays).

デフォルトでは，コントラストマトリクスは，全ての課題関係要素によって同定される．コントラストマトリクスは，--evc (あるいは--sumdelays)によって変化する．

COST FUNCTIONS

First-Order Counter-Balancing (FOCB). The FOCB matrix is the
Nevt-by-Nevt matrix of probabilities that one event type follows
another, where Nevt is the number of event types (excluding the NULL
condition). This is computed only from the sequence of events and is
independent of the timing (this is why it is referred to as
'pre-optimization').

一次のカウンターバランス(FOCB)．FOCBマトリクスは，他のものに続くひとつのイベントタイプの確率のNevt-by-Nevt (Nイベント×Nイベント，かな）マトリクスであり，Nevtは，イベントタイプの数（Null条件を除く）である．これは，イベントのシークエンスからのみ計算され，タイミングの独立がある（そういうわけで，これは'pre-optimization'として参照される）．

The ideal FOCB matrix can be computed from the
number of repetitions for each event type. The FOCB cost matrix is
computed by subtracting the actual probability from the ideal and then
dividing by the ideal. The final cost is computed by averaging the
absolute values of all elements in the cost matrix. This cost is
minimized during pre-optimization. FOCB optimization can be combined
with any other cost function. Note: FOCB requires that there be at
least 2 event types.

理想のFOCBマトリクスは，各々のイベントタイプの繰り返しの数から計算される．FOCBコストマトリクスは，理想の確率から実際の確率を引いた物によって計算さ，理想によって分けられる．最終のコストは，コストマトリクスにおける全ての要素の絶対値の平均によって計算される．このコストは，pre-optimizationの間に最小化される．FOCB最適化は，他のどのようなコスト関数とも結合する．注意：FOCBは，少なくとも2種類のイベントタイプを必要とする．

Efficiency (eff). Efficiency is defined as eff = 1/trace(C*inv(Xt*X)*Ct)
(note: any nuisance regressors are not included in the computation of
the trace but are included in the computation of the inverse). The
quantity trace(C*inv(XtX)*Ct) is a measure of the sum square error in Ghat
(ie, G-Bhat) relative to the noise inherent in the experiment. Therefore,
maximizing eff is a way of finding a schedule that will result in, on
average, the least error in Ghat.

Average Variance Reduction Factor (vrfavg). The Variance Reduction Factor
(VRF) is the amount by which the variance of an individual estimator (ie,
a component of Ghat) is reduced relative to the noise inherent in the
experiment. The VRF for a estimator is the inverse of the corresponding
component on the diagonal of C*inv(XtX)*Ct. The average VRF is this value
averaged across all estimators. This will yield similar results as when
the efficiency is optimized.

Average/StdDev Variance Reduction Factor (vrfavgstd). The cost is defined
as cost = vrfavg - W*vrfstd, where vrfstd is the standard deviation of
the VRFs and W is a weighting factor specified as a parameter on the
command-line. This penalizes schedules that result in large variations
in the individual VRFs of the estimators. There is currently a bug in
the implementation that causes it to mis-state the cost when the number
of repetitions are different for different event types. Also, only use
this cost when using a prescan window equal to or greater than the
PSD window (otherwise there will be a tendency not to schedule events
near the end of the run).

THE SUMMARY FILE

The summary file summarizes the conditions under which the search was
performed as well as the properties of each schedule found. It also
includes the number of iterations searched and the time it took to
search them as well as the average and standard deviation of the cost
measured over all schedules. It also includes the maximum efficiency
and average VRF over all schedules (these will be the same as the
best schedule if the eff or vrfavg cost functions were chosen).

Each schedule is summarized in a table with the following columns:
(1) Rank, (2) Cost, (3) ZCost, (4) Iteration Number (NthIter), (5)
Efficiency (Eff), (6) FOBC Error (CB1Err), (7) Average VRF (VRFAvg),
(7) StdDev VRF (VRFStd),
(8) Minimum VRF (VRFMin), (9) Maximum VRF (VRFMax), and (10) VRF
Range (VRFRng). Many of these measures have been described above.
ZCost is the number of standard deviations from the average cost
(over all schedules). The Iteration Number is the search iteration that
that schedule was found on. The first-order counter-balancing
measures come after this table. First, the ideal FOCB probability
matrix is printed followed by the actual matrix for each of the
schedules. Note: the printed ideal matrix is based on the nominal number
of repetitions. See BUGS.

CHOOSING PARAMETERS SETS

There are several parameters that must be chosen as a group because
they rely and/or relate to each other. These parameters are: (1) the
number of time points (Ntp), (2) the TR, (3) the prescan window (tPreScan),
(4) the duration of each event type (tEv), and (5) the number of repetitions
of each event type (nReps). The most basic relationship requires that
the total amount of stimulation time (tStimTot) be less than or equal to
the total amount of scan time (tScanTot), where tStimTot = sum(tEv*nReps)
(summed over all conditions), and tScanTot = Ntp*TR+tPreScan, so

sum(tEv*nReps) <= Ntp*TR+tPreScan (1)

If this constraint is not met, you will receive a 'Time Constraint
Violation' Error. The total amount of time dedicated to the Null stimulus
(tNullTot) is equal to the difference between the total scan time and
the total stimulation time:

tNullTot = Ntp*TR+tPreScan - sum(tEv*nReps) (2)

If the parameters are chosen such that equality results in equation (1),
then there will not be any time for the Null stimulus, which is generally
not good because inter-stimulus jitter is dependent upon inserting
random amounts of Null between non-Null stimuli.

A rule of thumb is to allocate as much time for the Null as one would for
any other stimulus. This can be done by choosing parameters such that

sum(tEv*nReps)(nEv+1)/nEv = Ntp*TR+tPreScan (3)

where nEv is the number of event types. The schedule can be optimized
around this point by allowing the number of repetitions to vary around
this nominal value.

There is also a DOF constraint which requires that the number of parameters
estimated be less than the number of time points, ie

Nbeta = nPSD*nEv+(PolyOrder+1) < Ntp (4)

where Nbeta is the number of parameters, nPSD is the number of elements
in the post-stimulus time window (ie, (PSDMax-PSDMin)/dPSD), and PolyOrder
is the order of the nuisance polynomial specified with -polyfit. If this
constraint is not met, you will receive a 'DOF Constraint Violation' Error.

CHOOSING THE SEARCH TERMINATION CRITERIA

The search is terminated when either the maximum number of iterations
has been reached or the maximum search time has been reached. It is
impossible to determine how many iterations to search over because
it is not possible to globally determine what the best schedule is nor
would it be possible to determine how long it would take a random search
to get there.

サーチは繰り返しの最大値に到達した時，あるいは最大のサーチ時間に到達したときに停止する．サーチが終わるまでどのくらい繰り返すかを決定することが不可欠である．なぜならば，何が最適なスケジュールであるかという全体的な決定ができず，目的を達成する(get there)ためのランダムサーチをするためにどのくらいの長さが必要か決定することもできないからである．

That said, there are some rules of thumb that can be followed,
the most basic being that if a 'large' number of schedules have been
searched and the best cost has not changed 'much' in a 'long time', then
you are done.

つまり，以下のような親指（？ thumb)のいくつかのルールがある．もっともベーシックなものは，スケジュールの'large'な数をサーチしたとき，最適なコストは'long time'に'much'を変化しない．それゆえ，あなたはそうしたほうが良い．

Of course, you still have to define 'large', 'much', and
'long time'. The summary file can help with this. In particular, there is a
line with the number of iterations since the last substitution (ie,
the number of iterations since one of the best nKeep schedules changed).
This can be used to judge how long a 'long time' is. The same information
can be extracted from the NthIter column of the summary table. At a minimum
let it run for 10000 iterations.

もちろん，あなたは'large' 'much'および'long time'を定義するべきである．summary fileは，これを助ける．特に，最後の代入(substitution，つまり，最適なnKeepスケジュールが変更されてからの繰り返しの数)からの繰り返し数のラインがある．これは，どのくらい長い'long time'が必要かを判定するのに有用である．同じ情報は，要約テーブルのNth Iter(N回目の繰り返し）行から取り出せる．10000回の繰り返しが最小数である．

PARADIGM FILE FORMAT
The schedules will be saved in 'paradigm file' format. This format has four
columns: time, numeric event id, event duration, and event label. A numeric
id of 0 indicates the Null Stimulus.

スケジュールは，'paradigm file'フォーマットに保存される．このフォーマットは，４行からなる．
時間，数値イベントID，イベントの持続時間，イベントラベルである．数値イベントIDの０は，Null刺激を指す．

BUGS

Also see the Optseq Home page at http://surfer.nmr.mgh.harvard.edu/optseq

The vrfavgstd cost function does not work properly if the number of reps
is different for different event types. A prescan window should also be
specified

The ideal counter-balance matrix reported in the summary file will be
for the nominal number of reps when the user has selected to optimize
over the number of reps making comparisons between the actual and
ideal inappropriate (the FOCB error reported for each will be correct
however).

vrfavgstdコスト関数は，異なるイベントタイプで反復回数が異なる場合はうまく働かないことがある．prescan窓も，特定されなくてはならない．

ユーザが実際と理想の間の比較をした繰り返し数の最適を選択した場合，summary fileに報告される 理想のカウンターバランスマトリクスは，名目上の(nominal)繰り返し数である(しかしながら，FOCBエラーは各々が正しいだろうと報告する）．

BUG REPORTING

optseq2 is offered with no guarantees and with no obligation or implication
that it will be supported in any way. Having said that, you can send
bug reports/questions to: [e-mail]. You must
include the following information: (1) optseq2 version, (2) computer
operating system, (3) command-line, (4) description of the problem, and
(5) log and/or summary files.

バグリポートは，[e-mail]までだそうですよ．
optseq2のバージョン，コンピュータのOS，コマンドライン，問題の記述，ログと／あるいはsummary filesを添えなくてはならない，とのこと．

AUTHOR

optseq2 was written by Douglas N. Greve in the Summber of '02.

REFERENCES

Dale, A.M., Greve, D.N., and Burock, M.A. (1999) Optimal Stimulus
equences for Event-Related fMRI. 5th International Conference on
Functional Mapping of the Human Brain. Duesseldorf, Germany. June
11-16.

Dale, A.M. (1999). Optimal experimental design for event-related
fMRI. Human Brain Mapping 8:109-114.