Learning and using taxonomies for visual and olfactory classification

Humans are able of distinguishing more than 5000 visual categories even in complex environments using a variety of different visual systems all working in tandem. We seem to be capable of distinguishing thousands of different odors as well. In the machine learning community, many commonly used multi-class classifiers do not scale well to such large numbers of categories. This thesis demonstrates a method of automatically creating application-specific taxonomies to aid in scaling classification algorithms to more than 100 cate- gories using both visual and olfactory data. The visual data consists of images collected online and pollen slides scanned under a microscope. The olfactory data was acquired by constructing a small portable sniffing apparatus which draws air over 10 carbon black polymer composite sensors. We investigate performance when classifying 256 visual categories, 8 or more species of pollen and 130 olfactory categories sampled from common household items and a standardized scratch-and-sniff test. Taxonomies are employed in a divide-and-conquer classification framework which improves classification time while allowing the end user to trade performance for specificity as needed. Before classification can even take place, the pollen counter and electronic nose must filter out a high volume of background “clutter” to detect the categories of interest. In the case of pollen this is done with an efficient cascade of classifiers that rule out most non-pollen before invoking slower multi-class classifiers. In the case of the electronic nose, much of the extraneous noise encountered in outdoor environments can be filtered using a sniffing strategy which preferentially samples the visensor response at frequencies that are relatively immune to background contributions from ambient water vapor. This combination of efficient background rejection with scalable classification algorithms is tested in detail for three separate projects: 1) the Caltech-256 Image Dataset, 2) the Caltech Automated Pollen Identification and Counting System (CAPICS) and 3) a portable electronic nose specially constructed for outdoor use.

Advanced Monte Carlo Simulation and Machine Learning for Frequency Domain Optical Coherence Tomography

Optical Coherence Tomography(OCT) is a popular, rapidly growing imaging technique with an increasing number of bio-medical applications due to its noninvasive nature. However, there are three major challenges in understanding and improving an OCT system: (1) Obtaining an OCT image is not easy. It either takes a real medical experiment or requires days of computer simulation. Without much data, it is difficult to study the physical processes underlying OCT imaging of different objects simply because there aren't many imaged objects. (2) Interpretation of an OCT image is also hard. This challenge is more profound than it appears. For instance, it would require a trained expert to tell from an OCT image of human skin whether there is a lesion or not. This is expensive in its own right, but even the expert cannot be sure about the exact size of the lesion or the width of the various skin layers. The take-away message is that analyzing an OCT image even from a high level would usually require a trained expert, and pixel-level interpretation is simply unrealistic. The reason is simple: we have OCT images but not their underlying ground-truth structure, so there is nothing to learn from. (3) The imaging depth of OCT is very limited (millimeter or sub-millimeter on human tissues). While OCT utilizes infrared light for illumination to stay noninvasive, the downside of this is that photons at such long wavelengths can only penetrate a limited depth into the tissue before getting back-scattered. To image a particular region of a tissue, photons first need to reach that region. As a result, OCT signals from deeper regions of the tissue are both weak (since few photons reached there) and distorted (due to multiple scatterings of the contributing photons). This fact alone makes OCT images very hard to interpret.

This thesis addresses the above challenges by successfully developing an advanced Monte Carlo simulation platform which is 10000 times faster than the state-of-the-art simulator in the literature, bringing down the simulation time from 360 hours to a single minute. This powerful simulation tool not only enables us to efficiently generate as many OCT images of objects with arbitrary structure and shape as we want on a common desktop computer, but it also provides us the underlying ground-truth of the simulated images at the same time because we dictate them at the beginning of the simulation. This is one of the key contributions of this thesis. What allows us to build such a powerful simulation tool includes a thorough understanding of the signal formation process, clever implementation of the importance sampling/photon splitting procedure, efficient use of a voxel-based mesh system in determining photon-mesh interception, and a parallel computation of different A-scans that consist a full OCT image, among other programming and mathematical tricks, which will be explained in detail later in the thesis.

Next we aim at the inverse problem: given an OCT image, predict/reconstruct its ground-truth structure on a pixel level. By solving this problem we would be able to interpret an OCT image completely and precisely without the help from a trained expert. It turns out that we can do much better. For simple structures we are able to reconstruct the ground-truth of an OCT image more than 98% correctly, and for more complicated structures (e.g., a multi-layered brain structure) we are looking at 93%. We achieved this through extensive uses of Machine Learning. The success of the Monte Carlo simulation already puts us in a great position by providing us with a great deal of data (effectively unlimited), in the form of (image, truth) pairs. Through a transformation of the high-dimensional response variable, we convert the learning task into a multi-output multi-class classification problem and a multi-output regression problem. We then build a hierarchy architecture of machine learning models (committee of experts) and train different parts of the architecture with specifically designed data sets. In prediction, an unseen OCT image first goes through a classification model to determine its structure (e.g., the number and the types of layers present in the image); then the image is handed to a regression model that is trained specifically for that particular structure to predict the length of the different layers and by doing so reconstruct the ground-truth of the image. We also demonstrate that ideas from Deep Learning can be useful to further improve the performance.

It is worth pointing out that solving the inverse problem automatically improves the imaging depth, since previously the lower half of an OCT image (i.e., greater depth) can be hardly seen but now becomes fully resolved. Interestingly, although OCT signals consisting the lower half of the image are weak, messy, and uninterpretable to human eyes, they still carry enough information which when fed into a well-trained machine learning model spits out precisely the true structure of the object being imaged. This is just another case where Artificial Intelligence (AI) outperforms human. To the best knowledge of the author, this thesis is not only a success but also the first attempt to reconstruct an OCT image at a pixel level. To even give a try on this kind of task, it would require fully annotated OCT images and a lot of them (hundreds or even thousands). This is clearly impossible without a powerful simulation tool like the one developed in this thesis.

On the uniqueness of singular solutions to boundary-initial value problems in linear elastodynamics

This investigation deals with certain generalizations of the classical uniqueness theorem for the second boundary-initial value problem in the linearized dynamical theory of not necessarily homogeneous nor isotropic elastic solids. First, the regularity assumptions underlying the foregoing theorem are relaxed by admitting stress fields with suitably restricted finite jump discontinuities. Such singularities are familiar from known solutions to dynamical elasticity problems involving discontinuous surface tractions or non-matching boundary and initial conditions. The proof of the appropriate uniqueness theorem given here rests on a generalization of the usual energy identity to the class of singular elastodynamic fields under consideration.

Following this extension of the conventional uniqueness theorem, we turn to a further relaxation of the customary smoothness hypotheses and allow the displacement field to be differentiable merely in a generalized sense, thereby admitting stress fields with square-integrable unbounded local singularities, such as those encountered in the presence of focusing of elastic waves. A statement of the traction problem applicable in these pathological circumstances necessitates the introduction of "weak solutions'' to the field equations that are accompanied by correspondingly weakened boundary and initial conditions. A uniqueness theorem pertaining to this weak formulation is then proved through an adaptation of an argument used by O. Ladyzhenskaya in connection with the first boundary-initial value problem for a second-order hyperbolic equation in a single dependent variable. Moreover, the second uniqueness theorem thus obtained contains, as a special case, a slight modification of the previously established uniqueness theorem covering solutions that exhibit only finite stress-discontinuities.

Dynamic response of hysteretic systems with application to a system containing limited slip

A general class of single degree of freedom systems possessing rate-independent hysteresis is defined. The hysteretic behavior in a system belonging to this class is depicted as a sequence of single-valued functions; at any given time, the current function is determined by some set of mathematical rules concerning the entire previous response of the system. Existence and uniqueness of solutions are established and boundedness of solutions is examined.

An asymptotic solution procedure is used to derive an approximation to the response of viscously damped systems with a small hysteretic nonlinearity and trigonometric excitation. Two properties of the hysteresis loops associated with any given system completely determine this approximation to the response: the area enclosed by each loop, and the average of the ascending and descending branches of each loop.

The approximation, supplemented by numerical calculations, is applied to investigate the steady-state response of a system with limited slip. Such features as disconnected response curves and jumps in response exist for a certain range of system parameters for any finite amount of slip.

To further understand the response of this system, solutions of the initial-value problem are examined. The boundedness of solutions is investigated first. Then the relationship between initial conditions and resulting steady-state solution is examined when multiple steady-state solutions exist. Using the approximate analysis and numerical calculations, it is found that significant regions of initial conditions in the initial condition plane lead to the different asymptotically stable steady-state solutions.

Earthquake response of steel braces and braced steel frames

This thesis consists of three parts. Chapter 2 deals with the dynamic buckling behavior of steel braces under cyclic axial end displacement. Braces under such a loading condition belong to a class of "acceleration magnifying" structural components, in which a small motion at the loading points can cause large internal acceleration and inertia. This member-level inertia is frequently ignored in current studies of braces and braced structures. This chapter shows that, under certain conditions, the inclusion of the member-level inertia can lead to brace behavior fundamentally different from that predicted by the quasi-static method. This result is to have significance in the correct use of the quasi-static, pseudo-dynamic and static condensation methods in the simulation of braces or braced structures under dynamic loading. The strain magnitude and distribution in the braces are also studied in this chapter.

Chapter 3 examines the effect of column uplift on the earthquake response of braced steel frames and explores the feasibility of flexible column-base anchoring. It is found that fully anchored braced-bay columns can induce extremely large internal forces in the braced-bay members and their connections, thus increasing the risk of failures observed in recent earthquakes. Flexible braced-bay column anchoring can significantly reduce the braced bay member force, but at the same time also introduces large story drift and column uplift. The pounding of an uplifting column with its support can result in very high compressive axial force.

Chapter 4 conducts a comparative study on the effectiveness of a proposed non-buckling bracing system and several conventional bracing systems. The non-buckling bracing system eliminates buckling and thus can be composed of small individual braces distributed widely in a structure to reduce bracing force concentration and increase redundancy. The elimination of buckling results in a significantly more effective bracing system compared with the conventional bracing systems. Among the conventional bracing systems, bracing configurations and end conditions for the bracing members affect the effectiveness.

The studies in Chapter 3 and Chapter 4 also indicate that code-designed conventionally braced steel frames can experience unacceptably severe response under the strong ground motions recorded during the recent Northridge and Kobe earthquakes.

Symmetric representation of an integral domain over a subdomain

Let F(θ) be a separable extension of degree n of a field F. Let Δ and D be integral domains with quotient fields F(θ) and F respectively. Assume that Δ ᴝ D. A mapping φ of Δ into the n x n D matrices is called a Δ/D rep if (i) it is a ring isomorphism and (ii) it maps d onto dI_n whenever d ϵ D. If the matrices are also symmetric, φ is a Δ/D symrep.

Every Δ/D rep can be extended uniquely to an F(θ)/F rep. This extension is completely determined by the image of θ. Two Δ/D reps are called equivalent if the images of θ differ by a D unimodular similarity. There is a one-to-one correspondence between classes of Δ/D reps and classes of Δ ideals having an n element basis over D.

The condition that a given Δ/D rep class contain a Δ/D symrep can be phrased in various ways. Using these formulations it is possible to (i) bound the number of symreps in a given class, (ii) count the number of symreps if F is finite, (iii) establish the existence of an F(θ)/F symrep when n is odd, F is an algebraic number field, and F(θ) is totally real if F is formally real (for n = 3 see Sapiro, “Characteristic polynomials of symmetric matrices” Sibirsk. Mat. Ž. 3 (1962) pp. 280-291), and (iv) study the case D = Z, the integers (see Taussky, “On matrix classes corresponding to an ideal and its inverse” Illinois J. Math. 1 (1957) pp. 108-113 and Faddeev, “On the characteristic equations of rational symmetric matrices” Dokl. Akad. Nauk SSSR 58 (1947) pp. 753-754).

The case D = Z and n = 2 is studied in detail. Let Δ’ be an integral domain also having quotient field F(θ) and such that Δ’ ᴝ Δ. Let φ be a Δ/Z symrep. A method is given for finding a Δ’/Z symrep ʘ such that the Δ’ ideal class corresponding to the class of ʘ is an extension to Δ’ of the Δ ideal class corresponding to the class of φ. The problem of finding all Δ/Z symreps equivalent to a given one is studied.

Longitudinal dispersion in laboratory and natural streams

This study concerns the longitudinal dispersion of fluid particles which are initially distributed uninformly over one cross section of a uniform, steady, turbulent open channel flow. The primary focus is on developing a method to predict the rate of dispersion in a natural stream.

Taylor's method of determining a dispersion coefficient, previously applied to flow in pipes and two-dimensional open channels, is extended to a class of three-dimensional flows which have large width-to-depth ratios, and in which the velocity varies continuously with lateral cross-sectional position. Most natural streams are included. The dispersion coefficient for a natural stream may be predicted from measurements of the channel cross-sectional geometry, the cross-sectional distribution of velocity, and the overall channel shear velocity. Tracer experiments are not required.

Large values of the dimensionless dispersion coefficient D/rU* are explained by lateral variations in downstream velocity. In effect, the characteristic length of the cross section is shown to be proportional to the width, rather than the hydraulic radius. The dimensionless dispersion coefficient depends approximately on the square of the width to depth ratio.

A numerical program is given which is capable of generating the entire dispersion pattern downstream from an instantaneous point or plane source of pollutant. The program is verified by the theory for two-dimensional flow, and gives results in good agreement with laboratory and field experiments.

Both laboratory and field experiments are described. Twenty-one laboratory experiments were conducted: thirteen in two-dimensional flows, over both smooth and roughened bottoms; and eight in three-dimensional flows, formed by adding extreme side roughness to produce lateral velocity variations. Four field experiments were conducted in the Green-Duwamish River, Washington.

Both laboratory and flume experiments prove that in three-dimensional flow the dominant mechanism for dispersion is lateral velocity variation. For instance, in one laboratory experiment the dimensionless dispersion coefficient D/rU* (where r is the hydraulic radius and U* the shear velocity) was increased by a factory of ten by roughening the channel banks. In three-dimensional laboratory flow, D/rU* varied from 190 to 640, a typical range for natural streams. For each experiment, the measured dispersion coefficient agreed with that predicted by the extension of Taylor's analysis within a maximum error of 15%. For the Green-Duwamish River, the average experimentally measured dispersion coefficient was within 5% of the prediction.

A generalized Hausdorff dimension for functions and sets

Let E be a compact subset of the n-dimensional unit cube, 1_n, and let C be a collection of convex bodies, all of positive n-dimensional Lebesgue measure, such that C contains bodies with arbitrarily small measure. The dimension of E with respect to the covering class C is defined to be the number

d_C(E) = sup(β:H_{β, C}(E) > 0),

where H_{β, C} is the outer measure

inf(Ʃm(C_i)^β:UC_i Ↄ E, C_i ϵ C) .

Only the one and two-dimensional cases are studied. Moreover, the covering classes considered are those consisting of intervals and rectangles, parallel to the coordinate axes, and those closed under translations. A covering class is identified with a set of points in the left-open portion, 1’_n, of 1_n, whose closure intersects 1_n - 1’_n. For n = 2, the outer measure H_{β, C} is adopted in place of the usual:

Inf(Ʃ(diam. (C_i))^β: UC_i Ↄ E, C_i ϵ C),

for the purpose of studying the influence of the shape of the covering sets on the dimension d_C(E).

If E is a closed set in 1₁, let M(E) be the class of all non-decreasing functions μ(x), supported on E with μ(x) = 0, x ≤ 0 and μ(x) = 1, x ≥ 1. Define for each μ ϵ M(E),

d_C(μ) = lim/c → inf/0 log ∆μ(c)/log c , (c ϵ C)

where ∆μ(c) = v/x (μ(x+c) – μ(x)). It is shown that

d_C(E) = sup (d_C(μ):μ ϵ M(E)).

This notion of dimension is extended to a certain class Ӻ of sub-additive functions, and the problem of studying the behavior of d_C(E) as a function of the covering class C is reduced to the study of d_C(f) where f ϵ Ӻ. Specifically, the set of points in 1₁,

(*) {d_B(F), d_C(f)): f ϵ Ӻ}

is characterized by a comparison of the relative positions of the points of B and C. A region of the form (*) is always closed and doubly-starred with respect to the points (0, 0) and (1, 1). Conversely, given any closed region in 1₂, doubly-starred with respect to (0, 0) and (1, 1), there are covering classes B and C such that (*) is exactly that region. All of the results are shown to apply to the dimension of closed sets E. Similar results can be obtained when a finite number of covering classes are considered.

In two dimensions, the notion of dimension is extended to the class M, of functions f(x, y), non-decreasing in x and y, supported on 1₂ with f(x, y) = 0 for x · y = 0 and f(1, 1) = 1, by the formula

d_C(f) = lim/s · t → inf/0 log ∆f(s, t)/log s · t , (s, t) ϵ C

where

∆f(s, t) = V/x, y (f(x+s, y+t) – f(x+s, y) – f(x, y+t) + f(x, t)).

A characterization of the equivalence d_C1(f) = d_C2(f) for all f ϵ M, is given by comparison of the gaps in the sets of products s · t and quotients s/t, (s, t) ϵ C_i (I = 1, 2).

Normal structures and automorphism groups of t-designs

Combinatorial configurations known as t-designs are studied. These are pairs ˂B, ∏˃, where each element of B is a k-subset of ∏, and each t-design occurs in exactly λ elements of B, for some fixed integers k and λ. A theory of internal structure of t-designs is developed, and it is shown that any t-design can be decomposed in a natural fashion into a sequence of “simple” subdesigns. The theory is quite similar to the analysis of a group with respect to its normal subgroups, quotient groups, and homomorphisms. The analogous concepts of normal subdesigns, quotient designs, and design homomorphisms are all defined and used.

This structure theory is then applied to the class of t-designs whose automorphism groups are transitive on sets of t points. It is shown that if G is a permutation group transitive on sets of t letters and ф is any set of letters, then images of ф under G form a t-design whose parameters may be calculated from the group G. Such groups are discussed, especially for the case t = 2, and the normal structure of such designs is considered. Theorem 2.2.12 gives necessary and sufficient conditions for a t-design to be simple, purely in terms of the automorphism group of the design. Some constructions are given.

Finally, 2-designs with k = 3 and λ = 2 are considered in detail. These designs are first considered in general, with examples illustrating some of the configurations which can arise. Then an attempt is made to classify all such designs with an automorphism group transitive on pairs of points. Many cases are eliminated of reduced to combinations of Steiner triple systems. In the remaining cases, the simple designs are determined to consist of one infinite class and one exceptional case.