11institutetext: Precision Methodologies, LLC, Wayland MA 01778, USA
11email<EMAIL_ADDRESS>
https://precisionmethods.guru 22institutetext: 22email<EMAIL_ADDRESS>
https://www.metalevel.at

# An Executable Specification of Oncology Dose-Escalation Protocols with
Prolog

David C. Norris 11 Markus Triska 22

###### Abstract

We present, as a pure Prolog program, the first executable specification of
the 3 + 3 dose-escalation protocol commonly used in early-phase oncology drug
development. In this program, the imperative operations of the protocol emerge
as consequences of clinically meaningful anticipatory-regret scenarios that
are declared as CLP($\mathbb{Z}$) constraints. This ‘regret-constrained’ (RC)
specification yields a robust formulation which can be used to prove
clinically meaningful safety and liveness properties of the protocol before
incorporating it into a trial, and then as an on-line decision support system
while the trial is underway. Our RC specification also readily accommodates
certain pragmatic modifications to trial enrollment which severely strain
traditionally imperative formulations. The features of modern Prolog systems
let us describe the 3 + 3 protocol with a short and general program that has
desirable algebraic properties and can therefore be used, tested and reasoned
about in several different ways.

###### Keywords:

System safety Formal system verification Clinical trials Dose finding.

##  1 Introduction

Clinical development of a new cancer drug for human use typically follows a
3-phase process. Phase 1 trials, which concern us here, try a drug for the
first time in humans, exploring relations between dosing and toxicity which
preclinical animal experimentation cannot adequately characterize. Subsequent
phase 2 and 3 trials address efficacy, and are premised on dosing
recommendations yielded by phase 1. Because cancer drugs’ toxicity usually
becomes evident on a shorter time-scale than their efficacy, phase 1 cancer
trials often adopt a maximum tolerated dose (MTD) heuristic which calibrates
dosing to produce mild-to-moderate toxicity. While it has long been recognized
that MTD varies from one patient to another [1], it remains an almost
universal practice in phase 1 oncology trials to define ‘tolerability’ in
population terms, according to what proportion of patients experience a
severe, ‘dose-limiting’ toxicity (DLT).

##  2 Prolog prerequisites and compatibility considerations

Our key contribution, described in the following sections, is the
specification of a dose-escalation protocol in the form of an executable
Prolog program. We have chosen Prolog as implementation language for several
reasons: First, Prolog is highly suited for this application, allowing us to
achieve a general and efficient program with a small code-base. Second, Prolog
remains the best-known logic programming language, continuing to be taught at
universities around the world. This makes our specification immediately
accessible to a substantial number of programmers. Third, a number of
different Prolog implementations exist, and yet are mutually compatible to
varying degrees thanks to the existence of an ISO standard that defines their
common syntactic and semantic features.

Standards are of great importance in the medical sector and play a significant
role in procurement decisions, resolution of legal disputes, warranty
questions, and the preparation of teaching material. It is to be expected that
the use of an ISO-standardized programming language will enable the broadest
possible adoption of our approach in such a safety-critical application area.
For these reasons, we are using Scryer Prolog for our application. Scryer
Prolog is a modern Prolog system written in Rust that aims for strict
conformance to the Prolog ISO standard and satisfies all syntactic conformity
tests given in https://www.complang.tuwien.ac.at/ulrich/iso-
prolog/conformity_testing. It is freely available from: https://www.scryer.pl.
The queries we show are executed with version 0.9.3.

A moderate knowledge of Prolog is required to fully understand the code
presented here. We are using only basic Prolog predicates, and features from
the following additional libraries that are available in Scryer Prolog and
also for several other Prolog systems:

    :- use_module(library(lists)).

Commonly known relations over lists, such as length/2 and maplist/N.

    :- use_module(library(clpz)).

Declarative integer arithmetic, with a monotonic execution mode requiring that
all logic variables standing for concrete integers be wrapped with the
dedicated functor (#)/1. We use CLP($\mathbb{Z}$) constraints such as (#=)/2
and (#>)/2 to denote the respective relations between integer expressions,
allowing for very general definitions.

    :- use_module(library(reif)).

This library provides the meta-predicates if_/3 and tfilter/3 as described in
[5].

    :- use_module(library(dcgs)).

Definite clause grammars (DCGs) which are available in virtually all Prolog
systems. We are using this built-in grammar mechanism to describe sequences of
events. The nonterminal ... //0 means any sequence.

    :- use_module(library(error)).

This library provides sound type tests. If a term is not sufficiently
instantiated to decide its type, an instantiation error is raised to prevent
incorrect failure in cases where a more specific instantiation would yield a
solution.

    :- use_module(library(si)).

“si” stands for sufficiently instantiated, and also for sound inference. This
library provides additional sound type tests.

    :- use_module(library(lambda)).

We use this higher-order construct to conveniently project away uninteresting
answer substitutions in toplevel interactions, and also to define anonymous
auxiliary predicates that do not warrant a standalone definition or dedicated
name.

    :- initialization(assertz(clpz:monotonic)).

We run our application in the monotonic execution mode to ensure that all
admissible cases are taken into account, and consequently use for example the
term #X to denote a logic variable X that stands for a concrete integer.

We provide a collection of texts that explain these language features in more
detail at https://www.metalevel.at/prolog. These language features are
explained in more detail at https://www.scryer.pl and the resources it links
to.

The Prolog code we present in the following sections is designed to run with
all conforming Prolog systems where the above provisions are present.

##  3 Dose-escalation trials

Participants in phase 1 oncology studies are typically patients with cancer
for whom standard treatments have stopped working or do not exist. These
patients enroll to pursue an experimental treatment with therapeutic intent
[9] in the face of unknown efficacy and great uncertainty about how toxicities
may manifest and at what doses.

The required therapeutic balance between tolerability and efficacy is
typically sought in dose-escalation trials that enroll patients serially into
an escalating sequence of pre-specified doses. Small cohorts of 1–3 patients
are enrolled together, all assigned to the same dose level. Although we will
demonstrate a pragmatically important generalization to variable cohort sizes,
initially we specify uniform cohorts of size 3.

    allowed_cohort_sizes([3]).

Whereas a complete trial protocol will specify complex clinical grading
systems for assessing a broad array of distinct toxicities, for dose-
escalation purposes each patient’s experienced toxicity gets tallied in binary
terms, according to whether the toxicity is severe enough to be deemed a
‘dose-limiting toxicity’ (DLT). Eliding the time which must elapse from dosing
to toxicity assessment, at any given moment each dose will be characterized by
a cumulative toxicity tally T/N denoting that a DLT has occurred in `T` out of
the `N` participants enrolled at that dose:

    valid_tally(T/N) :- valid_denom(N), 0 #=< #T, #T #=< N.

Rapid progress being imperative in cancer drug development, phase 1 trials are
typically designed to yield a recommended phase 2 dose without enrolling a
large number of patients. Thus, for phase 1 purposes, the maximum enrollment
deemed necessary to characterize any given dose may be quite modest:

    valid_denom(N) :- N in 0..6.

If a dose has current tally T0/N0, then enrollment of a new cohort at this
same dose will yield a new tally T/N in the expected way:

    enroll(T0/N0, T/N) :-
        allowed_cohort_sizes(Cs),
        member(Nnew, Cs),
        #N #= #N0 + #Nnew,
        valid_denom(N),
        Tnew in 0..Nnew, indomain(Tnew),
        #T #= #T0 + #Tnew.

The dose-escalation state at any moment consists of accumulated toxicity
tallies at each of an ascending sequence of up to 8 doses (a pragmatically
relevant maximum rarely exceeded by actual dose-escalation trials), together
with an index into this sequence identifying a ‘current dose’. We represent
this by a pair of tally-lists, the left-hand `Ls` listing lower doses in
descending dose order with the current dose at its head, and the right-hand
`Hs` listing higher doses in ascending order with the next-higher dose at its
head.

    valid_state(Ls - Hs) :-
        append(Ls, Hs, Ds),
        length(Ds, ND), ND in 1..8,
        maplist(valid_tally, Ds).

    state_tallies(Ls-Hs, Qs) :-
        valid_state(Ls-Hs),
        reverse(Ls, Js),
        append(Js, Hs, Qs).

As tallies accumulate at the various dose levels, the ‘current dose level’
(into which the next cohort is to be enrolled) may be updated by one of 3
possible dose-escalation decisions: escalate, stay and de-escalate:

    state0_decision_state(Ls - [H0|Hs], esc, [H|Ls] - Hs) :-
        valid_state(Ls - [H0|Hs]),
        enroll(H0, H).
    state0_decision_state([L0|Ls] - Hs, sta, [L|Ls] - Hs) :-
        valid_state([L0|Ls] - Hs),
        enroll(L0, L).
    state0_decision_state([L,D0|Ls] - Hs, des, [D|Ls] - [L|Hs]) :-
        valid_state([L,D0|Ls] - Hs),
        enroll(D0, D).

The very data structures in which we have declared the basic template of a
dose-escalation protocol already limit which dose-escalation decisions are
feasible at any point in the trial. One cannot, for instance, escalate above
the highest dose; nor can one de-escalate from the lowest:

    state0_decision_infeasible_t(_-[], esc, true).
    state0_decision_infeasible_t([_]-_, des, true).

We encode maximum dose-wise enrollment also as a matter of feasibility:

    state0_decision_infeasible_t(_-[_/N|_], esc, true)   :- #N #>= 6.
    state0_decision_infeasible_t([_/N|_]-_, sta, true)   :- #N #>= 6.
    state0_decision_infeasible_t([_,_/N|_]-_, des, true) :- #N #>= 6.

The `false` clauses of `state0_decision_infeasible_t/3` are obtained by
demonstrating that at least one valid subsequent state does exist:

    state0_decision_infeasible_t(S0, E, false) :-
        member(E, [esc,sta,des]),
        Goal = exists_subsequent_state(S0, E),
        once((term_si(Goal), Goal)).

    exists_subsequent_state(S0, E) :-
        state0_decision_state(S0, E, _).

The existential quantification performed here uses the (generally, impure)
predicate `once/1` to avoid redundant solutions for greater efficiency, yet it
does so in a safe way: `term_si/1` ensures that `once/1` is only called when
its argument is ground and can therefore yield at most one solution.
Importantly, `term_si/1` yields an instantiation error if its argument is not
ground, differing crucially from the standard predicate `ground/1`, which can
fail silently even in cases that admit solutions by further instantiations.
Therefore our use of `once/1` never incurs silent loss of solutions.

In addition to the `esc`, `sta` and `des` decisions which permit the trial to
continue, there is also the possibility of stopping with a dose
recommendation. The rules which relate observed toxicity tallies to these
decisions constitute the design of a dose-escalation protocol.

##  4 The traditional rules of 3 + 3 dose-escalation

The conventional, and still most prevalent, dose-escalation design is the 3 +
3. For an account of this design in practice, we are indebted to [4], quoted
at length in Figure 1. A similar description from [8] is given in Figure 2.

> “Although there is no canonical ‘standard method’, we present the design
> that we have most often encountered, which is used almost universally with
> minor variations. First, there is a precise [clinical] definition in the
> protocol of what is considered dose-limiting toxicity (DLT); it may differ
> in different settings. The dose levels are fixed in advance, with the first
> patients treated at dose level 1. Initially, one treats 3 patients at a
> level. If 0 out of 3 patients experiences DLT, one proceeds to the next
> higher level with a cohort of 3 patients. If 1 out of 3 patients experiences
> DLT, treat an additional 3 patients at the same dose level. If 1 out of 6
> patients experiences DLT at a level, the dose escalates for the next cohort
> of patients. If $\geq 2$ out of 6 patients experience DLT, or $\geq 2$ out
> of 3 patients experience DLT in the initial cohort treated at a dose level,
> then one has exceeded the MTD. Some investigations will, at this point,
> declare the previous dose level as the MTD, but a more common requirement is
> to have 6 patients treated at the MTD (if it is higher than level 0). To
> satisfy this requirement, one would treat another 3 patients at this
> previous dose level if there were only 3 already treated. The MTD is then
> defined as the highest dose level $(\geq 1)$ in which 6 patients have been
> treated with $\leq 1$ instance of DLT, or dose level 0 if there were $\geq
> 2$ instances of DLT at dose level 1.”

Figure 1: Natural-language description of the 3 + 3 dose-escalation protocol,
from [4]. Our specification implements the “more common requirement” described
here.

> “In the traditional 3 + 3, phase I cancer trial design, a minimum of three
> participants are studied at each dose level. If none of these three
> participants experience a DLT, a subsequent three participants are enrolled
> onto the next highest dose level. If one of three participants at a dose
> level experiences a DLT, up to three more participants are enrolled. When a
> DLT is observed in at least two participants in a cohort of three to six,
> the MTD is [regarded as having been] exceeded and an additional three
> participants (up to a total of six) are treated at the next lower dose
> level. The MTD is defined as the dose level at which none or one of six
> participants (0% to 17%) experience a DLT, when at least two of three to six
> participants (33% to 67%) experience a DLT at the next highest dose.”

Figure 2: Natural-language description of the 3 + 3 dose-escalation protocol,
from [8]. The “more common” variant of [4] appears to be taken for granted
here.

##  5 Indeterminacies in dose escalation

Before we can reconstruct the aforementioned rules, we must appreciate certain
essential indeterminacies inherent to dose escalation.

Whereas a dose-escalation decision determines the dose at which the next
cohort of trial participants will enroll, it does not fully determine the
ensuing trial state. This is because there is a nonzero probability of DLT in
any participant who receives a nonzero dose. Thus, the toxicity tally in a
cohort of size `C` could turn out as any of the `C+1` possibilities
`[C/C,...,0/C]`:

    enroll_tallies(C, Qs) :-
        n_countdown(C, Ts),
        maplist(\T^(=(T/C)), Ts, Qs).

    n_countdown(N, [N|Ns]) :- #N #> 0, #Nminus1 #= N - 1,
                              n_countdown(Nminus1, Ns).
    n_countdown(0, [0]).

Moreover, under an important generalization to be explored in Section 12, the
actual number of patients who will be available to enroll after a dose-
escalation decision may itself be indeterminate, drawn from a list `[C|Cs]` of
length $\geq 2$:

    enrollments_tallies([C|Cs], Qs) :-
        enroll_tallies(C, Q0s),
        append(Q0s, Q1s, Qs),
        enrollments_tallies(Cs, Q1s).
    enrollments_tallies([], []).

Thus, the decision to enroll a new cohort into a dose level that already has a
`T0/N0` toxicity tally gives rise to multiple possible outcome `Tallies`:

    tally0_tallies(T0/N0, Tallies) :-
        valid_tally(T0/N0),
        allowed_cohort_sizes(Cs),
        enrollments_tallies(Cs, Qs),
        maplist(\Qnew^Q^(Qnew=Tnew/Nnew,
                         #T #= T0 + Tnew,
                         #N #= N0 + Nnew, Q=T/N),
                Qs, Tallies).

##  6 Regret-constrained specification of $\mathbf{3+3}$ designs

We can now introduce what we call regret-constrained protocol specifications,
which ground dose escalation in specified events deemed to induce clinically
meaningful decisional regret, thereby constraining what dose-escalation
decisions are permissible in the course of a trial. This renders explicit a
linkage to underlying aims and clinical motivations left implicit by customary
treatments of dose-escalation via painstaking procedural tabulations. We will
exhibit a Prolog program that, on the basis of a few suitably calibrated yet
clinically intuitive regret-constraints, behaves consistently with the
natural-language 3 + 3 design rules quoted above.

To this end, we state that we `regret` a `Decision` when it yields some
undesirable `TallyHistory`, which for the purpose of modeling the 3 + 3 design
needs to take into account only the resulting tally `T/N` and the immediately
preceding tally `T0/N0`:

    state0_decision_histories(S0, E, Hs) :-
        (   E = esc,
            S0 = [T0/N0|_] - [Told/Nold|_]
        ;   E = sta,
            S0 = [T0/N0|_] - _,
            Told = T0, Nold = N0
        ;   E = des,
            S0 = [T0/N0, Told/Nold | _] - _
        ),
        tally0_tallies(Told/Nold, Qs),
        maplist(\Q^(=([Q, T0/N0])), Qs, Hs).

###  6.1 Specific, clinically-motivated regrets

It is always possible that, after an esc decision, all three patients in the
new cohort will experience DLTs. Although such an outcome is of course
regrettable, investigators need not regret their decision to escalate if they
feel it was justified by a low enough toxicity observed at the previous dose.
The judgment as to what constitutes sufficiently low toxicity to justify
escalation will generally depend on clinical context. The 3 + 3 design embeds
a judgment equating this condition with N0 $\geq 3$ and T0/N0 $\leq
1/6\in\mathbb{Q}$. Accordingly, we regret escalation precisely when this
justification is absent:

    decision_q0_q_regret(esc, T0/N0, _, #\ ( #N0 #>= 3 #/\ #T0 * 6 #=< N0 )).

The literature makes equally clear that overly cautious dose-escalation risks
exposing too many participants to subtherapeutic dosing [7]. Thus, decisional
regret can also serve to constrain des decisions. The 3 + 3 design is
consistent with a judgment regretting de-escalating from a moderately toxic
tally $\\{\mathtt{T0}\leq 1,\mathtt{N0}\geq 3\\}$ upon appreciating very low
net toxicity T/N $<1/6$ at the new lower dose:

    decision_q0_q_regret(des, T0/N0, T/N,
                         ( #T0 #=< 1 #/\ #N0 #>= 3 ) #/\
                         ( #N #> 0 #/\ #T * 6 #< #N )
                        ).

The literature also exhibits ample evidence of interest in net properties of
dose-escalation trials ex post facto [3]. A 3 + 3 trial run without protocol
violations can never record more than 4 DLTs at any single dose level. We
express this fact by positing a regret for any decision that results in $\geq
5$ toxicities at any dose level, regardless of preceding tally history:

    decision_q0_q_regret(esc, _, T/_, #T #>= 5).
    decision_q0_q_regret(sta, _, T/_, #T #>= 5).
    decision_q0_q_regret(des, _, T/_, #T #>= 5).

Prolog has allowed us to state these regrets in a very general form: We regret
any situation that satisfies the given constraints, even if nothing else is
known about it. Indeed, we capture an infinite set of concrete tallies with
each of these clauses of `decision_q0_q_regret/4`.

###  6.2 Reification of regret

To achieve efficiency while retaining the desired generality of our code with
the constructs from [5], we reify these declared regrets in a predicate,
`regret_t/3`. We ensure the `true` and `false` branches of `regret_t/3` are
constructed without copy-and-paste error by employing the `term_expansion/2`
mechanism to generate the `false` branch of `regret_t/3` as the constructive
negation of all `true` clauses, using the reification mechanism of
`library(clpz)`:

    % Generate e_vars_disjunction _at compile time_.
    :- dynamic(e_vars_disjunction/3).
    term_expansion(generate_clauses, Clauses) :-
        findall(e_vars_disjunction(E, Vars, Disjunction),
                (   member(E, [esc,sta,des]),
                    findall(Vs-RC,
                            (   decision_q0_q_regret(E, T0/N0, T/N, RC),
                                Vs = [N0,N,T0,T]
                            ), VsRCs),
                    pairs_keys_values(VsRCs, Vs, RCs),
                    maplist(=(Vars), Vs),
                    foldl(\X^Disj0^Disj^(Disj=(Disj0#\/X)), RCs, 0#=1, Disjunction)
                ),
                Clauses).
    generate_clauses.

    regret_t(E, H, Truth)  :-
        e_h_disjunction(E, H, Disjunction),
        Disjunction #<==> #B,
        b_t(B, Truth).

    b_t(0, false).
    b_t(1, true).

    e_h_disjunction(E, H, Disjunction) :-
        H = [T/N, T0/N0],
        e_vars_disjunction(E, [N0,N,T0,T], Disjunction).

The `e_vars_disjunction/3` clauses thus generated are:

    ?- listing(e_vars_disjunction/3).
     e_vars_disjunction(esc,[A,B,C,D],0#=1#\/ #\ (#A#>=3#/\ #C*6#=<A)#\/ #D#>=5).
     e_vars_disjunction(sta,[A,B,C,D],0#=1#\/ #D#>=5).
     e_vars_disjunction(des,[A,B,C,D],
                      0#=1#\/ #C#=<1#/\ #A#>=3#/\(#B#>0#/\ #D*6#< #B)#\/ #D#>=5).
        true.

###  6.3 Anticipatory regret

Whereas `regret_t/3` looks backwards to already-realized toxicity tallies, it
is also possible to anticipate all possible `Regrets`:

    state0_decision_regrets(S0, E, Regrets) :-
        state0_decision_histories(S0, E, Hs),
        tfilter(regret_t(E), Hs, Regrets).

A dose-escalation decision is `regrettable` iff the list of possible `Regrets`
is nonempty:

    state0_decision_regrettable_t(S0, E, false) :-
        state0_decision_regrets(S0, E, []).
    state0_decision_regrettable_t(S0, E, true) :-
        state0_decision_regrets(S0, E, [_|_]).

By conducting dose escalation to avert anticipated regret, resolving
degenerate choices by therapeutically motivated preference relations ${\tt
esc}\succ{\tt sta}\succ{\tt des}$ that favor exploration of higher doses, we
obtain an effective protocol specification.

    state0_nextdecision(S0, E) :-
        if_((   state0_decision_infeasible_t(S0, esc)
            ;   state0_decision_regrettable_t(S0, esc)),
            if_((   state0_decision_infeasible_t(S0, sta)
                ;   state0_decision_regrettable_t(S0, sta)),
                if_((   state0_decision_infeasible_t(S0, des)
                    ;   state0_decision_regrettable_t(S0, des)),
                    E = stop,
                    E = des),
                E = sta),
            E = esc).

Finally, we obtain all possible trial paths using a DCG path//1 which
describes all paths of the trial from the current state S0:

    path(S0) --> { state0_nextdecision(S0, E),
                   state0_decision_state(S0, E, S) },
                 [E, S],
                 path(S).
    path(S0) --> { state0_nextdecision(S0, stop),
                   stopstate_rec(S0, Rec) },
                 [stop, recommend_dose(Rec)].
    path(recommend_dose(_)) --> [].

When none of the dose-escalation decisions [esc,sta,des] remains feasible, the
trial stops, yielding a dose recommendation. The relation between the final
state and this recommendation is specified by stopstate_rec/2:

    stopstate_rec([]-_, 0).
    stopstate_rec([T/N|TNs]-_, Rec) :-
            (   #T * 6 #> #N, length(TNs, Rec)
            ;   #T * 6 #=< #N, length([_|TNs], Rec)
            ).

##  7 Algebraic properties of our formulation

With the lone exception of `once/1`, which is guaranteed to be used in a safe
way as explained in Section 3, the resulting program consists exclusively of
monotonic Prolog constructs. Our program thus by construction provides
algebraic properties that we consider essential in this safety-critical
application area:

  * •

If an answer says that no (further) solutions exist to a query, then there are
truly no (further) solutions, no matter which additional constraints we add.
In other words, our program cannot be “tricked” into yielding solutions that
other queries deny.

  * •

The predicates of library(debug) can be used for declarative debugging of the
program itself.

  * •

Every query either shows all possible answers, or yields an instantiation
error if the query is not sufficiently instantiated.

  * •

Reordering any clauses or goals in the program can affect termination or the
existence of instantiation errors, but it does not change the set of described
solutions.

In addition, the Scryer Prolog toplevel always shows all pending constraints
and can therefore be used like a theorem prover: When a query succeeds
unconditionally, a solution is guaranteed to exist.

These properties ensure that our program constitutes a declarative
specification that can be queried, run and reasoned about in different ways,
and yields only correct results in all possible usage modes. The only possible
remaining source of logic errors is a mistake in the protocol formulation
itself.

##  8 Relation of our specification to natural-language descriptions

From this program, we can elicit concretely much of the meaning of the text in
Figure 1, which we exhibit for the case of ${\tt D}=3$ doses:

  * •

The dose levels are fixed in advance, with the first patients treated at dose
level 1.

  *     ?- setof(E^S1, Etc^(phrase(path([0/0]-[0/0,0/0]), [E, S1 | Etc])),
             Starts).
       Starts = [sta^([0/3]-[0/0,0/0]),sta^([1/3]-[0/0,0/0]),
                 sta^([2/3]-[0/0,0/0]),sta^([3/3]-[0/0,0/0])].

  * •

If 0 out of 3 patients experiences DLT, one proceeds to the next higher level
with a cohort of 3 patients.

  *     ?- setof(E, Path^Ls^H^Hs^(phrase(path([0/0]-[0/0,0/0]), Path),
                 phrase((..., [[0/3|Ls]-[H|Hs]], [E], ...), Path)), Es).
       Es = [esc].

  * •

If 1 out of 3 patients experiences DLT, treat an additional 3 patients at the
same dose level.

  *     ?- setof(E, Path^Ls^H^Hs^(phrase(path([0/0]-[0/0,0/0]), Path),
                 phrase((..., [[1/3|Ls]-[H|Hs]], [E], ...), Path)), Es).
       Es = [sta].

  * •

If 1 out of 6 patients experiences DLT at a level, the dose escalates for the
next cohort of patients.

  *     ?- setof(E, Path^Ls^H^Hs^(phrase(path([0/0]-[0/0,0/0]), Path),
                              H = 0/0,
                    phrase((...,[[1/6|Ls]-[H|Hs]],[E],...), Path)), Es).
       Es = [esc].

Notably, eliciting the intended meaning of the text in the last case required
positing that the next-higher dose `H` had not yet been enrolled. Without this
proviso, `stop` would also have been permissible.

From the decision cascade in the body of `state0_nextdecision/2` it is evident
that our formulation yields a unique decision in any concrete situation (with
ground `S0`); we therefore consider it a complete specification. The Appendix
includes a complete enumeration of all 46 paths for the ${\tt D}=2$ case,
easily checked vis-à-vis the text of Figure 1.

##  9 Verification of safety properties

The text of Figure 1 trends from language that is initially imperative, toward
declarative statements near the end. The latter reflect clinical
investigators’ intense interest in asserting safety properties for their
trials and (by extension) for the conclusions drawn from them. Informally, a
safety property states that bad things do not happen. For example, the “more
common requirement”

> to have 6 patients treated at the MTD (if it is higher than level 0)

expresses a concern to avoid recommending a dose on the strength of too little
experience.

Our executable specification exhibits safety properties expressed in Figure 1
through statements about ‘the MTD’. For example,

  * •

If $\geq 2$ out of 6 patients experience DLT, or $\geq 2$ out of 3 patients
experience DLT in the initial cohort treated at a dose level, then one has
exceeded the MTD.

  *     recommends_dose_exceeding_mtd             :-
       D in 1..8, indomain(D),       % For trials of up to D=8 doses
       InitD = [Q]-Qs, length([Q|Qs], D), % .. that start from the lowest dose
       maplist(=(0/0), [Q|Qs]),      % .. with no prior toxicity information,
       phrase(path(InitD), Path),    % does any Path exist
       phrase((..., [Ls-_], ...,     % .. on which a state Ls-_ appears,
               [recommend_dose(Rec)] % .. such that the recommended dose Rec
              ), Path),
       length(Ls,X), Rec #>= X,      % .. was at least the current dose X,
       Ls = [T/_|_], #T #> 1.        % .. yet X ‘exceeded MTD’ per protocol?
    %?- time(recommends_dose_exceeding_mtd).
    %@    % CPU time: 574.029s, 2_701_969_903 inferences
    %@    false. % This safety property is verified for trials of up to 8 doses.

Note that the featured statement effectively asserts a property of the
desirable dose recommendation (which it refers to as ‘the MTD’), namely that
it should be less than any dose at which $\geq 2$ toxicities have been
tallied.

##  10 Verification of liveness properties

Although clinical investigators’ keen attention to safety is more readily
apparent in the literature, any sensible dose-escalation design must also
guarantee liveness properties. Informally, liveness properties state that good
things do happen. One such property applicable to these trials is that they
yield a recommendation, and then immediately stop:

    trial_fails_to_conclude_with_unique_rec :-
       D in 1..8, indomain(D), length([Q|Qs], D), maplist(=(0/0), [Q|Qs]),
       phrase(path([Q]-Qs), Path),
       (   phrase((..., [recommend_dose(Rec)], [_], ...), Path)
       ;   \+ phrase((..., [recommend_dose(Rec)]), Path)
       ).
    %?- time(trial_fails_to_conclude_with_unique_rec).
    %@    % CPU time: 560.946s, 2_675_988_416 inferences
    %@    false. % All trials of up to 8 doses yield a recommendation, then stop.

##  11 Generality and versatility of the specification

The DCG introduced in Section 9 is remarkably general and versatile. It is an
executable specification of the sequences of events which may occur in the
trial, in the sense that it states what holds, and it can be used in multiple
modes. This generality allows us to answer a variety of questions with
comparatively simple queries. For example, in one specific mode, we can use
our specification as an ‘expert system’ that automatically determines what the
next decision should be at a point where we have reached the highest dose of a
${\tt D}=3$ trial, having recorded a 0/3 tally at each dose:

    ?- setof(E, Path^(phrase(path([0/0]-[0/0,0/0]), Path),
                      phrase((...,[[0/3,0/3,0/3]-[], E], ...), Path)), Es).
       Es = [sta].

We can as easily adopt a retrospective point of view, to ask what dose-
escalation decisions could have preceded this state:

    ?- setof(E0, Path^(phrase(path([0/0]-[0/0,0/0]), Path),
                       phrase((...,[E0, [0/3,0/3,0/3]-[]],...), Path)), E0s).
       E0s = [esc].

We are also able to look far ahead, anticipating all recommendations that
remain possible at any time in an ongoing trial. Having recorded tallies of
0/3, 0/3 and 2/6 at dose levels 1, 2 and 3 of a ${\tt D}=3$ trial, for
example:

    ?- setof(Rec, Path^(phrase(path([0/0]-[0/0,0/0]), Path),
                        phrase((..., [[2/6,0/3,0/3]-[]],
                                ..., [recommend_dose(Rec)]), Path)), Recs).
       Recs = [0,1,2]. % Only dose level 3 has been ruled out so far.

Finally, the DCG allows complete enumeration of all admissible trials:

    ?- J+\time((D = 8, length([Q|Qs], D), maplist(=(0/0), [Q|Qs]),
                setof(Path, phrase(path([Q]-Qs), Path), Paths),
                length(Paths, J))).
    %@    % CPU time: 337.638s, 1_573_175_565 inferences
    %@    J = 16138.

This capability can confer substantial benefits even on analyses of a
statistical nature. For example, [6] employs such enumeration to derive
statistical characterizations of 3 + 3 trials, exempt from Monte Carlo error.
The generality and versatility of our Prolog code enables more usage modes
than a procedural implementation can provide. We regard the run-times of our
program in all these modes as commensurate to the importance of reliable
guarantees in this domain, and therefore do not pursue any further performance
considerations in the present paper.

##  12 Flexibly accommodating protocol variations

As shown by the expansive tabulations in [8] and [2], when working within the
tradition of informal protocol specifications, much labor is needed to adapt
the typically lumpy cohorts of dose-escalation designs to trial enrollment
occurring as a rather fluid arrival process in real time. Our RC specification
framework, by contrast, shows promise for being readily adaptable to this
challenge.

If we recompile our program with an expanded set of possible cohort sizes,

    allowed_cohort_sizes([3,2,1]).

then, as the following query shows, this added flexibility renders the
protocol adequate to admit paths in which participants enroll either singly or
in pairs, rather than waiting for arrival of a third participant to complete
the traditional cohort of 3. Such just-in-time or ‘rolling’ [8] enrollment may
enable de-escalation decisions to occur sooner, avoiding dosing patients at
levels that are no longer viable dose recommendations. This improves safety,
and also accelerates progress of the trial.

    ?- phrase(path([0/3,0/3,0/3]-[]), [sta, [2/5,0/3,0/3]-[],
                                       des, [0/6,0/3]-[2/5],
                                       stop, recommend_dose(2)]).
       true % The above-described path is admissible.
    ;  ... .

##  13 Conclusion

Possibly the most essential aspect of our program’s declarativeness is its
generality. This quality has allowed us to examine our program in numerous
ways to probe comprehensively for various forms of error. We can investigate
individual predicates with general queries that expose their full meaning as
implemented, to check for departures from intended meaning. Yet the very same
program allows us to recapitulate the best available natural-language
description of the 3 + 3 protocol, and indeed in so doing to recognize
deficiencies in that description and correct them. Not only does this reduce
the likelihood that we have failed to model ‘the true’ 3 + 3 protocol, but it
gives us a claim to have definitively superseded the extant natural-language
descriptions.

The internal consistency of our program, on the other hand, derives from its
very construction using a pure monotonic subset of Prolog. This enables us to
trust `false` answers from queries that search for violations of safety and
liveness properties, rendering such answers guarantees.

####  13.0.1 Acknowledgements

We thank Ulrich Neumerkel and several anonymous reviewers for their valuable
comments.

####  13.0.2

The authors have no competing interests to declare that are relevant to the
content of this article. This work received no external funding.

## References

  * [1] Edler, L.: Statistical requirements of phase I studies. Onkologie 13(2), 90–95 (Apr 1990). https://doi.org/10.1159/000216733
  * [2] Frankel, P.H., Chung, V., Tuscano, J., Siddiqi, T., Sampath, S., Longmate, J., Groshen, S., Newman, E.M.: Model of a Queuing Approach for Patient Accrual in Phase 1 Oncology Studies. JAMA Network Open 3(5), e204787–e204787 (May 2020). https://doi.org/10.1001/jamanetworkopen.2020.4787, https://doi.org/10.1001/jamanetworkopen.2020.4787
  * [3] Italiano, A., Massard, C., Bahleda, R., Vataire, A.L., Deutsch, E., Magné, N., Pignon, J.P., Vassal, G., Armand, J.P., Soria, J.C.: Treatment outcome and survival in participants of phase I oncology trials carried out from 2003 to 2006 at Institut Gustave Roussy. Annals of Oncology: Official Journal of the European Society for Medical Oncology 19(4), 787–792 (Apr 2008). https://doi.org/10.1093/annonc/mdm548
  * [4] Korn, E.L., Midthune, D., Chen, T.T., Rubinstein, L.V., Christian, M.C., Simon, R.M.: A comparison of two phase I trial designs. Statistics in Medicine 13(18), 1799–1806 (Sep 1994). https://doi.org/10.1002/sim.4780131802, http://doi.wiley.com/10.1002/sim.4780131802
  * [5] Neumerkel, U., Kral, S.: Indexing dif/2. CoRR abs/1607.01590 (2016), http://arxiv.org/abs/1607.01590
  * [6] Norris, D.C.: What Were They Thinking? Pharmacologic priors implicit in a choice of 3+3 dose-escalation design. arXiv:2012.05301 [stat.ME] (Dec 2020), https://arxiv.org/abs/2012.05301
  * [7] Simon, R., Freidlin, B., Rubinstein, L., Arbuck, S.G., Collins, J., Christian, M.C.: Accelerated titration designs for phase I clinical trials in oncology. Journal of the National Cancer Institute 89(15), 1138–1147 (Aug 1997). https://doi.org/10.1093/jnci/89.15.1138
  * [8] Skolnik, J.M., Barrett, J.S., Jayaraman, B., Patel, D., Adamson, P.C.: Shortening the Timeline of Pediatric Phase I Trials: The Rolling Six Design. Journal of Clinical Oncology 26(2), 190–195 (Jan 2008). https://doi.org/10.1200/JCO.2007.12.7712, http://ascopubs.org/doi/full/10.1200/JCO.2007.12.7712
  * [9] Weber, J.S., Levit, L.A., Adamson, P.C., Bruinooge, S.S., Burris, H.A., Carducci, M.A., Dicker, A.P., Gönen, M., Keefe, S.M., Postow, M.A., Thompson, M.A., Waterhouse, D.M., Weiner, S.L., Schuchter, L.M.: Reaffirming and Clarifying the American Society of Clinical Oncology’s Policy Statement on the Critical Role of Phase I Trials in Cancer Research and Treatment. Journal of Clinical Oncology 35(2), 139–140 (Nov 2016). https://doi.org/10.1200/JCO.2016.70.4692, http://ascopubs.org/doi/full/10.1200/JCO.2016.70.4692

## Appendix

A complete listing of all 46 paths of the 3 + 3 design for the ${\tt D}=2$
case. These may be checked one-by-one against the text of Figure 1.

    :- use_module(library(format)).
    ?- J+\(setof(Path, (phrase(path([0/0]-[0/0]), Path)), Paths)
          , maplist(portray_clause, Paths), length(Paths, J)).
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[0/6,0/3]-[],stop,recommend_dose(2)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[1/6,0/3]-[],stop,recommend_dose(2)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[2/6,0/3]-[],des,[0/6]-[2/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[2/6,0/3]-[],des,[1/6]-[2/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[2/6,0/3]-[],des,[2/6]-[2/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[2/6,0/3]-[],des,[3/6]-[2/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[3/6,0/3]-[],des,[0/6]-[3/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[3/6,0/3]-[],des,[1/6]-[3/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[3/6,0/3]-[],des,[2/6]-[3/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[0/3,0/3]-[],sta,[3/6,0/3]-[],des,[3/6]-[3/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[1/6,0/3]-[],stop,recommend_dose(2)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[2/6,0/3]-[],des,[0/6]-[2/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[2/6,0/3]-[],des,[1/6]-[2/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[2/6,0/3]-[],des,[2/6]-[2/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[2/6,0/3]-[],des,[3/6]-[2/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[3/6,0/3]-[],des,[0/6]-[3/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[3/6,0/3]-[],des,[1/6]-[3/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[3/6,0/3]-[],des,[2/6]-[3/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[3/6,0/3]-[],des,[3/6]-[3/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[4/6,0/3]-[],des,[0/6]-[4/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[4/6,0/3]-[],des,[1/6]-[4/6],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[4/6,0/3]-[],des,[2/6]-[4/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[1/3,0/3]-[],sta,[4/6,0/3]-[],des,[3/6]-[4/6],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[2/3,0/3]-[],des,[0/6]-[2/3],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[2/3,0/3]-[],des,[1/6]-[2/3],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[2/3,0/3]-[],des,[2/6]-[2/3],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[2/3,0/3]-[],des,[3/6]-[2/3],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[3/3,0/3]-[],des,[0/6]-[3/3],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[3/3,0/3]-[],des,[1/6]-[3/3],stop,recommend_dose(1)].
    [sta,[0/3]-[0/0],esc,[3/3,0/3]-[],des,[2/6]-[3/3],stop,recommend_dose(0)].
    [sta,[0/3]-[0/0],esc,[3/3,0/3]-[],des,[3/6]-[3/3],stop,recommend_dose(0)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[0/3,1/6]-[],sta,[0/6,1/6]-[],stop,recommend_dose(2)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[0/3,1/6]-[],sta,[1/6,1/6]-[],stop,recommend_dose(2)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[0/3,1/6]-[],sta,[2/6,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[0/3,1/6]-[],sta,[3/6,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[1/3,1/6]-[],sta,[1/6,1/6]-[],stop,recommend_dose(2)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[1/3,1/6]-[],sta,[2/6,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[1/3,1/6]-[],sta,[3/6,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[1/3,1/6]-[],sta,[4/6,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[2/3,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[1/6]-[0/0],esc,[3/3,1/6]-[],stop,recommend_dose(1)].
    [sta,[1/3]-[0/0],sta,[2/6]-[0/0],stop,recommend_dose(0)].
    [sta,[1/3]-[0/0],sta,[3/6]-[0/0],stop,recommend_dose(0)].
    [sta,[1/3]-[0/0],sta,[4/6]-[0/0],stop,recommend_dose(0)].
    [sta,[2/3]-[0/0],stop,recommend_dose(0)].
    [sta,[3/3]-[0/0],stop,recommend_dose(0)].
       J = 46.


# Unsupervised video summarization framework using keyframe extraction and
video skimming

Shruti Jadon This work has been done as part of 670 Computer Vision Coursework
at UMass Amherst. College of Information and Computer Science
University of Massachusetts
Amherst, MA 01002
Email<EMAIL_ADDRESS>Mahmood Jasim  College of Information and Computer
Science
University of Massachusetts
Amherst, MA 01002
Email<EMAIL_ADDRESS>
###### Abstract

Video is one of the robust sources of information and the consumption of
online and offline videos has reached an unprecedented level in the last few
years. A fundamental challenge of extracting information from videos is a
viewer has to go through the complete video to understand the context, as
opposed to an image where the viewer can extract information from a single
frame. Apart from context understanding, it almost impossible to create a
universal summarized video for everyone, as everyone has their own bias of
keyframe, e.g; In a soccer game, a coach person might consider those frames
which consist of information on player placement, techniques, etc; however, a
person with less knowledge about a soccer game, will focus more on frames
which consist of goals and score-board. Therefore, if we were to tackle
problem video summarization through a supervised learning path, it will
require extensive personalized labeling of data. In this paper, we attempt to
solve video summarization through unsupervised learning by employing
traditional vision-based algorithmic methodologies for accurate feature
extraction from video frames. We have also proposed a deep learning-based
feature extraction followed by multiple clustering methods to find an
effective way of summarizing a video by interesting key-frame extraction. We
have compared the performance of these approaches on the SumMe dataset and
showcased that using deep learning-based feature extraction has been proven to
perform better in case of dynamic viewpoint videos.

###### Index Terms:

Video Summarization, Vision, Deep Learning.

##  I Introduction

Following the advances of efficient data storage and streaming technologies,
videos have become arguably the primary source of information in today’s
social media-heavy culture and society. Video streaming sites like YouTube are
quickly replacing the traditional news and media sharing methods, whom,
themselves are forced to adapt the trend of posting videos instead of written
articles to convey stories, news and information. This abundance of videos
brings forth new challenges of developing an efficient way to extract the
subject matter of the videos in question. It would be frustrating,
inefficient, unintelligent and downright impossible to watch all movies
thoroughly and catalog them according to their categories and subject matter,
which is extremely important when searching for a specific video. Currently,
this categorization is dependent on the tags, metadata, titles etc., provided
by the video uploaders. However, they are highly personalized and unreliable
in application. Hence, a better way is required to create a summarized
representation of the video that is easily comprehensible in a short amount of
time. This is an open research problem in a multitude of fields including
information retrieval, networking and computer vision.

Video Summarization is the process of compacting a video down to only
important components in the video. The process is shown in Fig 1. This compact
representation is useful in retrieving the desired videos from a large video
library. A summarized video must have the following properties:

  * •

It must contain the high priority entities and events from the video.

  * •

The summary should be free of repetition and redundancy.

Failure to exclude these components might lead to misinterpretation of the
video from its summarized version. A summary of video also varies from person
to person, so a supervised video summarization can be seen as personalized
recommendation approach, but it requires extensive amount of data labeling by
a person and yet the trained model isn’t a generalized model among mass.

Figure 1: The process of video summarization. N number of frames in the video
is summarized to M number of frames where M is far smaller than N.

Various approaches have been taken to solve this problem by different
researchers. Some of most prominent approaches include keyframe Extraction
using Visual Features [1] [2] and Video Skimming [3],[4]. In this paper, we
will be exploring a generalized video summarization approach through
unsupervised keyframe extraction. We propose a framework to extract vision-
based keyframes and use them to create summarized videos with help of
clustering and video skimming. We have used the SumMe dataset [5] for our
experiments. Our key contributions include suggesting a new unsupervised
framework for video summarization. We have first extracted features on basis
of traditional computer vision filters and RESNET16 trained on image net, and
then used these extracted features for clustering to obtain keyframes. After
chosing the keyframes, we just skimmed the video by adding 1.5 second worth of
video around it.

The rest of this paper is organized as follows. The related research is
presented in section II, followed by our approach in section III. We present
our experimental results is section IV. The paper is concluded with
discussions and future goals in section V. Our code is available at
https://github.com/shruti-jadon/Video-Summarization-using-keyframe-Extraction-
and-Video-Skimming

##  II Related Research

The most difficult challenge of video summarization is determining and
separating the important content from the unimportant content. The important
content can be classified based on low level features like texture [6], shape
[7] or motion [8]. The frames containing these important information are
bundled together to create the summary. This manner of finding key information
from static frames is called keyframe extraction. These methods are used
dominantly to extract a static summary of the video. Some of the most popular
keyframe extraction methods include [9], [10]. These methods use low level
features and dissimilarity detection with clustering methods to extract static
keyframes from a video. The clustering methods are used to extract the extract
features that are worthwhile to be in the summary while uninteresting frames
rich with low level features are discarded. Different clustering methods have
been used by researchers to find interesting frames [9]. Some methods use web-
based image priors to extract the keyframes, for example, [11], [12].

While extracting static keyframes to compile a summary of the video is
effective, the summary itself might not be pleasant to watch and analyze by
humans as it will be discontinuous and with abrupt cuts and frame skips. This
can be solved by video skimming which appears more continuous and will less
abrupt frame changes and cuts. The process is more complex than simple
keyframe extraction, however, because a continuous flow of semantic
information [13] and relevance is needed to be maintained for videos skimming.
Some of the video skimming approaches include [1], which utilizes the motion
of the camera to extract important information and calculates the inter-frame
dissimilarities from the low level features to extract the interesting
components from the video. A simple approach to video skimming is to augment
the keyframe extraction process by including a continuous set from frames
before and after the keyframe up to a certain threshold and include these
collection frames in the final summary of the video to create an video skim.

Figure 2: A simple example of Image Histogram. Figure 3: A pictorial
representation of SIFT key points extraction from 8X8 Image.

##  III Approaches

In this paper, for static keyframe extraction, we extract low level features
using uniform sampling, image histograms, SIFT and image features from
Convolutional Neural Network (CNN) trained on ImageNet [14]. We also used two
clustering methods: K-means and Gaussian clustering and chosen number of
clusters on basis of summarized video size. We have used video skims around
the selected keyframes to make the summary fore fluid and comprehensible for
humans. We take inspiration from the VSUMM method which is a prominent method
in video summarization [15] [5].

###  III-A keyframe Extraction Techniques

####  III-A1 Uniform Sampling

Uniform sampling is one of the most common methods for keyframe extraction
[16]. The idea is to select every $k$th frame from the video where the value
of $k$ is dictated by the length of the video. A usual choice of length for a
summarized video is 5% to 15% of the original video, which means every 20th
frame in case of 5% or every 7th frame in case of 15% length of the summarized
video is chosen. For our experiment, we have chosen to use every 7th frame to
summarize the video. This is a very simple concept which does not maintain
semantic relevance. Uniform sampling is often considered as a generalized
baseline for video summarization.

Figure 4: Unsupervised Video Summarization Framework. Here, first video is
converted into frames, followed by feature extraction. After feature
extraction, they are plotted in an embeddings space, where they are clustered
with % of summarized video as number of clusters. Last, we take center of
these clusters as keyframes and apply video skimming to make a continuous
summarized video.

####  III-A2 Image histogram

Image histograms [17] represent the total distribution of an image. It gives
us the number of pixels for a specific brightness values rated from 0 to 256.
Image histograms contain important information about images and they can be
utilized to extract keyframes. We extract the histogram from all frames. Based
on the difference between histograms of two frames, we decide whether the
frames have significant dissimilarities among them. We infer that, a
significant inter-frame image histogram dissimilarity indicates a rapid change
of scene in the video which might contain interesting components. For our
experiments, if histograms of two consecutive frames are 50% or more
dissimilar, we extract that frame as a keyframe.

####  III-A3 Scale Invariant Feature Transform

Scale Invariant Feature Transform (SIFT) [18], has been one of the most
prominent local features used in computer vision is applications ranging from
object and gesture recognition to video tracking. We use SIFT features for
keyframe extraction. SIFT descriptors are invariant to scaling, translation,
rotation, small deformations, and partially invariant to illumination, making
it a robust descriptor to be used as local features. In SIFT, important
locations are first defined using a scale space of smoothed and resized images
and applying difference of Gaussian functions on these images to find the
maximum and minimum responses. Non maxima suppression is performed and
putative matches are discarded to ensure a collection of highly interesting
and distinct collection of keypoints. Histogram of oriented gradients is
performed by dividing the image into patches to find the dominant orientation
of the localized keypoints. These keypoints are extracted as local features.
In our experiment, we have extracted HOGs for each frame in video, and then
put a threshold which could take 15% of video.

####  III-A4 VSUMM

This technique has been one of the fundamental techniques in video
summarization in the unsupervised setup. The algorithm uses the standard
K-means algorithm to cluster features extracted from each frame. Color
histograms are proposed to be used in [15]. Color histograms are 3-D tensors,
where each pixel’s values in the RGB channels determines the bin it goes into.
Since each channel value ranges in 0 − 255, usually, 16 bins are taken for
each channel resulting in a 16X16X16 tensor. Due to computational reasons, a
simplified version of this histogram was computed, where each channel was
treated separately, resulting in feature vectors for each frame belonging to R
48 . The nest step suggested for clustering is slightly different. But, the
simplified color histograms give comparable performance to the true color
histograms. Therefore, we modified VSUMM a bit by using the features extracted
from VGG16 at the 2nd fully connected layer [19], and clustered it using
kmeans.

####  III-A5 ResNet16 on ImageNet

While reading about approach of VSUMM, we decided to test a different
approach. We chose ResNet16 trained on image net, with different range of
filters, and chopped of last loss layer, so as to obtain the embeddings of
each image (512 dimension). We extracted frames out of the videos, and forward
pass them through ResNet16, and after obtaining the embeddings for each frame
in video, we clustered them using 2 algorithms: K-means and Gaussian Mixture
Models. The number of cluster has been take as 15% of the video frame numbers.
We later chose the frames closest to the center of clusters as the keyframes.

Table I: F1 score values of 25 SumMe dataset videos with Human’s entry as baseline followed by different approaches of keyframe extraction Video Name | Human (Avg.) | Uniform Sampling | SIFT | VSUMM(K-means) | VSUMM(Gaussian) | CNN (K-means) | CNN (Gaussian)
---|---|---|---|---|---|---|---
Base jumping | 0.257 | 0.085364 | 0.234 | 0.083356 | 0.094 | 0.239 | 0.247
Bike Polo | 0.322 | 0.07112 | 0.196 | 0.078369 | 0.065 | 0.204 | 0.212
Scuba | 0.217 | 0.0145059 | 0.144 | 0.145599 | 0.172 | 0.195 | 0.184
Valparaiso Downhill | 0.217 | 0.19899 | 0.19 | 0.201909 | 0.197 | 0.207 | 0.211
Bearpark climbing | 0.217 | 0.160377 | 0.146 | 0.156611 | 0.142 | 0.196 | 0.204
Bus in Rock Tunnel | 0.217 | 0.030199 | 0.177 | 0.029341 | 0.033 | 0.124 | 0.119
Car railcrossing | 0.217 | 0.363804 | 0.36 | 0.386466 | 0.396 | 0.197 | 0.174
Cockpit Landing | 0.217 | 0.089413 | 0.035 | 0.906021 | 0.856 | 0.965 | 0.984
Cooking | 0.217 | 0.023748 | 0.192 | 0.023172 | 0.0257 | 0.205 | 0.197
Eiffel Tower | 0.312 | 0.119034 | 0.004 | 0.123115 | 0.135 | 0.157 | 0.146
Excavators river crossing | 0.303 | 0.328008 | 0.32 | 0.326871 | 0.345 | 0.342 | 0.357
Jumps | 0.483 | 0.176244 | 0.16 | 0.174919 | 0.185 | 0.182 | 0.176
Kids playing in leaves | 0.289 | 0.426775 | 0.366 | 0.424418 | 0.482 | 0.372 | 0.384
Playing on water slide | 0.195 | 0.168675 | 0.232 | 0.174321 | 0.185 | 0.278 | 0.297
Saving dolphines | 0.188 | 0.212642 | 0.121 | 0.229369 | 0.257 | 0.247 | 0.217
St Maarten Landing | 0.496 | 0.0404343 | 0.12 | 0.039482 | 0.0254 | 0.059 | 0.068
Statue of Liberty | 0.184 | 0.068651 | 0.208 | 0.070949 | 0.072 | 0.095 | 0.097
Uncut Evening Flight | 0.35 | 0.253156 | 0.256 | 0.251676 | 0.274 | 0.278 | 0.295
paluma jump | 0.509 | 0.048565 | 0.092 | 0.047268 | 0.048 | 0.049 | 0.049
playing ball | 0.271 | 0.239955 | 0.222 | 0.258244 | 0.237 | 0.256 | 0.258
Notre Dame | 0.231 | 0.229265 | 0.23 | 0.223917 | 0.021 | 0.0230 | 0.0227
Air Force One | 0.332 | 0.066812 | 0.07 | 0.065103 | 0.061 | 0.065 | 0.048
Fire Domino | 0.394 | 0.002603 | 0.247 | 0.003367 | 0.0020 | 0.0042 | 0.0035
car over camera | 0.346 | 0.035693 | 0.04 | 0.038304 | 0.035 | 0.0458 | 0.0475
Paintball | 0.399 | 0.224322 | 0.23 | 0.233006 | 0.245 | 0.297 | 0.304
mean | 0.311 | 0.0152 | 0.171 | 0.155 | 0.1869 | 0.1765 | 0.212

###  III-B Clustering

####  III-B1 K-means clustering

K-means clustering is a very popular clustering method. Given a set of image
frames extracted by one of the methods mentioned in section III-A, the goal is
to partition these frames into different clusters, so that the within-cluster
sum of squared difference is minimum. This is equivalent to minimizing the
pairwise squared deviation of points in the same cluster. With this clustering
we find the interesting frames to be included in the summarization and discard
the ones that are rich in local features but contains less informative or
interesting content.
For our paper, we have used Kmeans for clustering the features obtained from
RESNET16 ImageNet trained method. We obtained 512 dimension vector for each
frame in video, and clustered them. We have set the number of cluster to be
15% of the video. After clustering, we chose the key points which was closest
to the center of that specific cluster.

####  III-B2 Gaussian Clustering (Mixture Model)

Gaussian mixture models (GMM) are often used for data clustering. Usually,
fitted GMMs cluster by assigning query data points to the multivariate normal
components that maximize the component posterior probability given the data.
That is, given a fitted GMM, a cluster assigns query data to the component
yielding the highest posterior probability. This method of assigning a data
point to exactly one cluster is called hard clustering.
However, GMM clustering is more flexible because you can view it as a fuzzy or
soft clustering method. Soft clustering methods assign a score to a data point
for each cluster. The value of the score indicates the association strength of
the data point to the cluster. As opposed to hard clustering methods, soft
clustering methods are flexible in that they can assign a data point to more
than one cluster.
In this paper, we used clustering on the embeddings obtained using RESNET16
trained network. we set the number of clusters to be 15% of the video, then
chose the points which were closest to the center of the cluster.

###  III-C Video Summarization

Our approach for video summarization is influenced by the VSUMM method [15].
Firstly, keyframes containing important information is extracted using one of
the methods mentioned in section III-A. To reduce the computation time for
video segmentation, a fraction of the frames were used. Considering the
sequence of frames are strongly correlated, the difference from one frame to
the next is expected to be very low when sampled at high frequencies, such as,
30 frames per second. Instead using a low frequency rate of 5 frames per
second had insignificant effect on the results but it increased the
computation speed by a significant margin. We used 5 frames per second as a
sampling rate for our experiments and discarded the redundant frames.

After extracting all the keyframes, we perform a clustering on the frames to
categorized them into interesting and uninteresting frames using one of the
methods mentioned in section III-B. The cluster with the interesting frames
were used to generate the summary of the video. The summary of the video was
chosen to have the length of approximately 15% of the original video. But this
summary was discontinuous and thus different from the way a human observer
would evaluate the summary leading to poor scores as our evaluation method
coincides with how a human being scores the summary. This problem was overcome
by using a 1.8 second skims from the extracted interesting frame. This makes
the summary continuous and easy to comprehend. The low frequency sampling of
frames helps keep the size if the video in check.

##  IV Experiments and Results

###  IV-A Dataset

For our experimentation, we use the SumMe dataset [20] which was created to be
used as a benchmark for video summarization. The dataset contains 25 videos
with the length ranging from one to six minutes. Each of these videos are
annotated by at least 15 humans with a total of 390 human summaries. The
annotations were collected by crowd sourcing. The length of all the human
generated summaries are restricted to be within 15% of the original video.
Frames from two example videos, a) Air Force One and b) Play Ball is presented
in Fig 3.

###  IV-B Evaluation Method

The SumMe dataset provides individual scores to each annotated frames. We
evaluate our method by measuring the F-score from the set of frames that have
been selected by our method. We compare the F-score to the human generated
summaries to validate the effectiveness of our method. F-score is a measure
that combines precision and recall is the harmonic mean of precision and
recall, the traditional F-measure or balanced F-score:

${\displaystyle
F=2\cdot{\frac{\mathrm{precision}\cdot\mathrm{recall}}{\mathrm{precision}+\mathrm{recall}}}}{\displaystyle
F=2\cdot{\frac{\mathrm{precision}\cdot\mathrm{recall}}{\mathrm{precision}+\mathrm{recall}}}}$

This measure is approximately the average of the two when they are close, and
is more generally the harmonic mean, which, for the case of two numbers,
coincides with the square of the geometric mean divided by the arithmetic
mean. There are several reasons that the F-score can be criticized in
particular circumstances due to its bias as an evaluation metric. This is also
known as the $F_{1}$ measure, because recall and precision are evenly
weighted.

Figure 5: Two example videos from the SumMe dataset. a) Air Force One has a
fixed camera and mostly static background. b) Play Ball - has moving camera
with dynamic background.

###  IV-C Results

We ran mentioned methods on the SumMe Dataset, and compared the F-scores
obtained by them (as shown in Table 1) .Our main goal is to be as much close
to human, which we were able to obtain using SIFT, VSUMM, and CNN. We also
took mean of scores for all videos, and can see that CNN(Gaussian) was
performing good followed by VSUMM. We observed that, the videos which had
dynamic view point was performing good with VSUMM and CNN, whereas the videos
with stable view point was performing very poor even with compared to Uniform
Sampling. This is where we can find difference in a human’s method of
summarizing vs an algorithm method.We can also see that SIFT’s and CNN’s have
positive correlation in terms of F-scores this is due to the features
obtained. Though, SIFT is not able to outperform CNN.

##  V Conclusion

Video Summarization is one of the hardest task because it depends on person’s
perception. So, we can never have a good baseline to understand whether our
algorithm is working or not. Sometimes, Humans just want 1-2 second of video
as summary, whereas machine looks for slightest difference in image intensity
and might give us 10 seconds of video.

From what the baseline has been given in SumMe Dataset, we chose the average
human baseline as true, as we would like to consider all perspectives. After
testing with all different forms of videos, we can conclude that Gaussian
Clustering along with Convolutional Networks can give better performance than
other methods with moving point camera videos. In fact, the SIFT algorithm
seems to perform well on videos with high motion, the reason behind it is that
we used deep layered features, thus they consists of important points inside
image, followed by Gaussian Clustering, which is specifically made for mixture
based components. We have also observed that, even Uniform Sampling is giving
better result for videos which have stable camera view point and very less
motion.
We can conclude that one single algorithm can’t be solution of video
summarization, it is dependent of the type of video, the motion inside video.

## References

  * [1] Y. Gong and X. Liu, “Video summarization using singular value decomposition,” in _Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662)_ , vol. 2, 2000, pp. 174–180 vol.2.
  * [2] B. Gong, W.-L. Chao, K. Grauman, and F. Sha, “Diverse sequential subset selection for supervised video summarization,” in _Advances in Neural Information Processing Systems 27_ , Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2014, pp. 2069–2077. [Online]. Available: http://papers.nips.cc/paper/5413-diverse-sequential-subset-selection-for-supervised-video-summarization.pdf
  * [3] K. Chorianopoulos, “Collective intelligence within web video,” _Human-centric Computing and Information Sciences_ , vol. 3, no. 1, p. 10, Jun 2013. [Online]. Available: https://doi.org/10.1186/2192-1962-3-10
  * [4] Z. Liu, E. Zavesky, B. Shahraray, D. Gibbon, and A. Basso, “Brief and high-interest video summary generation: Evaluating the at&t labs rushes summarizations,” in _Proceedings of the 2Nd ACM TRECVid Video Summarization Workshop_ , ser. TVS ’08. New York, NY, USA: ACM, 2008, pp. 21–25. [Online]. Available: http://doi.acm.org/10.1145/1463563.1463565
  * [5] M. Gygli, H. Grabner, H. Riemenschneider, and L. Van Gool, “Creating summaries from user videos,” in _ECCV_ , 2014.
  * [6] T. Ahonen, A. Hadid, and M. Pietikainen, “Face description with local binary patterns: Application to face recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 28, no. 12, pp. 2037–2041, Dec 2006.
  * [7] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in _2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)_ , vol. 1, June 2005, pp. 886–893 vol. 1.
  * [8] A. Bruhn, J. Weickert, and C. Schnörr, “Lucas/kanade meets horn/schunck: Combining local and global optic flow methods,” _International Journal of Computer Vision_ , vol. 61, no. 3, pp. 211–231, Feb 2005. [Online]. Available: https://doi.org/10.1023/B:VISI.0000045324.43199.43
  * [9] N. Ejaz, I. Mehmood, and S. W. Baik, “Efficient visual attention based framework for extracting key frames from videos,” _Signal Processing: Image Communication_ , vol. 28, no. 1, pp. 34 – 44, 2013. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0923596512001828
  * [10] Y. J. Lee, J. Ghosh, and K. Grauman, “Discovering important people and objects for egocentric video summarization,” in _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , June 2012, pp. 1346–1353.
  * [11] A. Khosla, R. Hamid, C. J. Lin, and N. Sundaresan, “Large-scale video summarization using web-image priors,” in _2013 IEEE Conference on Computer Vision and Pattern Recognition_ , June 2013, pp. 2698–2705.
  * [12] G. Kim, L. Sigal, and E. P. Xing, “Joint summarization of large-scale collections of web images and videos for storyline reconstruction,” in _Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition_ , ser. CVPR ’14. Washington, DC, USA: IEEE Computer Society, 2014, pp. 4225–4232. [Online]. Available: http://dx.doi.org/10.1109/CVPR.2014.538
  * [13] S. JADON, _HANDS-ON ONE-SHOT LEARNING WITH PYTHON: A Practical Guide to Implementing Fast And… Accurate Deep Learning Models with Fewer Training_. PACKT PUBLISHING LIMITED, 2019\. [Online]. Available: https://books.google.com/books?id=mRfDxQEACAAJ
  * [14] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge,” _International Journal of Computer Vision (IJCV)_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [15] S. E. F. de Avila, A. P. B. a. Lopes, A. da Luz, Jr., and A. de Albuquerque Araújo, “Vsumm: A mechanism designed to produce static video summaries and a novel evaluation method,” _Pattern Recogn. Lett._ , vol. 32, no. 1, pp. 56–68, Jan. 2011. [Online]. Available: http://dx.doi.org/10.1016/j.patrec.2010.08.004
  * [16] M. Nixon and A. Aguado, _Feature extraction and image processing for computer vision_. Academic press, 2019\.
  * [17] Y. Wang, Q. Chen, and B. Zhang, “Image enhancement based on equal area dualistic sub-image histogram equalization method,” _IEEE Transactions on Consumer Electronics_ , vol. 45, no. 1, pp. 68–75, 1999.
  * [18] J.-M. Morel and G. Yu, “Is the “ scale invariant feature transform ” ( sift ) really scale invariant ?” 2010.
  * [19] S. Jadon, “Introduction to different activation functions for deep learning,” _Medium, Augmenting Humanity_ , vol. 16, 2018.
  * [20] M. Gygli, H. Grabner, H. Riemenschneider, and L. Van Gool, “Creating summaries from user videos,” in _ECCV_ , 2014.