text:
\documentclass[../../main]{subfiles}
\pagestyle{fancy}

\begin{document}

\chapter{Ideal absoluteness}
\label{chapter.ideal-absoluteness}
\thispagestyle{fancy}

Historically, the idea of considering elementary embeddings existing only in generic extensions has been around for a while, but it all started as an analysis of \textit{ideals}. \textit{Precipitous ideals} were introduced in \cite{IdealGame} and further analysed in \cite{Precipitous}, being ideals that give rise to well-founded generic ultrapowers.

\qquad In this chapter we will introduce the \textit{ideally measurable cardinals}, essentially just switching perspective from the ideals themselves to the cardinals they are on. We then proceed to show how these cardinals relate to ``pure'' generic cardinals, being proper class versions of the faintly measurable cardinals that we have considered throughout Chapter \ref{chapter.virtual-large-cardinals}. We start with a definition of the latter.

\defi[\gbc]{
  A cardinal $\kappa$ is \textbf{generically measurable} if there is a generic extension $V[g]$, a transitive class $\N\subset V[g]$ and a generic elementary embedding $\pi\colon V\to\N$ with $\crit\pi=\kappa$.
}

Note that, trivially, every generically measurable cardinal is faintly measurable. The corresponding ideal version of this is then the following:

\defi{
  A cardinal $\kappa$ is \textbf{ideally measurable} if there exists an ideal $\I$ on $\p(\theta)$ such that the generic ultrapower $\ult(V,\I)$ is well-founded in the forcing extension $V^{\mathbb P}$, where $\mathbb P := \p^V(\kappa)/\I$.
}

It should also be noted that \cite{claverie-ideal-extenders} generalised the concept of ideally measurables to \textit{ideally strong cardinals} by introducing the concept of \textit{ideal extenders} to capture the strongness properties.

\qquad Throughout this chapter we will be interested in how properties of the \textit{forcings} affect the large cardinal structure of a critical point of a generic embedding. We thus define the following:

\defi{
  Let $\theta$ be a regular uncountable cardinal, $\kappa<\theta$ a cardinal and $\Phi(\kappa)$ a poset property\footnote{Examples of these are having the $\kappa$-chain condition, being $\kappa$-closed, $\kappa$-distributive, $\kappa$-Knaster, $\kappa$-sized and so on. Formally speaking, $\Phi(\kappa)$ is a first-order formula $\varphi(\kappa)$ which is true iff there is a poset $\mathbb P$ such that $\kappa$ is a cardinal and some first-order formula $\psi(\kappa,\mathbb P)$ is true.}. Then $\kappa$ is \textbf{$\Phi(\kappa)$ faintly $\theta$-measurable} if it is faintly $\theta$-measurable, witnessed by a forcing poset satisfying $\Phi(\kappa)$. Similarly, $\kappa$ is \textbf{$\Phi(\kappa)$ generically measurable} if it is generically measurable with the associated forcing satisfying $\Phi(\kappa)$.
}

\defi{
	A poset property $\Phi(\kappa)$ is \textbf{ideal-absolute} if whenever $\kappa$ satisfies that there is a $\Phi(\kappa)$ forcing poset $\mathbb P$ such that, in $V^{\mathbb P}$, there is a $V$-normal $V$-measure $\mu$ on $\kappa$, then there is a normal ideal $\I$ on $\kappa$ such that $\p(\kappa)/\I$ is forcing equivalent to a forcing satisfying $\Phi(\kappa)$.
}

Note that this is \textit{almost} saying that $\Phi(\kappa)$ ideally measurables are equivalent to $\Phi(\kappa)$ generically measurables, but the only difference is that these definitions require well-foundedness of the target model.

\qquad If $\Phi(\kappa)$ implies $\omega$-distributivity then we \textit{do} get well-foundedness for free, however: any witness to the ill-foundedness of the ultrapower is an $\omega$-sequence in the generic extension, so $\omega$-distributivity implies that this sequence is in $V$ as well, which is contradicting $V$-normality of the measure.

\qquad A typical ideal that we will be utilising is the following:

\defi{
	Let $\kappa$ be a regular cardinal, $\mathbb P$ a poset and $\dot\mu$ a $\mathbb P$-name for a $V$-normal $V$-measure on $\kappa$. Then the \textbf{induced ideal} is
		\eq{
			\I(\mathbb P,\dot\mu):=\{X\subset\kappa\mid\norm{\check X\in\dot\mu}_{\B(\mathbb P)}=0\},
		}

		where $\B(\mathbb P)$ is the Boolean completion of $\mathbb P$.
}

Note that if the generic measure $\mu$ is $V$-normal then $\I(\mathbb P,\dot\mu)$ is also normal. This ideal will witness our first ideal-absoluteness result, which is a simple rephrasing of a folklore result.

\pagebreak
\prop[Folklore][prop.kappa-cc-ideal-abs]{
	``The $\kappa^+$-chain condition'' is ideal-absolute.
}
\proof{
	Assume $\mathbb P$ has the $\kappa^+$-chain condition such that there is a $\mathbb P$-name $\dot\mu$ for a $V$-normal $V$-measure on $\kappa$. Let $\I:=\I(\mathbb P,\dot\mu)$ --- we will show that $\p(\kappa)/\I$ has the $\kappa^+$-chain condition. Assume not and let $\bra{X_\alpha\mid\alpha<\kappa^+}$ be an antichain of $\p(\kappa)/\I$, which by normality of $\I$ we may assume is pairwise almost disjoint. But this then makes $\bra{\norm{\check X_\alpha\in\dot\mu}_{\B(\mathbb P)}\mid\alpha<\kappa^+}$ an antichain of $\mathbb P$ of size $\kappa^+$, $\contr$.
}

We next move to distributivity. This property is especially interesting in the context of our generic large cardinals, as an ideal $\I$ on some cardinal $\kappa$ is $\omega$-distributive precisely if it is precipitous\footnote{See \cite{Precipitous} and \cite{Foreman}.}, so that carrying an $\omega$-distributive ideal coincides with our definition of \textit{ideally measurable}.

\theo[N.][theo.distributive-ideal-abs]{
	``${<}\lambda$-distributivity'' is ideal-absolute for all regular $\lambda\in[\omega,\kappa^+]$.
}
\proof{
	Assume that $\mathbb P$ is a ${<}\lambda$-distributive forcing such that there exists a $\mathbb P$-name $\dot\mu$ for a $V$-normal $V$-measure on $\kappa$. Let $\I:=\I(\mathbb P,\dot\mu)$ --- we will show that $\p(\kappa)/\I$ is ${<}\lambda$-distributive.

  \qquad Let $\gamma<\lambda$ and let $\vec\A$ be a $\gamma$-sequence of maximum antichains $\A_\alpha\subset\p(\kappa)/\I$ such that $\A_\beta$ refines $\A_\alpha$ for $\alpha\leq\beta$. We have to show that there is a maximal antichain $\A$ which refines all the antichains in $\vec\A$.

  \qquad Now define for every $\alpha<\gamma$ the sets
  \eq{
    \A^*_\alpha :=\{\norm{\check X\in\dot\mu}_{\B(\mathbb P)}\mid X\in\A_\alpha\}.
  }

  Note that $\A^*_\alpha$ is an antichain in $\mathbb P$. They are also maximal, because if $p\in\mathbb P$ was incompatible with every condition in $\A^*_\alpha$ then, letting $X:=\triangle\{\kappa - Y\mid Y \in \A_\alpha\}$, we have that $p$ is compatible with $\norm{\check X\in\dot\mu}_{\B(\mathbb P)}$, so that $X\in \I^+$. But $X$ is incompatible with everything in $\A_\alpha$, contradicting that $\A_\alpha$ is maximal.

	\qquad By ${<}\lambda$-distributivity of $\mathbb P$ we get an antichain $\A^*$ which refines all the antichains in $\vec\A^*$. But note that for every $p\in\A^*$, if we define $s_p(\alpha)$ to be the unique $a\in\A_\alpha$ such that $p\leq a$, then it holds that $p\leq\norm{\Delta s_p\in\dot\mu}_{\B(\mathbb P)}$,\footnote{Here we are using that $\lambda\leq\kappa^+$ to ensure that the diagonal intersection is in the measure.} so that $\Delta s_p\in \I^+$. Now $\A:=\{\Delta s_p\mid p\in\A^*\}$ gives us a maximal antichain which refines all the antichains in $\vec\A$.
}

In an unpublished paper, Foreman proved the following:

\theo[Foreman][theo.foreman]{
  Let $\kappa$ be a regular cardinal such that $2^\kappa = \kappa^+$, and let $\lambda\leq\kappa^+$ be an infinite successor cardinal. If player II has a winning strategy in $\G^-_\lambda(\kappa)$ then $\kappa$ carries a $\kappa$-complete normal precipitous ideal $\I$ such that $\p(\kappa)/\I$ has a dense ${<}\lambda$-closed subset of size $\kappa^+$.
}

Here we improve that result by not relying on the \ch-assumption, reaching the conclusion for all regular infinite $\lambda$, and also showing $(\kappa,\kappa)$-distributivity of the ideal forcing. The argument follows the same overall structure as the original, with more technicalities to achieve the stronger result.

\theo[Foreman-N.][theo.hopelessideal]{
	Let $\kappa$ be a regular cardinal and $\lambda\leq\kappa^+$ regular infinite. If player II has a winning strategy in $\G_\lambda^-(\kappa)$ then $\kappa$ carries a $\kappa$-complete normal ideal $\I$ such that $\p(\kappa)/\I$ is $(\kappa,\kappa)$-distributive and has a dense ${<}\lambda$-closed subset.
}
\proof{
  Set $\mathbb P:=\text{Add}(\kappa^+,1)$ if $2^\kappa>\kappa^+$ and $\mathbb P:=\{\emptyset\}$ otherwise. If $\kappa$ is measurable then the dual ideal to the measure on $\kappa$ satisfies all of the wanted properties, so assume that $\kappa$ is not measurable.	Fix a wellordering $<_{\kappa^+}$ of $H_{\kappa^+}^V$ and a $\mathbb P$-name $\pi$ for a sequence $\bra{\N_\gamma\mid\gamma<\kappa^+}\in V^{\mathbb P}$ such that
\begin{itemize}
	\item $\N_\gamma\in V$ for every $\gamma<\kappa^+$;
  \item $\N_{\gamma+1}\prec H_{\kappa^+}^V$ is a $\kappa$-model for every $\gamma<\kappa^+$;
  \item $\N_\delta=\bigcup_{\gamma<\delta}\N_\gamma$ for limit ordinals $\delta<\kappa^+$;
  \item $\N_\gamma\cup\{\N_\gamma\}\subset\N_\beta$ for $\gamma<\beta<\kappa^+$;
	\item $\p(\kappa)^V\subset\bigcup_{\gamma<\kappa^+}\N_\gamma$.\\
\end{itemize}

Define now the auxilliary game $\G(\kappa)$ of length $\lambda$ as follows.
\game{\alpha_0}{p_0,\M_0,\mu_0,Y_0}{\alpha_1}{p_1,\M_1,\mu_1,Y_1}{\cdots}{\cdots}{}{}

Here $\bra{\alpha_\gamma\mid\gamma<\lambda}$ is an increasing continuous sequence of ordinals bounded in $\kappa^+$, $\vec p$ is a decreasing sequence of $\mathbb P$-conditions satisfying that
	\eq{
		&p_\gamma\forces\godel{\check\M_\gamma=\pi(\check\alpha_\gamma)\land\text{$\check\mu_\gamma$ is a $\check\M_\gamma$-normal $\check\M_\gamma$-measure on $\check\kappa$}}
	}

	such that $Y_\gamma=\Delta_{\xi<\kappa} X^{\mu_\gamma}_\xi$, where $\vec X^{\mu_\gamma}_\xi\in H_{\kappa^+}^V$ is the $<_{\kappa^+}$-least enumeration of $\mu_\gamma$.\footnote{We use that $\mathbb P$ is $\kappa$-closed to get the $p_\gamma$'s as well as to ensure that $\M_\gamma,\mu_\gamma\in V$.} We require that the $\mu_\gamma$'s are $\subset$-increasing, and player II wins iff she can continue playing throughout all $\lambda$ rounds. Let $\mu_\lambda:=\bigcup_{\xi<\lambda}\mu_\xi$ be the \textbf{final measure} of the play.

	\qquad To every limit ordinal $\eta<\kappa^+$ define the \textbf{restricted auxilliary game} $\G(\kappa)\restr\eta$ in which player I is only allowed to play ordinals ${<}\eta$ with the sequence bounded in $\eta$. Note that a strategy $\tau$ for player II is winning in $\G(\kappa)$ if and only if it is winning in $\G(\kappa)\restr\eta$ for all $\eta<\kappa^+$, simply because all sequences of ordinals played by player I are bounded in $\kappa^+$.

	\qquad Note that $\mu_\lambda$ is precisely the tail measure on $\kappa$ defined by the $Y_\gamma$'s; i.e. that $X\in\mu_\lambda$ iff there exists a $\delta<\lambda$ such that $\abs{Y_\delta-X}<\kappa$. From this it is simple to see that $\G(\kappa)$ is equivalent to $\G_\lambda^-(\kappa)$, so player II has a winning strategy $\tau_0$ in $\G(\kappa)$.

	\qquad For any winning strategy $\tau$ in $\G(\kappa)\restr\eta$ and to every partial play $p$ of $\G(\kappa)\restr\eta$ consistent with $\tau$, define the associated \textbf{hopeless ideal}\footnote{This terminology is due to Matt Foreman.}
	\eq{
		I_p^\tau\restr\eta:=\{X\subset\kappa\mid\ &\text{For every play $\vec\alpha_\gamma*\tau$ extending $p$ in $\G(\kappa)\restr\eta$,}\\ &\text{$X$ is \textit{not} in the final measure}\}
	}

	\clai{
		\label{clai.hopelessideal}
    $\I:=\bigcap_{\eta<\lambda}I_{\bra{}}^\tau\restr\eta$ is normal and $(\kappa,\kappa)$-distributive, for every winning strategy $\tau$ in $\G(\kappa)$ for player II.
	}

	\cproof{
		For normality, if $\bra{Z_\gamma\mid\gamma<\kappa}$ is a sequence of elements of $\I$ such that $Z:=\nabla_\gamma Z_\gamma$ is $\I$-positive, then there exists a play of $\G(\kappa)\restr\eta$ in which player II follows $\tau$ such that $Z$ lies in the final measure. If we let player I play sufficiently large ordinals in $\G(\kappa)\restr\eta$ we may assume that $\bra{Z_\gamma\mid\gamma<\kappa}$ is a subset and an element of the final model as well, meaning that one of the $Z_\gamma$'s also lies in the final measure, $\contr$.

		\qquad We now show $(\kappa,\kappa)$-distributivity. Let $\U\subset\p(\kappa)/\I$ be an unrooted tree of height $\kappa$ such that every level $\U_\alpha$ is a maximal antichain of size $\leq\kappa$. We have to show that there is a maximal antichain $\mathcal A$ consisting of limit points of branches of $\U$. Pick $X\in\U$ and let $p$ be a play of $\G(\kappa)\restr\eta$ consistent with $\tau$ with limit model $\M$ and limit measure $\mu$, such that $X\in\mu$.

		\qquad By letting player I in $p$ play sufficiently large ordinals, we may assume that $\U\subset\M$, using that $\abs{\U}\leq\kappa$, and also that $b_X:=\U\cap\mu\in\M$. This means that $d_X:=\Delta b_X\in\p(\kappa)/\I$ is a limit point of the branch $b_X$ through $\U$, so that $\mathcal A:=\{d_X\mid X\in\U\}$ is a maximal antichain of limit points of branches of $\U$, making $\p(\kappa)/\I$ $(\kappa,\kappa)$-distributive.
	}

	Fix some limit ordinal $\eta<\kappa^+$. We will recursively construct a tree $\T^\eta$ of height $\lambda$ which consists of subsets $X\subset\kappa$, ordered by reverse inclusion. In the following we will talk of player II's moves as subsets of $\kappa$ -- here we are referring to the code of the move. During the construction of the tree we will inductively maintain the following properties of $\T^\eta\restr\alpha$ for $\alpha\leq\lambda$:\\

	\begin{itemize}
		\item \textsc{Tree strategy}: For every $\gamma<\alpha$ there is a winning strategy $\tau^\eta_\gamma$ for player II in $\G(\kappa)\restr\eta$ such that for every $\beta<\gamma$, the $\beta$'th move by $\tau^\eta_\gamma$ is an element of $\T^\eta_\beta$ and $\tau^\eta_\gamma$ is consistent with $\tau^\eta_\beta$ for the first $\beta$-many rounds.
		\item \textsc{Unique pre-history}: Given any $\beta<\alpha$ and $Y\in\T^\eta_\beta$ there is a unique partial play $p$ of $\G(\kappa)\restr\eta$ consistent with $\tau^\eta_\beta$ ending with $Y$ --- we define $I_Y^\tau:=I_p^\tau$ for $\tau$ being any winning strategy for player II in $\G(\kappa)\restr\eta$ satisfying that $p$ is consistent with $\tau^\eta_\beta$.
		\item \textsc{Cofinally many responses}: Let $\beta+1<\alpha$ and $Y\in\T^\eta_\beta$, and set $p$ to be the unique partial play of $\G(\kappa)\restr\eta$ given by the unique pre-history of $Y$. Then the $\T^\eta$-successors of $Y$ consists of player II's $\tau^\eta_\beta$-responses to $\tau^\eta_\beta$-partial plays extending $p$ such that player I's last move in these partial plays are cofinal in $\eta$.\footnote{The reason why we are dealing with the \textit{restricted} auxilliary games is to achieve this property.}
		\item \textsc{Positivity}: If $\beta<\alpha$ and $Y\in\T^\eta_\beta$ then $Y$ is $I_X^{\tau^\eta_\gamma}$-positive for every $\gamma<\beta$ and every $X\in\T^\eta\restr\gamma+1$ with $X\leq_{\T^\eta}Y$.\footnote{This actually follows from the cofinally many responses, but we include it here for transparency.}
	\item \textsc{Almost disjointness property}: Every level $\T^\eta_\beta$ consists of pairwise almost disjoint sets.\footnote{Two subsets $X,Y\subset\kappa$ are \textit{almost disjoint} if $\abs{X\cap Y}<\kappa$.}
		\item \textsc{Hopeless ideal coherence}: $I_{\bra{}}^{\tau^\eta_\beta}\cap\p(Y)=I_Y^{\tau^\eta_\beta}\cap\p(Y)$ for every $\beta<\alpha$ and $Y\in\T^\eta_\beta$.\\
	\end{itemize}

  Note that what we are really aiming for is achieving the hopeless ideal coherence, since that enables us to ensure that if $X,Y\in\T^\eta$ and $X\subset Y$ then really $X\geq_{\T^\eta}Y$ --- i.e. that we ``catch'' both $X$ and $Y$ in the same play of $\G(\kappa)\restr\eta$. This is crucial to show the ${<}\lambda$-closure of $\T$. The rest of the properties are inductive properties we need to ensure this.

	\qquad Set $\T^\eta_0:=\{\kappa\}$. Assume that we have built $\T^\eta\restr\alpha+1$ satisfying the inductive assumptions\footnote{In particular, we assume that $\tau^\eta_\alpha$ is defined.} and let $Y\in\T^\eta_\alpha$ --- we need to specify what the $\T^\eta$-successors of $Y$ are. Since $\kappa$ is weakly compact and not measurable it holds by Proposition 6.4 in \cite{Kanamori} that $\text{sat}(I_Y^{\tau^\eta_\alpha})\geq\kappa^+$, so we can fix a maximal antichain $\bra{X_\gamma^Y\mid\gamma<\eta}$ of $I_Y^{\tau^\eta_\alpha}$-positive sets. By $\kappa$-completeness of $I_Y^{\tau^\eta_\alpha}$ we can by Exercise 22.1 in \cite{Jech} even ensure that all of the $X_\gamma^Y$'s are pairwise disjoint.

	\qquad To every $\gamma<\eta$ we fix a partial play $p$ of even length of $\G(\kappa)\restr\eta$ consistent with $\tau^\eta_\alpha$ such that the last ordinal $\beta_\gamma^Y$ in $p$ played by player I is greater than or equal to $\gamma$ and $X_\gamma^Y$ has measure one with respect to the last measure in $p$. We then define the $\T^\eta$-successors of $Y$ to be player II's $\tau^\eta_\alpha$-responses to the $\beta_\gamma$'s (which are subsets of the $X_\gamma^Y$'s modulo a bounded set and are therefore pairwise almost disjoint).

  \qquad For limit stages $\delta<\lambda$ we apply $\tau_0$ to the branches of $\T^\eta\restr\delta$ to get $\T^\eta_\delta$.

\qquad We now have to check that the inductive assumptions still hold; let us start with the tree strategy. Assume that we have a partial play $p$ of length $2\cdot\alpha+1$ of $\G(\kappa)\restr\eta$, i.e. the last move in $p$ is by player II, consistent with $\tau^\eta_\alpha$; write $\xi_p$ for player I's last move in $p$ and $Y_p$ for player II's response to $\xi_p$, which is also the last move in $p$. We can then pick a $\zeta<\eta$ such that $\beta_\zeta^{Y_p}>\xi_p$ by the cofinally many responses property and let $\tau^\eta_{\alpha+1}(p)$ be player II's $\tau^\eta_\alpha$-response to the partial play leading up to $\beta_\zeta^{Y_p}$. After this $(\alpha+1)$'th round we just set $\tau^\eta_{\alpha+1}$ to follow $\tau_0$. It is clear that $\tau^\eta_{\alpha+1}$ satisfies the required properties.

  \qquad Before we move on to checking the remaining inductive assumptions, let us pause to get some intuition about the tree strategies. In the definition of $\tau^\eta_{\alpha+1}$ above, we took a partial play consistent with $\tau^\eta_\alpha$, applied $\tau_0$ for a while, took note of player II's last $\tau_0$-response and then included \textit{only that} response in our new $\tau^\eta_{\alpha+1}$ partial play. This means that to every $\tau^\eta_\alpha$-partial play there is an ostensibly much longer $\tau_0$-partial play into which $\tau^\eta_\alpha$ embeds; so we can look at the $\tau^\eta_\alpha$-partial plays as being ``collapsed'' $\tau_0$-partial plays.

	\qquad  Given the above tree strategy, $\T^\eta_{\alpha+1}$ clearly satisfies the cofinally many responses property and the positivity property, simply by construction. For the unique pre-history, let $Y\in\T^\eta_{\alpha+1}$ and assume it has two distinct immediate $\T^\eta$-predecessors $Z_0,Z_1\in\T^\eta_\alpha$. But then $Y\subset Z_0\cap Z_1$ and $Y$ is $I_{Z_0}^{\tau^\eta_\alpha}$-positive by the positivity assumption, contradicting that $Z_0$ and $Z_1$ are almost disjoint by the almost disjointness property. Given the unique pre-history we then also get the almost disjointness property.

\clai{
	$\T^\eta\restr\alpha+2$ satisfies the hopeless ideal coherence property.
}

\cproof{
	Let $Y\in\T^\eta_{\alpha+1}$ --- we have to show that
	\eq{
		I_{\bra{}}^{\tau^\eta_{\alpha+1}}\cap\p(Y)=I_Y^{\tau^\eta_{\alpha+1}}\cap\p(Y).\tag*{$(1)$}
	}

	It is clear that $I_{\bra{}}^{\tau^\eta_{\alpha+1}}\subset I_Y^{\tau^\eta_{\alpha+1}}$, so let $Z\in I_Y^{\tau^\eta_{\alpha+1}}\cap\p(Y)$ and assume for a contradiction that $Z$ is $I_{\bra{}}^{\tau^\eta_{\alpha+1}}$-positive. Letting $\vec\alpha_\xi*\vec Y_\xi$ be a play of $\G(\kappa)\restr\eta$ consistent with $\tau^\eta_{\alpha+1}$ such that $Z$ is in the final measure, the definition of $\tau^\eta_{\alpha+1}$ yields that $Y_\alpha\in\T^\eta_{\alpha+1}$. As $Z\in I_Y^{\tau^\eta_{\alpha+1}}$ we have to assume that $Y\neq Y_\alpha$, so that the almost disjointness property implies that
\eq{
	\abs{Y\cap Y_\alpha}<\kappa.\tag*{$(2)$}
}

By the choice of $\vec\alpha_\xi*\vec Y_\xi$ there is some $\delta\in(\alpha,\lambda)$ such that $\abs{Y_\delta-Z}<\kappa$, i.e. that $Y_\delta$ is a subset of $Z$ modulo a bounded set, since the $Y_\alpha$'s generate the final measure of the play. But then $Y_\delta\subset Y_\alpha$ by the rules of $\G(\kappa)\restr\eta$, and also that $\abs{Y_\delta -Y}<\kappa$ since $Z\subset Y$. But this means that $Y\cap Y_\alpha$ is $I_Y^{\tau^\eta_{\alpha+1}}$-positive since $Y_\delta$ is, contradicting $(2)$. This shows $(1)$.
}

\qquad This finishes the construction of $\T^\eta_{\alpha+1}$. For limit levels $\delta<\lambda$ we define $\tau^\eta_\delta$ as simply applying $\tau_0$ to the branches of $\T^\eta\restr\delta$ --- showing that the inductive assumptions hold at $\T^\eta_\delta$ is analogous to the above arguments, so we are now done with the construction of $\T^\eta$. Let $\tau^\eta:=\bigcup_{\alpha<\lambda}\tau^\eta_\alpha\restr{^{<\alpha}H_{\kappa^+}}$ and define\footnote{Note that the tree strategy property above ensures that the strategies \textit{do} line up, so that $\tau^\eta$ is a well-defined strategy as well.} $\I^\eta:=I_{\bra{}}^{\tau^\eta}$.

\qquad Now note that $\I^{\eta+1}\subset\I^\eta$ and $\T^\eta\subset\T^{\eta+1}$ for every $\eta<\kappa^+$ --- define the ideal $\I:=\bigcap_{\eta<\kappa^+}\I^\eta$ and the tree $\T:=\bigcup_{\eta<\kappa^+}\T^\eta$. We showed in Claim \ref{clai.hopelessideal} that $\I$ is $\kappa$-complete, normal and $(\kappa,\kappa)$-distributive.

\qquad We claim that $\T$ is dense in $\p(\kappa)/\I$.\footnote{This means that given any $\I$-positive set $X$ there is a $Y\in\T$ such that $Y-X\in\I$.} Let $X$ be an $\I$-positive set, making it $\I^\eta$-positive for some $\eta<\kappa^+$, meaning that there is a play $\vec\alpha_\gamma*\tau^\eta$ of $\G(\kappa)\restr\eta$ such that $X$ is in the final measure, which means that $\abs{Y_\delta-X}<\kappa$ for some large $\delta<\lambda$ and in particular that $Y_\delta-X\in\I$. But $Y_\delta\in\T^\eta\subset\T$ by definition of $\tau^\eta$, which shows that $\T$ is dense.

\qquad It remains to show that $\T$ is ${<}\lambda$-closed. If $\lambda=\omega$ then this is trivial, so assume that $\lambda\geq\omega_1$. Let $\beta<\lambda$ and let $\bra{Z_\alpha\mid\alpha<\beta}$ be a $\subset$-decreasing sequence of elements $Z_\alpha\in\T$. We can fix some $\eta<\kappa^+$ such that $Z_\alpha\in\T^\eta$ for every $\alpha<\beta$ by regularity of $\kappa^+$, and since the $Z_\alpha$'s are $\subset$-decreasing they must also be $\leq_{\T^\eta}$-increasing by the hopeless ideal coherence for $\T^\eta$\footnote{This is the only place in which we are using hopeless ideal coherence.}.

\qquad Let $\tilde Z\in\T^\eta$ be player II's $\tau^\eta$-response to the unique partial play of $\G(\kappa)\restr\eta$ corresponding to the branch containing the $Z_\alpha$'s, and pick $Z\in\T^\eta$ such that $\abs{Z-\tilde Z}<\kappa$ and $Z\geq_{\T^\eta}Z_\alpha$ for all $\alpha<\beta$, again by the density claim and the hopeless ideal coherence. Then $Z$ witnesses ${<}\lambda$-closure of $\T$.\footnote{We are using that $\lambda$ is regular to get $Z$.}
}

With a bit more work we can from this result then derive the following equivalences.

\coro[N.][coro.powerclosed]{
	Let $\kappa$ be a regular cardinal and $\lambda\in[\omega_1,\kappa^+]$ be regular. Then the following are equivalent:
	\begin{enumerate}
		\item $\kappa$ is ${<}\lambda$-closed faintly power-measurable;
		\item $\kappa$ is ${<}\lambda$-closed ideally power-measurable;
		\item $\kappa$ is $(\kappa,\kappa)$-distributive ${<}\lambda$-closed faintly measurable;
		\item $\kappa$ is $(\kappa,\kappa)$-distributive ${<}\lambda$-closed ideally measurable;
		\item Player II has a winning strategy in $\G_\lambda(\kappa)$.
	\end{enumerate}
}
\proof{
	$(v)\Rightarrow (iv)$ is Theorem \ref{theo.hopelessideal} above\footnote{Here well-foundedness of the generic ultrapower is automatic since $\lambda$ has uncountable cofinality.} and $(iv)\Rightarrow(iii)+(ii)$, $(iii)\Rightarrow(i)$ and $(ii)\Rightarrow(i)$ are trivial, so we show $(i)\Rightarrow(v)$.

	\qquad Assume $\kappa$ is ${<}\lambda$-closed faintly power-measurable, so there is a ${<}\lambda$-closed forcing $\mathbb P$ and a $V$-generic $g\subset\mathbb P$ such that, in $V[g]$, there exists a transitive class $N$ and a $\kappa$-powerset preserving elementary embedding $\pi\colon V\to N$. Write $\mu$ for the induced weakly amenable $V$-normal $V$-measure on $\kappa$. Now, back in $V$, define a strategy $\sigma$ for player II in $G_\lambda(\kappa)$ as follows.

	\qquad Whenever player I plays some model $M_\alpha$ then we let player II respond with a filter $\mu_\alpha$ such that, for some $p_\alpha\in\mathbb P$, $p_\alpha\forces\godel{\check\mu_\alpha=\dot\mu\cap\check M_\alpha}$ --- such a filter exists because $\mu$ is weakly amenable. We require the $p_\alpha$'s to be decreasing, which is possible by ${<}\lambda$-closure. Now, all the $\mu_\alpha$'s are clearly $M_\alpha$-normal $M_\alpha$-measures on $\kappa$, which makes $\sigma$ a winning strategy.
}

Note that the above results all relied on $\lambda$ being uncountable to achieve well-foundedness of the generic ultrapower. If we simply ignore this well-foundedness aspect then we get the following similar equivalence in the $\lambda=\omega$ case, which then also includes completely ineffable cardinals.

\coro[N.][coro.ineff]{
	Let $\kappa$ be a regular cardinal. Then the following are equivalent:\footnote{Points $(i)$ and $(ii)$ look a lot like the definition of faintly power-measurable and $(\kappa,\kappa)$-distributive ideally measurable, but here we are not requiring the ultrapowers to be well-founded, so that would be stretching the definition of being measurable.}
	\begin{enumerate}
		\item There exists a forcing poset $\mathbb P$ such that, in $V^{\mathbb P}$, there is a weakly amenable $V$-normal $V$-measure on $\kappa$;
		\item There exists a $(\kappa,\kappa)$-distributive forcing poset $\mathbb P$ such that, in $V^{\mathbb P}$, there is a $V$-normal $V$-measure on $\kappa$;
		\item $\kappa$ carries a normal $(\kappa,\kappa)$-distributive ideal;
		\item Player II has a winning strategy in $\G_\omega^-(\kappa)$;
		\item $\kappa$ is completely ineffable.
	\end{enumerate}
}
\proof{
	$(iv)\Leftrightarrow (v)$ was shown in Theorem \ref{theo.ineff}, and $(iii)\Rightarrow(ii)$ and $(ii)\Rightarrow(i)$ are trivial. $(i)\Rightarrow(iv)$ is as $(i)\Rightarrow(v)$ in Corollary \ref{coro.powerclosed}, and $(iv)\Rightarrow(iii)$ is Theorem \ref{theo.hopelessideal}.
}

As an immediate consequence we then get another ideal-absoluteness result.

\qcoro{
	``$(\kappa,\kappa)$-distributive ${<}\lambda$-closed'' is ideal-absolute for all regular $\lambda\in[\omega,\kappa^+]$.
}

We get the following similar results for the Cohen games\footnote{Theorem \ref{theo.hopelessideal2} is the reason for naming the $\C$-games ``Cohen games".}.

\theo[N.][theo.hopelessideal2]{
	Let $\kappa$ and $\lambda\leq\kappa$ be regular infinite cardinals such that $2^{<\theta}<\kappa$ for every $\theta<\lambda$. If player II has a winning strategy in $\C_\lambda^-(\kappa)$ then $\kappa$ carries a $\lambda$-complete  ideal $\I$ such that $\p(\kappa)/\I$ is forcing equivalent to $\text{Add}(\lambda,1)$.
}
\proof{
	We follow the proof of Theorem \ref{theo.hopelessideal} closely. Set $\mathbb P:=\text{Col}(\lambda,2^\kappa)$. Fix a wellordering $<_{\kappa^+}$ of $H_{\kappa^+}$ and a $\mathbb P$-name $\pi$ for a sequence $\bra{\N_\gamma\mid\gamma<\lambda}\in V^{\mathbb P}$ such that
	\begin{itemize}
		\item $\N_\gamma\in V$ for every $\gamma<\lambda$;
		\item $\kappa{+}1\subset\N_\gamma$ and $\abs{\N_\gamma-H_\kappa}^V<\lambda$ for every $\gamma<\lambda$;
		\item If $\delta<\lambda$ is a limit ordinal then $\N_\delta=\bigcup_{\gamma<\delta}\N_\gamma$, $\N_\delta\prec H_{\kappa^+}$ and it holds that $\N_\delta\models\zfc^-$;
		\item $\N_\gamma\cup\{\N_\gamma\}\subset\N_\beta$ for all $\gamma<\beta<\lambda$;
		\item $\p(\kappa)^V\subset\bigcup_{\gamma<\lambda}\N_\gamma$.\\
	\end{itemize}

	Define the auxilliary game $\G(\kappa)$ as in the proof of Theorem \ref{theo.hopelessideal} but where player I plays ordinals $\alpha_\eta<\lambda$ and where we use the above $\N_\gamma$'s. Here we only need ${<}\lambda$-closure of $\mathbb P$ to get an equivalence between $\G(\kappa)$ and $\C_\lambda^-(\kappa)$, since $\abs{\N_\gamma-H_\kappa}^V<\lambda$ for all $\gamma<\lambda$.

	\qquad To every limit ordinal $\eta<\lambda$ we define the restricted auxilliary game $\G(\kappa)\restr\eta$ as in the proof of Theorem \ref{theo.hopelessideal}, and to every winning strategy $\tau$ in $\G(\kappa)\restr\eta$ and partial play $p$ of $\G(\kappa)\restr\eta$ consistent with $\tau$ define the associated \textbf{hopeless ideal}
	\eq{
		I_p^\tau\restr\eta:=\{X\subset\kappa\mid\ &\text{For every play $\vec\alpha_\gamma*\tau$ extending $p$ in $\G(\kappa)\restr\eta$,}\\ &\text{$X$ is \textit{not} in the final measure}\}.
	}

	Now, if $\kappa$ is measurable then we trivially get the conclusion,\footnote{Take $\I(\text{Add}(\lambda,1),\check\mu)$ for $\mu$ the measure on $\kappa$.} so assume $\kappa$ is not measurable. Then $\text{sat}(\kappa)\geq\lambda$ since $2^{<\theta}<\kappa$ for every $\theta<\lambda$,\footnote{See Proposition 16.4 in \cite{Kanamori}.} so that we can continue exactly as in the proof of Theorem \ref{theo.hopelessideal} to construct ($\lambda$-sized) trees $\T^\eta$ and winning strategies $\tau^\eta$ for all limit ordinals $\eta<\lambda$ such that, setting $\I:=\bigcap_{\eta<\lambda}I^{\tau^\eta}_{\bra{}}$ and $\T:=\bigcup_{\eta<\lambda}\T^\eta$, $\T$ is a dense ${<}\lambda$-closed subset of $\p(\kappa)/\I$ of size $\lambda$, so that $\p(\kappa)/\I$ is forcing equivalent to $\text{Add}(\lambda,1)$.
}

\coro[N.]{
	\label{coro.cohen}
	Let $\kappa$ and $\lambda\in[\omega_1,\kappa]$ be regular such that $2^{<\theta}<\kappa$ for every $\theta<\lambda$. Then the following are equivalent:
	\begin{enumerate}
		\item $\kappa$ is ${<}\lambda$-closed faintly measurable;
		\item $\kappa$ is ${<}\lambda$-closed ideally measurable;
		\item $\kappa$ is ${<}\lambda$-closed $\lambda$-sized faintly measurable;
		\item $\kappa$ is ${<}\lambda$-closed $\lambda$-sized ideally measurable;
		\item Player II has a winning strategy in $\C_\lambda(\kappa)$.
	\end{enumerate}
}
\proof{
	$(iv)\Rightarrow (iii)+(ii)$, $(ii)\Rightarrow(i)$ and $(iii)\Rightarrow(i)$ all trivial, and $(i)\Rightarrow(v)$ is like $(i)\Rightarrow(v)$ in Corollary \ref{coro.powerclosed}, and $(v)\Rightarrow(iv)$ is Theorem \ref{theo.hopelessideal2}.
}

Again, if we ignore well-foundedness then we get the same equivalence in the $\lambda=\omega$ case:

\coro[N.]{
	\label{coro.cohen2}
	Let $\kappa$ be regular infinite. Then the following facts hold:
	\begin{enumerate}
		\item Player II has a winning strategy in $\C_\omega^-(\kappa)$; and
		\item $\kappa$ carries an ideal $I$ such that $\p(\kappa)/I$ is forcing equivalent to $\text{Add}(\omega,1)$.
	\end{enumerate}
}
\proof{
	Player II has a winning strategy in $\C_\omega^-(\kappa)$ as we are simply measuring finitely many sets without any demand for well-foundedness, showing $(i)$. Since $2^{<n}<\kappa$ for all $n<\omega$ as $\kappa$ is infinite, Theorem \ref{theo.hopelessideal2} then implies $(ii)$.
}

\qcoro[N.]{
  The property ``${<}\lambda$-closed $\lambda$-sized'' is ideal-absolute for all regular $\lambda\in[\omega,\kappa]$ such that $2^{<\theta}<\kappa$ for all $\theta<\kappa$.
}

With this corollary, our journey has come to an end. An ending, which is nothing but an oxymoron in one of these perennial mathematical journeys, so instead consider the following final chapter my baton to you, dear reader.\\

{\itshape
  \begin{center}
    \begin{tabular}{l}
      Natten bøjer sig i vækst;\\
      Og dagene vasker dit ansigt.\\
      Du træder gennem søvnen;\\
      Og åbner en dør til solen.\\
      Dér, ikke i dit eget lys;\\
      Bærer du kroppen;\\
      Strømmet igennem af blod.\\
      Dér er du menneske nu;\\
      Og du går for at finde din tid.\\[3px]
      --- Michael Strunge
    \end{tabular}
  \end{center}
}

\end{document}

max_stars_repo_name: saattrupdan/phd

max_issues_repo_name: saattrupdan/phd

max_forks_repo_name: saattrupdan/phd


text:
%!TEX root = ../Airbnb_CaseStudy.tex
\section{Objectives and KPIs} % (fold)
\label{sec:obj_kpis}

To track the progress toward the operational and strategical objectives of a company it has to define and monitor {\bf quantifiable} measures. Those measures have to be able to show the success or failure of certain targets. There might be some common industry key performance indicators (KPI) but nevertheless to get most out of the KPIs you use to monitor your web site's success they have to be synchronised with the company's strategy \citep[p. 347-349]{Kaushik07}.

\subsection{Establish a trusted p2p marketplace}
To figure out if the users still have trust in the p2p marketplace we need to collect information about the number of customer complaints, how many of them could not be solved directly as well as the \textit{transaction throughput} on the system. This will give us also hints about the \textit{customer satisfaction} and allows us to see a decline in the usage patterns of the platform more rapidly. In addition we can get feedback from our customers about our \textit{problem solving strategies} in case they are facing issues with the host.

\begin{description}
	\item \textbf{Possible KPIs}
	\begin{itemize}
    	\item No. of returning customers 2+
        \item Quality survey about "have you at some point felt like you won't be receiving your money" or "have you at some point felt like your host won't be showing up?"
        \item Rating of host in survey
        \item Ratio of mitigated to unmitigated conflict cases
        \item No. of transactions processed per period
        \item Amount of transactions processed per period
        \item No. of revisits per period
    \end{itemize}
\end{description}

% subsection p2p_marketplace (end)

\subsection{Available to and used by a worldwide community}
As one of the main objectives of our service is to establish a platform that is used on a global scope we have to measure the number of customers per region, the number of customer registration per region as well as a ratio of places available to book in various cities around the world. This will provide us with information if we succeed to \textit{attract new users} and \textit{to enlist additional outstanding places}. As our platform relies on a \textit{network effect} to continue to grow we have to continuously attract new users who might recommend the system to their friends or might also offer some interesting places to stay.

\begin{description}
	\item \textbf{Possible KPIs}
	\begin{itemize}
    	\item No. of cities with more than 20\% places to book
        \item No. of new customers from one country
        \item No. of countries with more than N customers
        \item Track origin of requester
        \item Ratio of visitors to population of the country
        \item No. of visitors from particular country
    \end{itemize}
\end{description}

% subsection worldwide_community (end)

\subsection{Enlist unique, attractive accommodations}
Just having a large pool of accommodations in place might not be sufficient to keep the offers on the platform attractive. We will have to constantly measure the actual set of offerings to figure out if they still \textit{fit the client expectations}, if the \textit{quality of the service} at the location is either steadying or growing or whether we \textit{missed out some regions} in a country that are of interest to our user base.

\begin{description}
	\item \textbf{Possible KPIs}
	\begin{itemize}
    	\item Location of accommodations (GPS coordinates to figure out distribution over a region)
        \item Ratio of special ``stop words" that are used in descriptions/reviews
        \item Rating of accommodations in customer survey (satisfaction, uniqueness)
        \item No. of sharing of accommodations on social networks (recommendation of place through the customer)
        \item No. of likes per accommodation on our own platform
    \end{itemize}
\end{description}

% subsection unique_accomodations (end)

\subsection{Provide a convenient booking experience}
The \textit{ease-of-use of our platform} is important to speed-up the process of finding and booking a desired place for the customer. So we measure how long it takes for a customer to finish the process, how long they stay on each site, which steps they take on the site to reach their goal as well as the number of aborts and cancellations, whose can give us hints if the process or the web site itself might be to complicated.

\begin{description}
	\item \textbf{Possible KPIs}
	\begin{itemize}
    	\item No. of unsatisfied customers (complaints \& refunds) per 1000 bookings
        \item Increase conversion ratio of visitors who booked a place
        \item Increase conversion ratio of visitors who became hosts
        \item No. of booking problems (aborts, cancellations, bouncers, ...)
        \item Major conversion rate
        \item Minor steps taken to book a place
        \item Time it took from visiting the site till the booking
        \item Time spend on each page
    \end{itemize}
\end{description}

% subsection convenient_experience (end)

\subsection{Leading to loyal, satisfied customers}
From a technical point of view we want to make sure that our platform is \textit{always available} for the customer and there are \textit{zero down-times} due to server or software errors. Additionally we want to make sure that the system \textit{does not slow down} with an increasing number of concurrent users accessing it. Beside those technical issues we also want to make sure that the existing customers are well served and get help immediately if it is required.

\begin{description}
	\item \textbf{Possible KPIs}
	\begin{itemize}
    	\item No. of concurrent users
    	\item Network latency
        \item Page load time (due to amount of processes)
        \item No. of 404 pages
        \item No. of 5xx pages (server errors)
        \item Server down-time/up-time
        \item No. of users reacting on mail campaigns
        \item No. of users utilizing the help system
    \end{itemize}
\end{description}
% section obj_kpis (end)

ext: tex

max_stars_repo_name: appelgriebsch/case-studies

max_issues_repo_name: appelgriebsch/case-studies

max_forks_repo_name: appelgriebsch/case-studies


text:
\cleardoublepage

\chapter*{Colophon}

This thesis was typeset using the \XeTeX{} engine. The microtype package is
responsible for micro-typographic adjustments concerning the color of the text,
line breakages, and the addition of character protrusion. TikZ has been used
for the illustrations.
The font used for the text and headings is Philipp Poll's Linux Libertine.
Some of the beautiful open type features which the typeface provides -- such
as old-style figures and swashes -- have been activated. The font used for the
monospaced code listings is Paul Hunt's \texttt{Source Code Pro}, which he
developed for Adobe. Both fonts are provided under free licenses.\\

\noindent{}The quote used on page \pageref{page:quote} is taken from Grimm's
Household Tales by Jacob and Wilhelm Grimm. Their collection of fairy tales
was first published in 1812 and translated from German to English in 1884 by
Margaret Hunt\footnote[1]{\href{https://en.wikisource.org/wiki/Page:Grimm\%27s_Fairy_Tales.djvu/355}{https://en.wikisource.org/wiki/Page:Grimm\%27s\_Fairy\_Tales.djvu/355}}.
The text is part of the public domain. It is typeset in the Linux Libertine
font as well, though with historical ligatures.\\

\noindent{}The title page typeface is Knuth's \textsf{Computer Modern Sans Serif}.
The illustration on the title page is titled »\emph{H\"ansel and Gretel}«;
it was created by Alexander Zick (1845-1907) and is in the public
domain\footnote[2]{\href{https://commons.wikimedia.org/wiki/File:H\%C3\%A4nsel_und_Gretel.jpg}{https://commons.wikimedia.org/wiki/File:H\"ansel\_und\_Gretel.jpg
}}.\\

\noindent{}The choice of the title illustration and the subsequent quote was
motivated by parallels in event-sourced systems and this certain fairytale.
Pigeons ate their breadcrumb trail and thus H\"ansel and Grethel were unable
to find their way back home. %which the siblings had created.
The objective of an event-sourced system is to never get to a point where it
is not possible to reconstruct how the system got there.
This thesis shows that there is much more to an event-sourced system. Not only
can we rebuild how we got somewhere, we can also explore which other houses we
could have reached taking different trails through the forest. How the story
could have gone differently, if H\"ansel and Gretel had had an event-sourced
system with retroactive capabilities\dots{}

max_stars_repo_name: cmichi/masterthesis

max_stars_repo_licenses: Unlicense MIT

max_issues_repo_name: cmichi/masterthesis

max_issues_repo_licenses: Unlicense MIT

max_forks_repo_name: cmichi/masterthesis

max_forks_repo_licenses: Unlicense MIT


text:
\subsection{Datasets}
Several datasets were proposed through the years to evaluate the task of FET. Since building large annotated datasets is an expensive task, most of them are built using Distant Supervision techniques. Some state-of-the-art datasets used to evaluate FET approaches are FIGER~\cite{Ling2012FineGrainedER}, BBN~\cite{ren-etal-2016-afet}, OntoNotes~\cite{ontonotes} and Choi~\cite{choi}. While the first three datasets have tree-like structures to group types hierarchically, Choi is organized differently. It groups the types into three categories: general, fine-grained, and ultra-fine-grained. Each dataset is provided with its own type set and is split into training set and test set. While every training set is obtained through distant supervision, test sets are manually annotated for most of them.

This thesis focuses the experiments on two of the most popular datasets: FIGER and BBN. The reason behind the choice is that they have a less complex hierarchy than OntoNotes, thus allowing us to better comprehend how KENN influences the task and how to take advantage of it. Regarding Choi, it has not been considered for this work because types are not hierarchically organized.

\subsubsection{FIGER}
FIGER is one of the first FET datasets. It was presented in 2012 with Fine-Grained Entity Recognition~\cite{Ling2012FineGrainedER}. The original version of the dataset is based on a type set $T$ derived from Freebase~\cite{bollacker2008freebase} and counts a total of 112 types. The hierarchy is organized as a forest of trees with maximum depth 1, i.e., 2-level hierarchy. A summary of the type set can be found in Figure~\ref{fig:figer}.

\begin{figure}
    \centering
    \includegraphics[width=0.7\linewidth]{figer.png}
    \caption{Type set of FIGER. Each box can be seen as a two-level tree, with the root node represented by the type in bold. The box at the bottom right is composed of uncategorized types. (Source:~\cite{Ling2012FineGrainedER})}
    \label{fig:figer}
\end{figure}

As said previously, the training set is obtained with a distant supervision technique and counts about $1.5M$ instances. The source of data that has been labeled is constituted by Wikipedia articles, where anchor links are treated as entity mentions. The annotation procedure can be summarized in three steps:
\begin{enumerate}
    \item For each sentence, detect all the linked segments $m$
    \item For each $m$, retrieve the related Wikipedia entity $e_{m}$
    \item For each $e_{m}$, obtain its types $t'_{m}$ from Freebase
    \item For each $t'_{m}$, refine the types to obtain a subset $t_{m} \subseteq t'_{m}$ such that $t_{m} \subseteq T$. The refinement is done by keeping only the ones with more than 5 ground instances and merging types that are too specific.
\end{enumerate}

The test set is composed of 434 manually annotated examples. The sentences are extracted from local newspapers, photography and veterinary magazines, and the student newspaper of the University of Washington.

Each entry of the dataset is represented following the structure of the JSON in Figure~\ref{fig:entry_bbn}. The main fields are \textit{tokens}, which contains the list of the worlds of the sentence, and \textit{mentions}. For each mention there are three subfields: \textit{start} and \textit{end} indicate the index of the tokens that delimits the mention, and \textit{labels} contains the true types.

\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{figures/entry_bbn.JPG}
    \caption{Structure of a FIGER/BBN entry. Example taken from BBN.}
    \label{fig:entry_bbn}
\end{figure}

\subsubsection{BBN}
BBN dataset for FET made its first appearance in~\cite{ren2016noise} in 2016. The original version of this dataset comes from the BBN Pronoun Coreference and Entity Type Corpus~\cite{bbnCoreference}, composed of manually annotated Wall Street Journal articles. These articles were originally annotated using 93 types, divided into 12 named entity types, 9 nominal entity types, 7 numeric types, and 64 subtypes. However, when applying distant supervision, the authors used DBpedia Spotlight to link entities and they had to remove those BBN types that could not be mapped into Freebase types. The resulting type set counts 47 types.

The dataset is constituted by 32,739 entries. The test set has not been manually annotated. To construct it, the authors simply extracted a subset composed of the 20\% of the dataset,

An entry of the dataset is structured in the same way as FIGER (Figure~\ref{fig:entry_bbn}), so we can find the sentence as \textit{tokens} and the \textit{mentions} including \textit{start}, \textit{end} and \textit{labels} as subfields.

\subsubsection{Dataset preparation \& statistics} \label{dataset_stats}
The adopted versions of the datasets are those proposed by Ren et al. in~\cite{ren-etal-2016-afet}\footnote{https://github.com/INK-USC/AFET}. Before performing the experiments, both training sets of FIGER and BBN were refined. First of all, the duplicates (i.e., instances with the same context, mention, and types) were removed. Then, examples having the same context and different sets of mentions were merged. Each entry with more than one mention was subsequently divided into distinct entries with single mentions. Regarding FIGER, the equivalent types \texttt{/living\_thing} and \texttt{/livingthing} were unified in \texttt{/living\_thing}. Finally the sentences were split into 3 fields: \textit{left\_context\_token}, \textit{mention\_span} and \textit{right\_context\_token}. The mention types can be found in the field \textit{y\_str}. An example of an entry of the refined dataset is available in Figure~\ref{fig:entry_bbn_clean}. Since the dev sets were not provided within the original datasets, they were obtained by sampling about 1K instances of the training sets, such that single-mention examples derived from the same multi-mention example are assigned to the same set.

\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{figures/entry_bbn_clean.JPG}
    \caption{Structure of a FIGER/BBN entry after data preparation - Example taken from BBN}
    \label{fig:entry_bbn_clean}
\end{figure}

Before proceeding with the analysis of the datasets, it is helpful to point out that every sentence can contain multiple types from different branches. We will refer to this condition with the term multibranch. Furthermore, if an instance $x$ of the dataset is labeled with a type $t$ that is a subtype of $t'$, then the type set of $x$ must contain both $t$ and $t'$.

In Table~\ref{tab:dataset_stats} we can find some useful statistics about the two datasets. The fields of the table can be described as follows:
\begin{itemize}
    \item \textbf{\# ex:} number of examples of the refined version of the dataset
    \item \textbf{\% only supertype:} percentage of examples where a coarse type occurs without any of its subtypes
    \item \textbf{\% only supertype (strict):} percentage of examples where only coarse types occur
    \item \textbf{\% inter-tree:} percentage of examples where sibling types occur together
    \item \textbf{\% intra-tree:} percentage of examples where types from different trees occur together
    \item \textbf{\% intra/inter-tree:} percentage of examples where types from different branches occur together\footnote{this statistic is not equivalent to \textit{\%~inter-tree}~+~\%~intra-tree, since in the same example we could find both the situations}
    \item \textbf{\# types:} number of types of the refined version of the dataset
    \item \textbf{\# avg types:} average number of types per example
    \item \textbf{\% isolated types:} percentage of types corresponding to an isolated node\footnote{node without any parent or child} of the hierarchy
\end{itemize}

Looking at the table, it is possible to draw some considerations. In both datasets, we can observe that the multibranch examples are mostly caused by the presence of \textit{inter-tree} types. Regarding FIGER, we see that the statistics about \textit{only~supertype} are widely different between the training/dev and test sets. We have about the 21\% of cases against the 60\%, becoming 15\% against 54\% considering the \textit{strict} mode. This diversity derives from the manual annotation, where probably the types annotated through distant supervision that were too specific have been removed by the annotators. Even the statistics of \textit{intra/inter-tree} differ a lot between the training/dev and test sets. In this case, we move from the 35\% of multibranch examples to the 11\%. Again, the reason can be found in the manual annotation. Indeed, when using distant supervision techniques, a mention can be labeled with all its meanings disregarding the context. To point out how noisy is FIGER, we can also see how the \textit{\#~avg~types} statistic drastically decreases after the manual annotation.

Moving on to BBN, which does not have a manually annotated test set, the situation is quite different. First of all, we can notice that while the training/dev set counts the 22-24\% of multibranch examples, in the test set they are absent. This statistic is motivated by the fact that Ren et al. pruned these examples from the test set. For the same reason, we have no difference between the values of \textit{\%~only~supertype} and \textit{\%~only~supertype~(strict)} in the test.

\begin{table}
\centering
\caption{Datasets statistics}
\label{tab:dataset_stats}
\resizebox{\columnwidth}{!}{\begin{tabular}{cccclll}
\hline
\multicolumn{1}{|c|}{\textbf{Dataset}} & \multicolumn{1}{c|}{\textbf{\# ex}}    & \multicolumn{1}{c|}{\textbf{\% only supertype}} & \multicolumn{1}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}\% only supertype\\ (strict)\end{tabular}}} & \multicolumn{1}{c|}{\textbf{\% inter-tree}} & \multicolumn{1}{c|}{\textbf{\% intra-tree}} & \multicolumn{1}{c|}{\textbf{\% inter/intra-tree}} \\ \hline
\multicolumn{1}{|c|}{BBN train}        & 84,492                                 & 16.0                                            & 7.64                                                                                & \multicolumn{1}{c}{22.33}                   & \multicolumn{1}{c}{2.65}                    & \multicolumn{1}{c|}{24.09}                        \\
\multicolumn{1}{|c|}{BBN dev}          & 1,039                                  & 15.3                                            & 8.47                                                                                & \multicolumn{1}{c}{20.69}                   & \multicolumn{1}{c}{2.31}                    & \multicolumn{1}{c|}{22.52}                        \\
\multicolumn{1}{|c|}{BBN test}         & 12,349                                 & 7.44                                            & 7.44                                                                                & \multicolumn{1}{c}{-}                       & \multicolumn{1}{c}{-}                       & \multicolumn{1}{c|}{-}                            \\ \hline
\multicolumn{1}{|c|}{FIGER train}      & 2,676,854                              & 21.33                                           & 14.99                                                                                & \multicolumn{1}{c}{23.63}                   & \multicolumn{1}{c}{15.38}                   & \multicolumn{1}{c|}{35.23}                        \\
\multicolumn{1}{|c|}{FIGER dev}        & 1,094                                  & 21.57                                           & 14.72                                                                                & \multicolumn{1}{c}{25.59}                   & \multicolumn{1}{c}{14.35}                   & \multicolumn{1}{c|}{35.83}                        \\
\multicolumn{1}{|c|}{FIGER test}       & 563                                    & 60.57                                           & 54.17                                                                                & \multicolumn{1}{c}{11.01}                   & \multicolumn{1}{c}{0.71}                    & \multicolumn{1}{c|}{11.72}                        \\ \hline
\multicolumn{1}{l}{}                   & \multicolumn{1}{l}{}                   & \multicolumn{1}{l}{}                            & \multicolumn{1}{l}{}                                                                               &                                             &                                             &                                                   \\ \cline{1-4}
\multicolumn{1}{|c|}{\textbf{Dataset}} & \multicolumn{1}{c|}{\textbf{\# types}} & \multicolumn{1}{c|}{\textbf{\# avg types}}      & \multicolumn{1}{c|}{\textbf{\% isolated types}}                                                    &                                             &                                             &                                                   \\ \cline{1-4}
\multicolumn{1}{|c|}{BBN train}        & 157,292                                & 1.86                                            & \multicolumn{1}{c|}{24.3}                                                                          &                                             &                                             &                                                   \\
\multicolumn{1}{|c|}{BBN dev}          & 1,903                                  & 1.83                                            & \multicolumn{1}{c|}{24.44}                                                                         &                                             &                                             &                                                   \\
\multicolumn{1}{|c|}{BBN test}         & 20,606                                 & 1.67                                            & \multicolumn{1}{c|}{15.4}                                                                          &                                             &                                             &                                                   \\ \cline{1-4}
\multicolumn{1}{|c|}{FIGER train}      & 6,380,532                              & 2.38                                            & \multicolumn{1}{c|}{9.21}                                                                          &                                             &                                             &                                                   \\
\multicolumn{1}{|c|}{FIGER dev}        & 2,616                                  & 2.39                                            & \multicolumn{1}{c|}{9.79}                                                                          &                                             &                                             &                                                   \\
\multicolumn{1}{|c|}{FIGER test}       & 840                                    & 1.49                                            & \multicolumn{1}{c|}{6.55}                                                                          &                                             &                                             &                                                   \\ \cline{1-4}
\end{tabular}}
\end{table}

The information about the hierarchy of each dataset are reported in Table~\ref{tab:dataset_hierarchy}. The columns of the table can be described as follows:
\begin{itemize}
    \item \textbf{\# nodes:} number of nodes of the hierarchy (i.e., cardinality of the type set)
    \item \textbf{\# levels:} maximum number of levels of a tree in the type set
    \item \textbf{\# top level:} number of root nodes with at least a child (i.e., supertypes)
    \item \textbf{\# leaves:} number of child nodes (i.e., subtypes)
    \item \textbf{\# isolated:} number of isolated nodes (i.e., neither supertypes nor subtypes)
\end{itemize}

\begin{table}
\centering
\caption{Datasets hierarchical structure}
\label{tab:dataset_hierarchy}
\begin{tabular}{|c|ccccc|}
\hline
\textbf{Dataset} & \multicolumn{1}{c|}{\textbf{\# nodes}} & \multicolumn{1}{c|}{\textbf{\# levels}} & \multicolumn{1}{c|}{\textbf{\# top level}} & \multicolumn{1}{c|}{\textbf{\# leaves}} & \textbf{\# isolated} \\ \hline
BBN              & 47                                     & 2                                       & 9                                          & 31                                      & 7                    \\ \hline
FIGER            & 128                                    & 2                                       & 22                                         & 79                                      & 27                   \\ \hline
\end{tabular}
\end{table}


text:
\section{Additional Experiments}
\label{sec:addexp}

\paragraph{CREMI A/B/C.} As part of the MICCAI 2016 challenge on circuit reconstruction from electron microscopy images (CREMI), six ssTEM datasets were made publicly available\footnote{\scriptsize{\url{http://www.cremi.org}}},  each $1250\times1250\times125$ voxels. Since only three datasets include manually-labeled `ground truth', we use these three volumes for our experiments. The volumes are part of an adult fruit fly (Drosophila melanogaster) brain. The resolution of all three datasets is $4\times4\times40~\text{nm}^3\text{/voxel}$. We evaluate error detection and correction on subvolumes of CREMI A/B/C with the dimensions $1250\times1250\times5$ voxels. The subvolumes were cut from the last 25 sections of each of the three datasets and unseen during training. We compare focused proofreading and guided proofreading with automatic selection ($p_t=0.95$) and selection oracle.

\paragraph{Retraining.} Since the CREMI data is a different species, we simply retrain our split error classifier as well as focused proofreading by Plaza~\cite{focused_proofreading}. For this, we use the first 100 sections of each of the three CREMI datasets combined as training data. All parameters are unchanged and left as reported in the paper.

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremi_roc_separate_small.pdf}
\caption{Receiver Operating Characteristic curves comparing focused proofreading and guided proofreading automatic correction on the CREMI A/B/C fruit fly subvolumes. Guided proofreading performs better on all three datasets.}
\label{fig:cremi_performance}
\end{figure}

\paragraph{Classification Performance.} Figure~\ref{fig:cremi_performance} compares the  focused proofreading and guided proofreading classifiers on the CREMI A/B/C datasets. Our method exhibits higher sensitivity and lower fall-out.

%\paragraph{Error correction.} In all three datasets merge error detection found over 300 merge errors. Unfortunately, merge error correction crashed because of a software error on our part. Therefore, we only evaluate split error detection and correction on subvolumes of CREMI A/B/C with the dimensions $1250\times1250\times5$ voxels. The subvolumes were cut from the last 25 sections of each of the three datasets and unseen during training. We compare focused proofreading and guided proofreading with automatic selection ($p_t=0.95$) and selection oracle.

\subsection{CREMI A}

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremiA_trails.pdf}
\caption{Performance comparison of Plaza's focused proofreading and our guided proofreading on 5 sections of the CREMI A dataset. All measurements are reported as median VI, the lower the better. The threshold for automatic selection is $p_t=0.95$ (green line). The slope of the selection oracle shows that guided proofreading reduces VI faster.}
\label{fig:cremiAtrails}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremiAboxplot.pdf}
\caption{VI distributions of guided proofreading (GP) and focused proofreading (FP) output across slices of the CREMI A dataset, with different error correction approaches. The variation resulting from performance of FP with automatic selection is $5.4\times$ higher than GP (\protect\includegraphics[width=0.2cm]{gfx/arrow.pdf}), with median VI of $5.32$ and $SD=0.009$. GP does not reach the best possible VI as discussed in the text.}
\label{fig:cremiAboxplot}
\end{figure}

Figure~\ref{fig:cremiAtrails} and~\ref{fig:cremiAboxplot} compare Plaza's focused proofreading and guided proofreading on the five sections of CREMI A.

\vspace{-4mm}

\paragraph{Selection oracle.} With focused proofreading, the selection oracle reduces median VI to 0.928, $SD=0.043$ from an initial median VI of 1.06 ($SD=0.055$). 532 corrections out of 3707 were accepted. Guided proofreading does not reach the best possible VI, however, reduces VI faster with less corrections to 0.941 ($SD=0.04$). Out of 4463 corrections, 1275 were accepted.

\paragraph{Automatic selection with threshold.} Not surprisingly, focused proofreading performs poorly when ran automatically (VI of 5.32, $SD=0.009$). Guided proofreading is able to reduce VI to 0.989 ($SD=0.043$) with $p_t=0.95$.

\subsection{CREMI B}

Figure~\ref{fig:cremiBtrails} and~\ref{fig:cremiBboxplot} show the results on the CREMI B dataset.

\paragraph{Selection oracle.} Focused proofreading is able to reduce median VI to 1.29, $SD=0.031$ from an initial median VI of 1.63 ($SD=0.025$). Out of 1959 corrections, the selection oracle accepted 517. With guided proofreading, the median VI is reduced to 1.30, $SD=0.03$ while accepting 1111 corrections out of 3073.

\paragraph{Automatic selection with threshold.} Focused proofreading results in a VI of 4.25 ($SD=0.07$). Guided proofreading reduces median VI to 1.43 ($SD=0.038$).

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremiB_trails.pdf}
\caption{Split error correction by Plaza's focused proofreading and our guided proofreading compared on the CREMI B dataset. All measurements are reported as median VI, the lower the better. Automatic selection with threshold (green line) yields reasonable performance using guided proofreading.}
\label{fig:cremiBtrails}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=.9\linewidth]{gfx/cremiBboxplot.pdf}
\caption{VI distributions of guided proofreading (GP) and focused proofreading (FP) output across 5 sections of the CREMI B dataset. We compare automatic selection and oracle selection. The variation resulting from performance of FP with automatic selection is $3\times$ higher than GP (\protect\includegraphics[width=0.2cm]{gfx/arrow.pdf}), with median VI of $4.25$ and $SD=0.07$.}
\label{fig:cremiBboxplot}
\end{figure}

\subsection{CREMI C}

The results of split error correction using focused proofreading and guided proofreading on the CREMI C subvolume are shown in Figure~\ref{fig:cremiCtrails} and~\ref{fig:cremiCboxplot}.

\paragraph{Selection oracle.} With focused proofreading, the initial median VI of 1.75 ($SD=0.086$) is reduced to 1.45 ($SD=0.056$) with 670 accepted corrections out of 2694. Guided proofreading is able to reduce the VI to 1.47 ($SD=0.06$). Here, the oracle accepted 1531 out of 4332 corrections.

\paragraph{Automatic selection with threshold.} Focused proofreading results in a VI of 4.81 ($SD=0.03$). Guided proofreading with $p_t=0.95$ reduces median VI to 1.57 ($SD=0.081$).

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremiC_trails.pdf}
\caption{Performance comparison of Plaza's focused proofreading and our guided proofreading on the CREMI C dataset. Lower VI scores are better. Guided proofreading corrects the initial segmentation faster with less corrections than focused proofreading. The green line shows the automatic threshold $p_t=0.95$.}
\label{fig:cremiCtrails}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{gfx/cremiCboxplot.pdf}
\caption{VI distributions of guided proofreading (GP) and focused proofreading (FP) output across the CREMI C subvolume, with different error correction approaches. The variation resulting from performance of FP with automatic selection is $3\times$ higher than GP (\protect\includegraphics[width=0.2cm]{gfx/arrow.pdf}), with median VI of $4.81$ and $SD=0.08$.}
\label{fig:cremiCboxplot}
\end{figure}

max_stars_repo_name: VCG/gp

max_issues_repo_name: VCG/gp

max_forks_repo_name: VCG/gp


text:
\documentclass{article}
\usepackage{amsmath}
% if you need to pass options to natbib, use, e.g.:
% \PassOptionsToPackage{numbers, compress}{natbib}
% before loading nips_2017
%
% to avoid loading the natbib package, add option nonatbib:
% \usepackage[nonatbib]{nips_2017}

%\usepackage{nips_2017}

% to compile a camera-ready version, add the [final] option, e.g.:
\usepackage[final]{nips_2017}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{subfig}
\usepackage{cleveref}
\usepackage{graphicx}
\usepackage{siunitx}

\graphicspath{ {hw4/imgs/} }

\title{Computer Vision 1: Image Alignment and Stitching}

\author{
	Gabriele Bani \\
	11640758 \\
  \texttt{gabriele.bani@student.uva.nl} \\
  %% examples of more authors
  \And
  	Andrii Skliar \\
  11636785 \\
  \texttt{andrii.skliar@student.uva.nl} \\
}

\begin{document}
\maketitle
\section*{Introduction}

In this homework we explore algorithms for keypoint matching using SIFT keypoints and image affine transformation and stitching using RANSAC.

\section{Image Alignment}
We have visualized keypoint matching and image transformation for all possible combinations of images and you can see results in \cref{fig:boat_matching}, \cref{fig:bus_matching}, \cref{fig:boat_transformation} and \cref{fig:bus_transformation}.

If we just do a transformation and round coordinates (which corresponds to nearest neighbor interpolation), we get a lot of black pixels, which means, that color values for them are missing. To solve that issue, we have used the following technique for interpolation: for every such pixel, we find the mean of the colors in the window of 5x5 with that pixel in the center and replace it with the mean value. This is similar to just using median filter of size 5x5 on those pixel.

\begin{enumerate}
    \item How many matches do we need to solve an affine transformation?\\

    The least amount is 3 matches, because system has 6 unknown variable and that would make sense that having 3 samples, we have 6 known variables to solve system of equations. However, in general, minimum number of points depends on the model, that we are trying to approximate. If it is linear, two points will be enough (because you only need 2 points to define a line), while for circle you would need 3 points (because you only need three points to define a circle) and for homography you need at least 4 points. In our case, we constrain homography to affine homography, thus, we only need 3 points.\\

    However, that would not give us least squares solution (because our system is not overdetermined) and that might lead to overfitting. Overfitting for the given algorithm happens in a following way: let's say, that we could find parameters with which we get all three points to be inliers in the first iteration. In that case, even if we find better transformation, we will never change our solution and that means, that better solution (with lower error in general), will be skipped. That can be solved by either lowering the error threshold or increasing number of matches. However, too many matches would also result into system not being able to find a suitable transformation and that should be taken into account when choosing the number of samples. In our case, we fixed it to 7 and that number seems to work very well for us.
    \newpage

    \item How many iterations in average are needed to find good transformation parameters?\\

    There is generally no exact answer to that, but there is a way to estimate expected number of iterations. It is done using a following formula: $N = \frac{log(1-p)}{log(1-w^n)}$, where $p$ is the confidence level, $w$ is the probability of a random data point to be an inlier, $n$ is the number of samples used to estimate the model. In our case, $w = 0.5$, $p = 0.99$.
    \end{enumerate}

\begin{figure}[h]
  \caption{Results for keypoint matching for boat images with random subset of 50 points plotted}
  \centering
    \includegraphics[width=0.9\textwidth]{boat_keypoint_matching.jpg}
  \label{fig:boat_matching}
\end{figure}

\begin{figure}[h]
  \caption{Results for keypoint matching for bus images with random subset of 50 points plotted}
  \centering
    \includegraphics[width=0.9\textwidth]{bus_keypoint_matching.jpg}
  \label{fig:bus_matching}
\end{figure}

\begin{figure}[h]
    \centering
    \caption{Original and transformed boat images}
    \subfloat[Left part of the image]{{
    	\includegraphics[width=0.5\textwidth]{boat1.jpg}
    }}
    \subfloat[Right part of the image]{{
    	\includegraphics[width=0.5\textwidth]{boat2.jpg}
    }}\\
    \subfloat[Transformed image (left transformed to right)]{{
    	\includegraphics[width=0.5\textwidth]{boat_left_right_transformation.jpg}
    }}
    \subfloat[Transformed image (right transformed to left)]{{
    	\includegraphics[width=0.5\textwidth]{boat_right_left_transformation.jpg}
    }}
\label{fig:boat_transformation}
\end{figure}

\begin{figure}[h]
    \centering
    \caption{Original and transformed bus images}
    \subfloat[Left part of the image]{{
    	\includegraphics[width=0.5\textwidth]{left.jpg}
    }}
    \subfloat[Right part of the image]{{
    	\includegraphics[width=0.5\textwidth]{right.jpg}
    }}\\
    \subfloat[Transformed image (left transformed to right)]{{
    	\includegraphics[width=0.5\textwidth]{bus_left_right_transformation.jpg}
    }}
    \subfloat[Transformed image (right transformed to left)]{{
    	\includegraphics[width=0.5\textwidth]{bus_right_left_transformation.jpg}
    }}
\label{fig:bus_transformation}
\end{figure}

\section{Image Stitching}

We have visualized image stitching for all possible combinations of images and you can see results in \cref{fig:boat_stitching} and \cref{fig:bus_stitching}.

\begin{figure}[h]
    \centering
    \caption{Original and stitched boat images}
    \subfloat[Left part of the image]{{
    	\includegraphics[width=0.5\textwidth]{boat1.jpg}
    }}
    \subfloat[Right part of the image]{{
    	\includegraphics[width=0.5\textwidth]{boat2.jpg}
    }}\\
    \subfloat[Stitched image (right transformed to left)]{{
    	\includegraphics[width=0.5\textwidth]{boat_right_left_stitching.jpg}
    }}
    \subfloat[Stitched image (left transformed to right)]{{
    	\includegraphics[width=0.5\textwidth]{boat_left_right_stitching.jpg}
    }}
\label{fig:boat_stitching}
\end{figure}

\begin{figure}[h]
    \centering
    \caption{Original and stitched bus images}
    \subfloat[Left part of the image]{{
    	\includegraphics[width=0.5\textwidth]{left.jpg}
    }}
    \subfloat[Right part of the image]{{
    	\includegraphics[width=0.5\textwidth]{right.jpg}
    }}\\
    \subfloat[Stitched image (right transformed to left)]{{
    	\includegraphics[width=0.5\textwidth]{bus_right_left_stitching.jpg}
    }}
    \subfloat[Stitched image (left transformed to right)]{{
    	\includegraphics[width=0.5\textwidth]{bus_left_right_stitching.jpg}
    }}
\label{fig:bus_stitching}
\end{figure}

\section*{Conclusion}

In this homework we have explored algorithms for keypoint matching using SIFT keypoints and image affine transformation and stitching using RANSAC.

\end{document}

max_stars_repo_name: askliar/computer-vision

max_issues_repo_name: askliar/computer-vision

max_forks_repo_name: askliar/computer-vision


text:
% $Id$ %
\appendix

\input{appendix/file_formats.tex}

\opt{lcd_bitmap}{\input{appendix/album_art_info.tex}}

\input{appendix/wps_tags.tex}

\input{appendix/config_file_options.tex}

\input{appendix/menu_structure.tex}

\chapter{User feedback}\label{sec:feedback}
\section{Bug reports}
If you experience inappropriate performance from any supported feature,
please file a bug report on our web page. Do not report missing
features as bugs, instead file them as feature ideas (see below).

For open bug reports refer to
\url{http://www.rockbox.org/tracker/index.php?type=2}

\subsection{Rules for submitting new bug reports}

\begin{enumerate}
\item  Check that the bug has not already been reported
\item  Always include the following information in your bug report:

\begin{itemize}
\item  Which exact \dap{} you have.
\item  Which exact Rockbox version you are using
(Menu $\rightarrow$ System $\rightarrow$ Rockbox Info $\rightarrow$ Version)
\item  A step{}-by{}-step description of what you did and what happened
\item  Whether the problem is repeatable or a one{}-time occurrence
\item  All relevant data regarding the problem, such as playlists, MP3
files etc. (IMPORTANT!)
\end{itemize}
\end{enumerate}

\section{Feature ideas}
To suggest an idea for a feature or to read those made by others, see
\url{http://forums.rockbox.org/index.php?board=49.0}.  Please keep in
mind that this forum is for the discussion of feature ideas - they are not
 requests and there is no guarantee they will be acted upon.

\subsection{Rules for submitting a new feature idea}

\begin{enumerate}
\item Check that the feature has not already been suggested.
  Duplicates are really boring!
\item Check that the feature has not already been implemented.
  Download the latest current/daily build and/or search the mail list archive.
\item Check that the feature is possible to implement (see \reference{ref:NODO}).
\end{enumerate}

\subsection{\label{ref:NODO}Features we will not implement}
This is a list of Feature Requests we get repeatedly that we simply
cannot do. View it as the opposite of a TODO!

\begin{itemize}
\opt{archos}{
\item Record to WAV (uncompressed) or MP3pro format.\\
The recording hardware (the MAS) does not allow us to do this
\item Crossfade between tracks.\\
  Crossfading would require two mp3 decoders, and we only have one.
  This is not possible.
\item Support MP3pro, WMA or other sound format playback.\\
  The mp3{}-decoding hardware can only play MP3. We cannot make it play other
  sound formats.
\item  Converting OGG $\rightarrow$ MP3.\\
  The mp3{}-decoding hardware cannot decode OGG. It can be reprogrammed, but
  there is too little memory for OGG and we have no documentation on how to
  program the MAS' DSP. Doing the conversion with the CPU is impossible, since
  a 12~MHz SH1 is far too slow for this daunting task.
\item Archos Multimedia support.\\
  The Archos Multimedia is a completely different beast. It is an entirely
  different architecture, different CPU and upgrading the software is done
  a completely different way. We do not wish to venture into this.  Others
  may do so. We will not.
\item Multi{}-band (or graphic) equaliser.\\
  We cannot access information for that kind of visualisation from the MP3
  decoding hardware.
\item CBR recording.\\
  The MP3 encoding hardware does not allow this.
\item Change tempo of a song without changing pitch.\\
  The MP3 decoding hardware does not allow this.
\item Graphic frequency (spectrum analyser).\\
  We cannot access the audio waveform from the MP3 decoder so we cannot analyse
  it. Even if we had access to it, the CPU would probably be too slow to
  perform the analysis anyway.
\item Cool sound effects.\\
  Adding new sound effects requires reprogramming the MAS chip, and we cannot
  do that. The MAS chip is programmable, but we have no access to the chip
  documentation.
}
\nopt{iriverh300,iaudiox5}{
\item Interfacing with other USB devices (like cameras) or 2 player games over USB.\\
  The USB system demands that there is a master that talks to a slave. The
  \dap{} can only serve as a slave, as most other USB devices such as
  cameras can. Thus, without a master no communication between the slaves
  can take place. If that is not enough, we have no way of actually
  controlling the communication performed over USB since the USB circuit
  in the \dap{} is strictly made for disk{}-access and does not allow us
  to play with it the way we'd need for any good communication to work.
}
\item Support other file systems than FAT32 (like NTFS or ext2 etc.).\\
  No.
  \opt{archos}{Rockbox needs to support FAT32 since it can only start off a FAT32
  partition (since that is the only way the ROM can load it), and adding}%
  support for more file systems will just take away valuable ram for
  unnecessary features. You can partition your \dap{} fine, just make sure
  the first one is FAT32 and then make the other ones whatever file system
  you want. Just do not expect Rockbox to understand them.
\item Add scandisk{}-like features.\\
  It would be a very slow operation that would drain the batteries and
  take a lot of useful ram for something that is much better and faster
  done when connected to a host computer.
\item Alphabetical list skipping.\\
  Skipping around the lists by jumping letters (i.e skip all C's and go
  straight to the first D). This isn't feasible with the current list
  implementation, if you really want this you can get similar effects using
  the database (see \reference{ref:database}).
\item Add support for non standard tag formats.\\
APE tags in MP3 files has been rejected a few times already. Its not something we want.
\item Implementing the ability to playback DRM files.\\
  Firstly, this would be extremely difficult to implement legally - Rockbox
  is not legal entity as such, and therefore is unable to enter into license
  agreements with providers of DRM technology.
  Secondly, Rockbox is open source, which would mean that any DRM technology we
  incorporated into our codebase would suddenly become visible to the whole world,
  completely defeating its purpose. Remember, DRM achieves part of its security
  through obscurity, and publishing the keys necessary to decrypt DRM'd
  media would essentially render it useless.
\end{itemize}

\chapter{Credits}
People that have contributed to the project, one way or another. Friends!
%
\begin{multicols}{2}
\noindent\caps{\small{\input{CREDITS.tex}}}
\end{multicols}

\chapter{Licenses}

\section{GNU Free Documentation License}
\input{appendix/fdl.tex}
\newpage
\section{The GNU General Public License}
\input{appendix/gpl-2.0.tex}

max_stars_repo_name: Rockbox-Chinese-Community/Rockbox-RCC

max_issues_repo_name: Rockbox-Chinese-Community/Rockbox-RCC

max_forks_repo_name: Rockbox-Chinese-Community/Rockbox-RCC