Limits...
A theoretically-sufficient and computationally-practical technique for deterministic frequency seriation.

Lipo CP, Madsen ME, Dunnell RC - PLoS ONE (2015)

Bottom Line: This compression removes the ability to use all of the features of our data to fit to the seriation model, obscuring violations of the model, and thus lessens our ability to understand the degree to which the resulting order is chronological, spatial, or a mixture.Our initial implementation of IDSS does not solve all the problems of seriation, but begins to moves towards a resolution of a long-standing problem in archaeology while opening up new avenues of research into the study of cultural relatedness.We demonstrate the utility of IDSS using late prehistoric decorated ceramics from the Mississippi River Valley.

View Article: PubMed Central - PubMed

Affiliation: Department of Anthropology and IIRMES, California State University Long Beach, 1250 Bellflower Blvd., Long Beach, CA 90840, USA.

ABSTRACT
Frequency seriation played a key role in the formation of archaeology as a discipline due to its ability to generate chronologies. Interest in its utility for exploring issues of contemporary interest beyond chronology, however, has been limited. This limitation is partly due to a lack of quantitative algorithms that can be used to build deterministic seriation solutions. When the number of assemblages becomes greater than just a handful, the resources required for evaluation of possible permutations easily outstrips available computing capacity. On the other hand, probabilistic approaches to creating seriations offer a computationally manageable alternative but rely upon a compressed description of the data to order assemblages. This compression removes the ability to use all of the features of our data to fit to the seriation model, obscuring violations of the model, and thus lessens our ability to understand the degree to which the resulting order is chronological, spatial, or a mixture. Recently, frequency seriation has been reconceived as a general method for studying the structure of cultural transmission through time and across space. The use of an evolution-based framework renews the potential for seriation but also calls for a computationally feasible algorithm that is capable of producing solutions under varying configurations, without manual trial and error fitting. Here, we introduce the Iterative Deterministic Seriation Solution (IDSS) for constructing frequency seriations, an algorithm that dramatically constrains the search for potential valid orders of assemblages. Our initial implementation of IDSS does not solve all the problems of seriation, but begins to moves towards a resolution of a long-standing problem in archaeology while opening up new avenues of research into the study of cultural relatedness. We demonstrate the utility of IDSS using late prehistoric decorated ceramics from the Mississippi River Valley. The results compare favorably to previous analyses but add new details into the structure of cultural transmission of these late prehistoric populations.

No MeSH data available.


Related in: MedlinePlus

Example of the IDSS algorithm seriation output for 15 assemblages with 6 types.This seriation order was generated using a threshold of 0.10. Panel A takes the form of traditional centered-bar format where the empty bars indicate relative proportion of the type and small black bars represent confidence intervals of α = 0.05 for the type proportions. Panel B is the same order in graph form. Note that while hand-sorting of this example data could be relatively easily done, the IDSS algorithm ensures that the longest possible solution or set of solutions is found. In real-world cases, patterns of type frequencies often includes the effects of sample size, space and other transmission processes. In these cases, a systematic deterministic method is necessary to ensure comprehensive and statistically sound solutions.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4414518&req=5

pone.0124942.g005: Example of the IDSS algorithm seriation output for 15 assemblages with 6 types.This seriation order was generated using a threshold of 0.10. Panel A takes the form of traditional centered-bar format where the empty bars indicate relative proportion of the type and small black bars represent confidence intervals of α = 0.05 for the type proportions. Panel B is the same order in graph form. Note that while hand-sorting of this example data could be relatively easily done, the IDSS algorithm ensures that the longest possible solution or set of solutions is found. In real-world cases, patterns of type frequencies often includes the effects of sample size, space and other transmission processes. In these cases, a systematic deterministic method is necessary to ensure comprehensive and statistically sound solutions.

Mentions: We have coded the IDSS algorithm in Python (see S1 Text for the full algorithm). Tests of our IDSS implementation show that with artificially generated data in which an a priori solution is known, the correct solution set is always identified. In Panel A of Fig 5, we show a set of 15 unordered assemblages each with 6 types. Using a threshold of 0.10 (i.e., the maximum acceptable difference between assemblage frequencies is no more than 10%), the IDSS algorithm was able to locate the optimal seriation order of these assemblages out of all possible valid solutions in just over 1470 seconds, using a 2013-era quad-core computer. This length of time might appear slow relative to quick hand-sorting but the results of intuitive shuffling of graphical representations cannot ensure that the largest possible order is identified nor can it find all the equally valid solutions that might be present. Traditional brute force sorting approaches that evaluate the entire search space can easily take many years (Table 1). Using IDSS instead of hand-sorting allows identification of all valid solutions from groups of 20 or fewer assemblages on a single desktop computer. Twenty or so assemblages is a common scale of analysis, at least for many archaeological cases conducted within local regions, and it is important for a DFS algorithm to be able to produce optimal solutions for this scale of data, on commonly available hardware. In particular, many large sets of assemblages break down into much smaller subsets when ordered and thus can be analyzed quickly. Solutions with larger numbers of assemblages or few solution subsets require carefully setting the maximum differences between assemblages and using a computing cluster to further parallelize the evaluation of solutions.


A theoretically-sufficient and computationally-practical technique for deterministic frequency seriation.

Lipo CP, Madsen ME, Dunnell RC - PLoS ONE (2015)

Example of the IDSS algorithm seriation output for 15 assemblages with 6 types.This seriation order was generated using a threshold of 0.10. Panel A takes the form of traditional centered-bar format where the empty bars indicate relative proportion of the type and small black bars represent confidence intervals of α = 0.05 for the type proportions. Panel B is the same order in graph form. Note that while hand-sorting of this example data could be relatively easily done, the IDSS algorithm ensures that the longest possible solution or set of solutions is found. In real-world cases, patterns of type frequencies often includes the effects of sample size, space and other transmission processes. In these cases, a systematic deterministic method is necessary to ensure comprehensive and statistically sound solutions.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4414518&req=5

pone.0124942.g005: Example of the IDSS algorithm seriation output for 15 assemblages with 6 types.This seriation order was generated using a threshold of 0.10. Panel A takes the form of traditional centered-bar format where the empty bars indicate relative proportion of the type and small black bars represent confidence intervals of α = 0.05 for the type proportions. Panel B is the same order in graph form. Note that while hand-sorting of this example data could be relatively easily done, the IDSS algorithm ensures that the longest possible solution or set of solutions is found. In real-world cases, patterns of type frequencies often includes the effects of sample size, space and other transmission processes. In these cases, a systematic deterministic method is necessary to ensure comprehensive and statistically sound solutions.
Mentions: We have coded the IDSS algorithm in Python (see S1 Text for the full algorithm). Tests of our IDSS implementation show that with artificially generated data in which an a priori solution is known, the correct solution set is always identified. In Panel A of Fig 5, we show a set of 15 unordered assemblages each with 6 types. Using a threshold of 0.10 (i.e., the maximum acceptable difference between assemblage frequencies is no more than 10%), the IDSS algorithm was able to locate the optimal seriation order of these assemblages out of all possible valid solutions in just over 1470 seconds, using a 2013-era quad-core computer. This length of time might appear slow relative to quick hand-sorting but the results of intuitive shuffling of graphical representations cannot ensure that the largest possible order is identified nor can it find all the equally valid solutions that might be present. Traditional brute force sorting approaches that evaluate the entire search space can easily take many years (Table 1). Using IDSS instead of hand-sorting allows identification of all valid solutions from groups of 20 or fewer assemblages on a single desktop computer. Twenty or so assemblages is a common scale of analysis, at least for many archaeological cases conducted within local regions, and it is important for a DFS algorithm to be able to produce optimal solutions for this scale of data, on commonly available hardware. In particular, many large sets of assemblages break down into much smaller subsets when ordered and thus can be analyzed quickly. Solutions with larger numbers of assemblages or few solution subsets require carefully setting the maximum differences between assemblages and using a computing cluster to further parallelize the evaluation of solutions.

Bottom Line: This compression removes the ability to use all of the features of our data to fit to the seriation model, obscuring violations of the model, and thus lessens our ability to understand the degree to which the resulting order is chronological, spatial, or a mixture.Our initial implementation of IDSS does not solve all the problems of seriation, but begins to moves towards a resolution of a long-standing problem in archaeology while opening up new avenues of research into the study of cultural relatedness.We demonstrate the utility of IDSS using late prehistoric decorated ceramics from the Mississippi River Valley.

View Article: PubMed Central - PubMed

Affiliation: Department of Anthropology and IIRMES, California State University Long Beach, 1250 Bellflower Blvd., Long Beach, CA 90840, USA.

ABSTRACT
Frequency seriation played a key role in the formation of archaeology as a discipline due to its ability to generate chronologies. Interest in its utility for exploring issues of contemporary interest beyond chronology, however, has been limited. This limitation is partly due to a lack of quantitative algorithms that can be used to build deterministic seriation solutions. When the number of assemblages becomes greater than just a handful, the resources required for evaluation of possible permutations easily outstrips available computing capacity. On the other hand, probabilistic approaches to creating seriations offer a computationally manageable alternative but rely upon a compressed description of the data to order assemblages. This compression removes the ability to use all of the features of our data to fit to the seriation model, obscuring violations of the model, and thus lessens our ability to understand the degree to which the resulting order is chronological, spatial, or a mixture. Recently, frequency seriation has been reconceived as a general method for studying the structure of cultural transmission through time and across space. The use of an evolution-based framework renews the potential for seriation but also calls for a computationally feasible algorithm that is capable of producing solutions under varying configurations, without manual trial and error fitting. Here, we introduce the Iterative Deterministic Seriation Solution (IDSS) for constructing frequency seriations, an algorithm that dramatically constrains the search for potential valid orders of assemblages. Our initial implementation of IDSS does not solve all the problems of seriation, but begins to moves towards a resolution of a long-standing problem in archaeology while opening up new avenues of research into the study of cultural relatedness. We demonstrate the utility of IDSS using late prehistoric decorated ceramics from the Mississippi River Valley. The results compare favorably to previous analyses but add new details into the structure of cultural transmission of these late prehistoric populations.

No MeSH data available.


Related in: MedlinePlus