Matching Items (36)
Description
Research on combinatorics education is sparse when compared with other fields in mathematics education. This research attempted to contribute to the dearth of literature by examining students' reasoning about enumerative combinatorics problems and how students conceptualize the set of elements being counted in such problems, called the solution set. In particular, the focus was on the stable patterns of reasoning, known as ways of thinking, which students applied in a variety of combinatorial situations and tasks. This study catalogued students' ways of thinking about solution sets as they progressed through an instructional sequence. In addition, the relationships between the catalogued ways of thinking were explored. Further, the study investigated the challenges students experienced as they interacted with the tasks and instructional interventions, and how students' ways of thinking evolved as these challenges were overcome. Finally, it examined the role of instruction in guiding students to develop and extend their ways of thinking. Two pairs of undergraduate students with no formal experience with combinatorics participated in one of the two consecutive teaching experiments conducted in Spring 2012. Many ways of thinking emerged through the grounded theory analysis of the data, but only eight were identified as robust. These robust ways of thinking were classified into three categories: Subsets, Odometer, and Problem Posing. The Subsets category encompasses two ways of thinking, both of which ultimately involve envisioning the solution set as the union of subsets. The three ways of thinking in Odometer category involve holding an item or a set of items constant and systematically varying the other items involved in the counting process. The ways of thinking belonging to Problem Posing category involve spontaneously posing new, related combinatorics problems and finding relationships between the solution sets of the original and the new problem. The evolution of students' ways of thinking in the Problem Posing category was analyzed. This entailed examining the perturbation experienced by students and the resulting accommodation of their thinking. It was found that such perturbation and its resolution was often the result of an instructional intervention. Implications for teaching practice are discussed.
ContributorsHalani, Aviva (Author) / Roh, Kyeong Hah (Thesis advisor) / Fishel, Susanna (Committee member) / Saldanha, Luis (Committee member) / Thompson, Patrick (Committee member) / Zandieh, Michelle (Committee member) / Arizona State University (Publisher)
Created2013
Description
Advances in data collection technologies have made it cost-effective to obtain heterogeneous data from multiple data sources. Very often, the data are of very high dimension and feature selection is preferred in order to reduce noise, save computational cost and learn interpretable models. Due to the multi-modality nature of heterogeneous data, it is interesting to design efficient machine learning models that are capable of performing variable selection and feature group (data source) selection simultaneously (a.k.a bi-level selection). In this thesis, I carry out research along this direction with a particular focus on designing efficient optimization algorithms. I start with a unified bi-level learning model that contains several existing feature selection models as special cases. Then the proposed model is further extended to tackle the block-wise missing data, one of the major challenges in the diagnosis of Alzheimer's Disease (AD). Moreover, I propose a novel interpretable sparse group feature selection model that greatly facilitates the procedure of parameter tuning and model selection. Last but not least, I show that by solving the sparse group hard thresholding problem directly, the sparse group feature selection model can be further improved in terms of both algorithmic complexity and efficiency. Promising results are demonstrated in the extensive evaluation on multiple real-world data sets.
ContributorsXiang, Shuo (Author) / Ye, Jieping (Thesis advisor) / Mittelmann, Hans D (Committee member) / Davulcu, Hasan (Committee member) / He, Jingrui (Committee member) / Arizona State University (Publisher)
Created2014
Description
This dissertation describes an investigation of four students' ways of thinking about functions of two variables and rate of change of those two-variable functions. Most secondary, introductory algebra, pre-calculus, and first and second semester calculus courses do not require students to think about functions of more than one variable. Yet vector calculus, calculus on manifolds, linear algebra, and differential equations all rest upon the idea of functions of two (or more) variables. This dissertation contributes to understanding productive ways of thinking that can support students in thinking about functions of two or more variables as they describe complex systems with multiple variables interacting. This dissertation focuses on modeling the way of thinking of four students who participated in a specific instructional sequence designed to explore the limits of their ways of thinking and in turn, develop a robust model that could explain, describe, and predict students' actions relative to specific tasks. The data was collected using a teaching experiment methodology, and the tasks within the teaching experiment leveraged quantitative reasoning and covariation as foundations of students developing a coherent understanding of two-variable functions and their rates of change. The findings of this study indicated that I could characterize students' ways of thinking about two-variable functions by focusing on their use of novice and/or expert shape thinking, and the students' ways of thinking about rate of change by focusing on their quantitative reasoning. The findings suggested that quantitative and covariational reasoning were foundational to a student's ability to generalize their understanding of a single-variable function to two or more variables, and their conception of rate of change to rate of change at a point in space. These results created a need to better understand how experts in the field, such as mathematicians and mathematics educators, thinking about multivariable functions and their rates of change.
ContributorsWeber, Eric David (Author) / Thompson, Patrick (Thesis advisor) / Middleton, James (Committee member) / Carlson, Marilyn (Committee member) / Saldanha, Luis (Committee member) / Milner, Fabio (Committee member) / Van de Sande, Carla (Committee member) / Arizona State University (Publisher)
Created2012
Description
This thesis studies recommendation systems and considers joint sampling and learning. Sampling in recommendation systems is to obtain users' ratings on specific items chosen by the recommendation platform, and learning is to infer the unknown ratings of users to items given the existing data. In this thesis, the problem is formulated as an adaptive matrix completion problem in which sampling is to reveal the unknown entries of a $U\times M$ matrix where $U$ is the number of users, $M$ is the number of items, and each entry of the $U\times M$ matrix represents the rating of a user to an item. In the literature, this matrix completion problem has been studied under a static setting, i.e., recovering the matrix based on a set of partial ratings. This thesis considers both sampling and learning, and proposes an adaptive algorithm. The algorithm adapts its sampling and learning based on the existing data. The idea is to sample items that reveal more information based on the previous sampling results and then learn based on clustering. Performance of the proposed algorithm has been evaluated using simulations.
ContributorsZhu, Lingfang (Author) / Xue, Guoliang (Thesis advisor) / He, Jingrui (Committee member) / Tong, Hanghang (Committee member) / Arizona State University (Publisher)
Created2015
Description
Diffusion processes in networks can be used to model many real-world processes, such as the propagation of a rumor on social networks and cascading failures on power networks. Analysis of diffusion processes in networks can help us answer important questions such as the role and the importance of each node in the network for spreading the diffusion and how to top or contain a cascading failure in the network. This dissertation consists of three parts.
In the first part, we study the problem of locating multiple diffusion sources in networks under the Susceptible-Infected-Recovered (SIR) model. Given a complete snapshot of the network, we developed a sample-path-based algorithm, named clustering and localization, and proved that for regular trees, the estimators produced by the proposed algorithm are within a constant distance from the real sources with a high probability. Then, we considered the case in which only a partial snapshot is observed and proposed a new algorithm, named Optimal-Jordan-Cover (OJC). The algorithm first extracts a subgraph using a candidate selection algorithm that selects source candidates based on the number of observed infected nodes in their neighborhoods. Then, in the extracted subgraph, OJC finds a set of nodes that "cover" all observed infected nodes with the minimum radius. The set of nodes is called the Jordan cover, and is regarded as the set of diffusion sources. We proved that OJC can locate all sources with probability one asymptotically with partial observations in the Erdos-Renyi (ER) random graph. Multiple experiments on different networks were done, which show our algorithms outperform others.
In the second part, we tackle the problem of reconstructing the diffusion history from partial observations. We formulated the diffusion history reconstruction problem as a maximum a posteriori (MAP) problem and proved the problem is NP hard. Then we proposed a step-by- step reconstruction algorithm, which can always produce a diffusion history that is consistent with the partial observations. Our experimental results based on synthetic and real networks show that the algorithm significantly outperforms some existing methods.
In the third part, we consider the problem of improving the robustness of an interdependent network by rewiring a small number of links during a cascading attack. We formulated the problem as a Markov decision process (MDP) problem. While the problem is NP-hard, we developed an effective and efficient algorithm, RealWire, to robustify the network and to mitigate the damage during the attack. Extensive experimental results show that our algorithm outperforms other algorithms on most of the robustness metrics.
In the first part, we study the problem of locating multiple diffusion sources in networks under the Susceptible-Infected-Recovered (SIR) model. Given a complete snapshot of the network, we developed a sample-path-based algorithm, named clustering and localization, and proved that for regular trees, the estimators produced by the proposed algorithm are within a constant distance from the real sources with a high probability. Then, we considered the case in which only a partial snapshot is observed and proposed a new algorithm, named Optimal-Jordan-Cover (OJC). The algorithm first extracts a subgraph using a candidate selection algorithm that selects source candidates based on the number of observed infected nodes in their neighborhoods. Then, in the extracted subgraph, OJC finds a set of nodes that "cover" all observed infected nodes with the minimum radius. The set of nodes is called the Jordan cover, and is regarded as the set of diffusion sources. We proved that OJC can locate all sources with probability one asymptotically with partial observations in the Erdos-Renyi (ER) random graph. Multiple experiments on different networks were done, which show our algorithms outperform others.
In the second part, we tackle the problem of reconstructing the diffusion history from partial observations. We formulated the diffusion history reconstruction problem as a maximum a posteriori (MAP) problem and proved the problem is NP hard. Then we proposed a step-by- step reconstruction algorithm, which can always produce a diffusion history that is consistent with the partial observations. Our experimental results based on synthetic and real networks show that the algorithm significantly outperforms some existing methods.
In the third part, we consider the problem of improving the robustness of an interdependent network by rewiring a small number of links during a cascading attack. We formulated the problem as a Markov decision process (MDP) problem. While the problem is NP-hard, we developed an effective and efficient algorithm, RealWire, to robustify the network and to mitigate the damage during the attack. Extensive experimental results show that our algorithm outperforms other algorithms on most of the robustness metrics.
ContributorsChen, Zhen (Author) / Ying, Lei (Thesis advisor) / Tong, Hanghang (Thesis advisor) / Zhang, Junshan (Committee member) / He, Jingrui (Committee member) / Arizona State University (Publisher)
Created2018
Description
Network mining has been attracting a lot of research attention because of the prevalence of networks. As the world is becoming increasingly connected and correlated, networks arising from inter-dependent application domains are often collected from different sources, forming the so-called multi-sourced networks. Examples of such multi-sourced networks include critical infrastructure networks, multi-platform social networks, cross-domain collaboration networks, and many more. Compared with single-sourced network, multi-sourced networks bear more complex structures and therefore could potentially contain more valuable information.
This thesis proposes a multi-layered HITS (Hyperlink-Induced Topic Search) algorithm to perform the ranking task on multi-sourced networks. Specifically, each node in the network receives an authority score and a hub score for evaluating the value of the node itself and the value of its outgoing links respectively. Based on a recent multi-layered network model, which allows more flexible dependency structure across different sources (i.e., layers), the proposed algorithm leverages both within-layer smoothness and cross-layer consistency. This essentially allows nodes from different layers to be ranked accordingly. The multi-layered HITS is formulated as a regularized optimization problem with non-negative constraint and solved by an iterative update process. Extensive experimental evaluations demonstrate the effectiveness and explainability of the proposed algorithm.
This thesis proposes a multi-layered HITS (Hyperlink-Induced Topic Search) algorithm to perform the ranking task on multi-sourced networks. Specifically, each node in the network receives an authority score and a hub score for evaluating the value of the node itself and the value of its outgoing links respectively. Based on a recent multi-layered network model, which allows more flexible dependency structure across different sources (i.e., layers), the proposed algorithm leverages both within-layer smoothness and cross-layer consistency. This essentially allows nodes from different layers to be ranked accordingly. The multi-layered HITS is formulated as a regularized optimization problem with non-negative constraint and solved by an iterative update process. Extensive experimental evaluations demonstrate the effectiveness and explainability of the proposed algorithm.
ContributorsYu, Haichao (Author) / Tong, Hanghang (Thesis advisor) / He, Jingrui (Committee member) / Yang, Yezhou (Committee member) / Arizona State University (Publisher)
Created2018
Description
There have been a number of studies that have examined students’ difficulties in understanding the idea of logarithm and the effectiveness of non-traditional interventions. However, there have been few studies that have examined the understandings students develop and need to develop when completing conceptually oriented logarithmic lessons. In this document, I present the three papers of my dissertation study. The first paper examines two students’ development of concepts foundational to the idea of logarithm. This paper discusses two essential understandings that were revealed to be problematic and essential for students’ development of productive meanings for exponents, logarithms and logarithmic properties. The findings of this study informed my later work to support students in understanding logarithms, their properties and logarithmic functions. The second paper examines two students’ development of the idea of logarithm. This paper describes the reasoning abilities two students exhibited as they engaged with tasks designed to foster their construction of more productive meanings for the idea of logarithm. The findings of this study provide novel insights for supporting students in understanding the idea of logarithm meaningfully. Finally, the third paper begins with an examination of the historical development of the idea of logarithm. I then leveraged the insights of this literature review and the first two papers to perform a conceptual analysis of what is involved in learning and understanding the idea of logarithm. The literature review and conceptual analysis contributes novel and useful information for curriculum developers, instructors, and other researchers studying student learning of this idea.
ContributorsKuper Flores, Emily Ginamarie (Author) / Carlson, Marilyn (Thesis advisor) / Thompson, Patrick (Committee member) / Milner, Fabio (Committee member) / Zazkis, Dov (Committee member) / Czocher, Jennifer (Committee member) / Arizona State University (Publisher)
Created2018
Description
Unsupervised learning of time series data, also known as temporal clustering, is a challenging problem in machine learning. This thesis presents a novel algorithm, Deep Temporal Clustering (DTC), to naturally integrate dimensionality reduction and temporal clustering into a single end-to-end learning framework, fully unsupervised. The algorithm utilizes an autoencoder for temporal dimensionality reduction and a novel temporal clustering layer for cluster assignment. Then it jointly optimizes the clustering objective and the dimensionality reduction objective. Based on requirement and application, the temporal clustering layer can be customized with any temporal similarity metric. Several similarity metrics and state-of-the-art algorithms are considered and compared. To gain insight into temporal features that the network has learned for its clustering, a visualization method is applied that generates a region of interest heatmap for the time series. The viability of the algorithm is demonstrated using time series data from diverse domains, ranging from earthquakes to spacecraft sensor data. In each case, the proposed algorithm outperforms traditional methods. The superior performance is attributed to the fully integrated temporal dimensionality reduction and clustering criterion.
ContributorsMadiraju, NaveenSai (Author) / Liang, Jianming (Thesis advisor) / Wang, Yalin (Thesis advisor) / He, Jingrui (Committee member) / Arizona State University (Publisher)
Created2018
Description
The concept of distribution is one of the core ideas of probability theory and inferential statistics, if not the core idea. Many introductory statistics textbooks pay lip service to stochastic/random processes but how do students think about these processes? This study sought to explore what understandings of stochastic process students develop as they work through materials intended to support them in constructing the long-run behavior meaning for distribution.
I collected data in three phases. First, I conducted a set of task-based clinical interviews that allowed me to build initial models for the students’ meanings for randomness and probability. Second, I worked with Bonnie in an exploratory teaching setting through three sets of activities to see what meanings she would develop for randomness and stochastic process. The final phase consisted of me working with Danielle as she worked through the same activities as Bonnie but this time in teaching experiment setting where I used a series of interventions to test out how Danielle was thinking about stochastic processes.
My analysis shows that students can be aware that the word “random” lives in two worlds, thereby having conflicting meanings. Bonnie’s meaning for randomness evolved over the course of the study from an unproductive meaning centered on the emotions of the characters in the context to a meaning that randomness is the lack of a pattern. Bonnie’s lack of pattern meaning for randomness subsequently underpinned her image of stochastic/processes, leading her to engage in pattern-hunting behavior every time she needed to classify a process as stochastic or not. Danielle’s image of a stochastic process was grounded in whether she saw the repetition as being reproducible (process can be repeated, and outcomes are identical to prior time through the process) or replicable (process can be repeated but the outcomes aren’t in the same order as before). Danielle employed a strategy of carrying out several trials of the process, resetting the applet, and then carrying out the process again, making replicability central to her thinking.
I collected data in three phases. First, I conducted a set of task-based clinical interviews that allowed me to build initial models for the students’ meanings for randomness and probability. Second, I worked with Bonnie in an exploratory teaching setting through three sets of activities to see what meanings she would develop for randomness and stochastic process. The final phase consisted of me working with Danielle as she worked through the same activities as Bonnie but this time in teaching experiment setting where I used a series of interventions to test out how Danielle was thinking about stochastic processes.
My analysis shows that students can be aware that the word “random” lives in two worlds, thereby having conflicting meanings. Bonnie’s meaning for randomness evolved over the course of the study from an unproductive meaning centered on the emotions of the characters in the context to a meaning that randomness is the lack of a pattern. Bonnie’s lack of pattern meaning for randomness subsequently underpinned her image of stochastic/processes, leading her to engage in pattern-hunting behavior every time she needed to classify a process as stochastic or not. Danielle’s image of a stochastic process was grounded in whether she saw the repetition as being reproducible (process can be repeated, and outcomes are identical to prior time through the process) or replicable (process can be repeated but the outcomes aren’t in the same order as before). Danielle employed a strategy of carrying out several trials of the process, resetting the applet, and then carrying out the process again, making replicability central to her thinking.
ContributorsHatfield, Neil (Author) / Thompson, Patrick (Thesis advisor) / Carlson, Marilyn (Committee member) / Middleton, James (Committee member) / Lehrer, Richard (Committee member) / Reiser, Mark R. (Committee member) / Arizona State University (Publisher)
Created2019
Description
This thesis presents a family of adaptive curvature methods for gradient-based stochastic optimization. In particular, a general algorithmic framework is introduced along with a practical implementation that yields an efficient, adaptive curvature gradient descent algorithm. To this end, a theoretical and practical link between curvature matrix estimation and shrinkage methods for covariance matrices is established. The use of shrinkage improves estimation accuracy of the curvature matrix when data samples are scarce. This thesis also introduce several insights that result in data- and computation-efficient update equations. Empirical results suggest that the proposed method compares favorably with existing second-order techniques based on the Fisher or Gauss-Newton and with adaptive stochastic gradient descent methods on both supervised and reinforcement learning tasks.
ContributorsBarron, Trevor (Author) / Ben Amor, Heni (Thesis advisor) / He, Jingrui (Committee member) / Levihn, Martin (Committee member) / Arizona State University (Publisher)
Created2019