text:
# Multiplication or addition of decimals or integers for prehighschool; non deterministic testing

I'm creating a simple android app for pre-highschool students which teaches the very basics of addition or multiplication of integers or decimals.

The part of the program in this question is aimed at allowing them to practice without the need of a teacher giving them exercises and checking their results.

Note: This is the first time I m using unit tests so I'm not experienced at unit-testing at all.

The following are of great interest to me:

1. Unit tests:

• What should I improve? I don't aim for 100% code coverage since that feels more of a fixation on following blindly a "rule" without the actual need for it (but of course I might be wrong).
• Since my methods contain random.random() numbers I was thinking of creating tests that test a method millions or billions of times (e.g. assertIsInstance(_int_term(), int) inside a for _ in range(10**8) loop). This would very strongly indicate (but not with absolute certainty) that the methods work correctly. Should I create such tests?
• Methods with optional parameters, e.g. Terms._int_term(max_val): The parameters are made optional only because I wanted to be able to test the method easily (that is, call it without the need to instantiate Terms() class. If I were not using unit tests, I would simply make it a non static method, and would remove the parameter completely. Is this a bad practice?
2. Docstrings: Are more docstrings needed? Or do good method names suffice? The reason I didn't create dosctings for everything is that they could go stale in case I change code without also updating all the related docstrings.

Of course any other comments unrelated to the above 2 points are also very welcome.

## Directory tree

• project_dir
• main.py
• tests
• test_main
• test_terms.py

## Code

Main module:

"""
Used for the creation of "questions" for the user,
along with the expected answer (that is, the result of the operation)

Some examples of "questions" and their "answers":

"+2-4" ,        "-2"
"(-2)(+7)",     "-14"
"-1.60-2.04",   "-3.64"

The program should be aimed specifically at teaching
the very basics of addition or multiplication of integers or decimals,
in a scaling difficulty.

Exercises that deviate from those specific concepts should be avoided.
Examples of what should NOT be implemented:

"2-4",          # Deviates (slightly) since it also teaches that 2 == +2
"-2(+7)",       # Deviates (same as example above)
"+2-4(-5)",     # Deviates since it combines addition and multiplication

"""

import decimal
from random import randint, choice, random

class Terms(object):

MIN_TERMS_COUNT = 2
MAX_TERMS_COUNT = 3
TERMS_TYPES = {'int', 'float'}
MAX_ABS_VALUE = 10

DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP = {
1: dict(
terms_count=2,
terms_type='int'
),
2: dict(
terms_count=3,
terms_type='int'
),
3: dict(
terms_count=2,
terms_type='float'
)
}

TOTAL_DIFFICULTY_LVLS = len(DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP)

def __init__(self, difficulty_lvl):
self.difficulty_lvl = difficulty_lvl
self.terms_count = self.DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP[self.difficulty_lvl]['terms_count']
self.terms_type = self.DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP[self.difficulty_lvl]['terms_type']

@staticmethod
def _int_term(max_val=MAX_ABS_VALUE):
return randint(0, max_val)

@staticmethod
def _float_term(max_val=MAX_ABS_VALUE):
return random() * max_val

@staticmethod
def final_term(term_without_sign):
"""
Creates a single term.

:param term_without_sign:
:return: (num)
"""
sign = choice(['-', '+'])

if sign == '-':
final_term = -1 * term_without_sign
else:
final_term = term_without_sign

return final_term

def all_terms(self):
lst = []

if self.terms_type == 'int':
func = self._int_term
elif self.terms_type == 'float':
func = self._float_term
else:
raise NotImplemented('{}'.format(self.terms_type))

for _ in range(self.terms_count):
term_without_sign = func()
final_term = self.final_term(term_without_sign=term_without_sign)
lst.append(final_term)

return lst

"""
Based on difficulty and operation type,
creates terms (either float or ints) which are then rounded to allow
specific number of decimals.
"""

def __init__(self, difficulty_lvl, op_type):
self.terms_as_numbers = Terms(difficulty_lvl=difficulty_lvl).all_terms()
self.op_type = op_type

@staticmethod
def round_single_term_2_decimals(given_float):

num = decimal.Decimal(str(given_float))
return num.quantize(decimal.Decimal('.01'), decimal.ROUND_HALF_UP)

def terms_to_rounded_numbers(self):
"""
Ensures all terms have an appropriate number of decimals.

:return: (list)
"""

lst = []

for t in self.terms_as_numbers:

if isinstance(t, int):
lst.append(t)

else:
t = self.round_single_term_2_decimals(given_float=t)
lst.append(t)

return lst

def terms_as_strings(self):
lst = []

for t in self.terms_to_rounded_numbers():

if t > 0:
lst.append('+{}'.format(t))

elif t == 0:
random_sign = choice(['+', '-'])
lst.append('{sign}{term}'.format(sign=random_sign, term=t))

else:
lst.append(str(t))

return lst

def operation_str(self):
"""
Creates the operation string presented to the user.

:return: (str)
"""

terms_as_strings = self.terms_as_strings()

op_str = ''.join(terms_as_strings)

elif self.op_type == 'multiplication':
op_str = ''
for t in terms_as_strings:
op_str += '({})'.format(t)

else:
raise NotImplemented('{}'.format(self.op_type))

return op_str

result = 0
for t in self.terms_to_rounded_numbers():
result += t

elif self.op_type == 'multiplication':

result = 1
for t in self.terms_to_rounded_numbers():
result *= t

else:
raise NotImplemented('{}'.format(self.op_type))

return result

if __name__ == '__main__':

# VISUAL TESTS
if 1:

TOTAL_DIFFICULTY_LVLS = Terms.TOTAL_DIFFICULTY_LVLS

# --------------------------------------------------
# all_terms()
print('\n'+'-'*80)
print('TERMS')

def print_all_terms(difficulty_lvl):
print('\nDifficulty {}'.format(difficulty_lvl))
# (terms' lists printed for each difficulty lvl)
terms_lsts_count = 3
for _ in range(terms_lsts_count):
print(Terms(difficulty_lvl=difficulty_lvl).all_terms())

# (tests all difficulties)
for d in range(1, TOTAL_DIFFICULTY_LVLS + 1):
print_all_terms(difficulty_lvl=d)

# --------------------------------------------------
print('\n'+'-'*80)
print('OPERATION STRING')
for d in range(1, TOTAL_DIFFICULTY_LVLS + 1):
print('\nDifficulty: {}'.format(d))

for _ in range(3):
question = inst.operation_str()
msg = '{q} = {a}'.format(q=question, a=answer)
print(msg)

Test module test_terms.py:

from unittest import TestCase

class TestDifficultyMap(TestCase):

def setUp(self):

import main

self.Term = main.Terms
self.difficulty_dct = self.Term.DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP
self.terms_counts_found = {v['terms_count'] for v in self.difficulty_dct.values()}
self.terms_types_found = {v['terms_type'] for v in self.difficulty_dct.values()}

def test_min_terms_count_DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP(self):

min_terms_count_allowed = self.Term.MIN_TERMS_COUNT
min_terms_count_found = min(self.terms_counts_found)

self.assertGreaterEqual(
min_terms_count_found, min_terms_count_allowed
)

def test_max_terms_count_DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP(self):

max_terms_count_allowed = self.Term.MAX_TERMS_COUNT
max_terms_count_found = max(self.terms_counts_found)

self.assertGreaterEqual(
max_terms_count_found, max_terms_count_allowed
)

def test_terms_types_DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP(self):

self.assertEquals(
self.terms_types_found, self.Term.TERMS_TYPES
)

class TestIntAndFloatTerm(TestCase):

def setUp(self):

import main
self.Term = main.Terms

# _int_term
def test__int_term(self):
self.assertEqual(
self.Term._int_term(max_val=0), 0
)

def test_is_int__int_term(self):
self.assertIsInstance(
self.Term._int_term(max_val=1), int
)

# _float_term
def test__float_term(self):
max_val = 15
term_val = self.Term._float_term(max_val=max_val)
self.assertTrue(0 <= term_val <= max_val)

def test_is_float__float_term(self):
self.assertIsInstance(
self.Term._float_term(max_val=1), float
)

class TestAllTermsMethod(TestCase):

def setUp(self):

import main
self.Term = main.Terms
self.difficulties_available = self.Term.DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP.keys()

def test_len_above_min_all_terms(self):
inst = self.Term(difficulty_lvl=1)

min_terms_count_allowed = self.Term.MIN_TERMS_COUNT
terms_lst = inst.all_terms()

self.assertGreaterEqual(len(terms_lst), min_terms_count_allowed)

def _contains_x_type_all_terms(self, x_type):
found_type = False

for lvl in self.difficulties_available:
inst = self.Term(difficulty_lvl=lvl)

terms = inst.all_terms()

for t in terms:
if type(t) is x_type:
found_type = True

self.assertTrue(found_type, msg='Did not find {}.'.format(x_type))

def test_contains_float_all_terms(self):
self._contains_x_type_all_terms(x_type=float)

def test_contains_int_all_terms(self):
self._contains_x_type_all_terms(x_type=int)

Test module test_questionandanswer.py:

from unittest import TestCase

class TestQuestion(TestCase):

def setUp(self):

from decimal import Decimal

self.positive_float_to_expected_2nd_decimal_rounded = {
0.0049: Decimal('0.00'),
0: Decimal('0'),
0.005: Decimal('0.01'),
2.255: Decimal('2.26'),
9.999: Decimal('10'),
0.004: Decimal('0'),
}

self.negative_float_to_expected_2nd_decimal_rounded = {
-k: -v for k, v in self.positive_float_to_expected_2nd_decimal_rounded.items()}

def test_positive_round_single_term_2_decimals(self):

for given_float, expected in self.positive_float_to_expected_2nd_decimal_rounded.items():

def test_negative_round_single_term_2_decimals(self):

for given_float, expected in self.negative_float_to_expected_2nd_decimal_rounded.items():

Style

Python has a style guide called PEP 8 which is definitly worth reading and and worth following if you do not have good reasons not to. In you case, your usage of empty lines for instance is not compliant to PEP8. You'll find tools online to check your code compliancy to PEP8 in a automated way if you want to.

Code organisation

You've written your code in classes which is sometimes a good thing. Sometimes, you don't need a class.

In any case, most of the things in the Terms class could be extracted out of it (also removing the need for many self.). By the way, it may be interesting to point out that variables defined at the class levels can be pretty complicated and are not entirely needed and could be simple global variables.

Also, you have variables that are not used at all and you should get rid of them.

Once everything than can be moved out of the class (and renamed) is moved out, you get:

"""
Used for the creation of "questions" for the user,
along with the expected answer (that is, the result of the operation)

Some examples of "questions" and their "answers":

"+2-4" ,        "-2"
"(-2)(+7)",     "-14"
"-1.60-2.04",   "-3.64"

The program should be aimed specifically at teaching
the very basics of addition or multiplication of integers or decimals,
in a scaling difficulty.

Exercises that deviate from those specific concepts should be avoided.
Examples of what should NOT be implemented:

"2-4",          # Deviates (slightly) since it also teaches that 2 == +2
"-2(+7)",       # Deviates (same as example above)
"+2-4(-5)",     # Deviates since it combines addition and multiplication

"""

import decimal
from random import randint, choice, random, seed

MAX_ABS_VALUE = 10

def rand_int_term(max_val=MAX_ABS_VALUE):
return randint(0, max_val)

def rand_float_term(max_val=MAX_ABS_VALUE):
return random() * max_val

def create_term(term_without_sign):
"""
Creates a single term.

:param term_without_sign:
:return: (num)
"""
sign = choice(['-', '+'])

if sign == '-':
term = -1 * term_without_sign
else:
term = term_without_sign

return term

DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP = {
1: dict(
terms_count=2,
terms_type='int'
),
2: dict(
terms_count=3,
terms_type='int'
),
3: dict(
terms_count=2,
terms_type='float'
)
}

TOTAL_DIFFICULTY_LVLS = len(DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP)

class Terms(object):

def __init__(self, difficulty_lvl):
terms_data = DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP[difficulty_lvl]
self.terms_count = terms_data['terms_count']
self.terms_type = terms_data['terms_type']

def all_terms(self):
lst = []

if self.terms_type == 'int':
func = rand_int_term
elif self.terms_type == 'float':
func = rand_float_term
else:
raise NotImplemented('{}'.format(self.terms_type))

for _ in range(self.terms_count):
term_without_sign = func()
term = create_term(term_without_sign=term_without_sign)
lst.append(term)

return lst

"""
Based on difficulty and operation type,
creates terms (either float or ints) which are then rounded to allow
specific number of decimals.
"""

def __init__(self, difficulty_lvl, op_type):
self.terms_as_numbers = Terms(difficulty_lvl=difficulty_lvl).all_terms()
self.op_type = op_type

@staticmethod
def round_single_term_2_decimals(given_float):

num = decimal.Decimal(str(given_float))
return num.quantize(decimal.Decimal('.01'), decimal.ROUND_HALF_UP)

def terms_to_rounded_numbers(self):
"""
Ensures all terms have an appropriate number of decimals.

:return: (list)
"""

lst = []

for t in self.terms_as_numbers:

if isinstance(t, int):
lst.append(t)

else:
t = self.round_single_term_2_decimals(given_float=t)
lst.append(t)

return lst

def terms_as_strings(self):
lst = []

for t in self.terms_to_rounded_numbers():

if t > 0:
lst.append('+{}'.format(t))

elif t == 0:
random_sign = choice(['+', '-'])
lst.append('{sign}{term}'.format(sign=random_sign, term=t))

else:
lst.append(str(t))

return lst

def operation_str(self):
"""
Creates the operation string presented to the user.

:return: (str)
"""

terms_as_strings = self.terms_as_strings()

op_str = ''.join(terms_as_strings)

elif self.op_type == 'multiplication':
op_str = ''
for t in terms_as_strings:
op_str += '({})'.format(t)

else:
raise NotImplemented('{}'.format(self.op_type))

return op_str

result = 0
for t in self.terms_to_rounded_numbers():
result += t

elif self.op_type == 'multiplication':

result = 1
for t in self.terms_to_rounded_numbers():
result *= t

else:
raise NotImplemented('{}'.format(self.op_type))

return result

if __name__ == '__main__':

# VISUAL TESTS
if 1:

seed(42)  # Tmporal addition from Josay to have same results on different runs

# --------------------------------------------------
# all_terms()
print('\n'+'-'*80)
print('TERMS')

def print_all_terms(difficulty_lvl):
print('\nDifficulty {}'.format(difficulty_lvl))
# (terms' lists printed for each difficulty lvl)
terms_lsts_count = 3
for _ in range(terms_lsts_count):
print(Terms(difficulty_lvl=difficulty_lvl).all_terms())

# (tests all difficulties)
for d in range(1, TOTAL_DIFFICULTY_LVLS + 1):
print_all_terms(difficulty_lvl=d)

# --------------------------------------------------
print('\n'+'-'*80)
print('OPERATION STRING')
for d in range(1, TOTAL_DIFFICULTY_LVLS + 1):
print('\nDifficulty: {}'.format(d))

for _ in range(3):
question = inst.operation_str()
msg = '{q} = {a}'.format(q=question, a=answer)
print(msg)

(I just realised that I forgot to extract stuff from QuestionAndAnswer but you get the spirit.)

Avoid useless string manipulation

You have a dictionnary where values are strings and these strings are later one used to retrieve the relevant function. It may be easier to just map keys to functions.

You simply get :

DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP = {
1: dict(
terms_count=2,
terms_type=rand_int_term
),
2: dict(
terms_count=3,
terms_type=rand_int_term
),
3: dict(
terms_count=2,
terms_type=rand_float_term
)
}

...

def all_terms(self):
lst = []
for _ in range(self.terms_count):
term_without_sign = self.terms_type()
term = create_term(term_without_sign=term_without_sign)
lst.append(term)

(term_type probably needs to be renamed, I'll leave this to you)

List comprehension

You can use list comprehension to rewrite all_terms in a more concise/pythonic way :

def all_terms(self):
return [ create_term(term_without_sign=self.terms_type())
for _ in range(self.terms_count)]

Remove duplicated code

In terms_to_rounded_numbers, you have :

        if isinstance(t, int):
lst.append(t)
else:
t = round_single_term_2_decimals(given_float=t)
lst.append(t)

which could simply be written:

        if not isinstance(t, int):
t = round_single_term_2_decimals(given_float=t)
lst.append(t)

But here again, list comprehension can be used:

Using the right data type

At the moment, difficulties are stored in a dictionnary mapping consecutive integers to values. This looks a lot like a list (except that the indexing starts from 1 instead of 0).

Variable names

given_float is a weird parameter name for a function. Maybe float_arg would make more sense.

Avoid string concatenation

From PEP 8:

For example, do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a += b or a = a + b . This optimization is fragile even in CPython (it only works for some types) and isn't present at all in implementations that don't use refcounting. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.

Thus, you could write:

    elif self.op_type == 'multiplication':
op_str = ''.join('({})'.format(t) for t in terms_as_strings)

Avoid useless string manipulation (again)

In create_term, you call sign = random.choice(['-', '+']) to get the character corresponding to a sign. It may be easier to do:

return term_without_sign * random.choice([-1, 1])

This could also be applied to terms_as_strings but I do not quite understand what you were trying to do.

List comprehension (again)

It would probably be worth extracting the conversion from terms_as_strings in a function on its own and then use it in a list comprehension.

def term_as_string(t):
if t > 0:
return '+{}'.format(t)
elif t == 0:
random_sign = random.choice(['+', '-'])
return '{sign}{term}'.format(sign=random_sign, term=t)
else:
return str(t)

....

def terms_as_strings(self):
return [term_as_string(t) for t in self.terms_to_rounded_numbers()]

Avoid string manipulation (again)

At the moment, you have a list of string representing operations types and in a few places, you look if the string you are handling corresponds to any of the string you know and perform the relevant computations. This has multiple problems: you have a lot of repeated code and it is easy to forgot a place if you want to add an operation. It would make sense to use a data structure with all the relevant pieces of information. A tuple and more particularly, a namedtuple seems relevant for this task.

import operator
from collections import namedtuple
Operation = namedtuple('Operation', 'name symbol func neutral format')  # name and symbol do not seems to be useful at the moment

OPERATIONS_TYPES = {
Operation('multiplication', '*', operator.mul, 1, '{}'),
}

...

def operation_str(self):
"""
Creates the operation string presented to the user.

:return: (str)
"""
terms_as_strings = self.terms_as_strings()
return ''.join(self.op_type.format.format(t) for t in terms_as_strings)

op = self.op_type
result = op.neutral
for t in self.terms_to_rounded_numbers():
result = op.func(result, t)
return result

Using the right data type (again with actual solution)

As said before, the fact that DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP is a bit puzzling as you are accessing it using range and getting item at the given index. A list is probably the right thing to use here. Also, this is not really pythonic nor efficient. I'd recommand reading/watching Ned Batchelder's presentation : "Loop Like A Native".

In your case, instead of getting the element at difficulty_lvl in Terms, it may be easier to provide it directly to the constructor. Doing the same thing also in QuestionAndAnswser, you can then simply look over the list. Then, if you do need the index, you can use enumerate.

All this requires many changes everywhere but once done, you can get rid of the TOTAL_DIFFICULTY_LVLS variable.

Remaining code looks like :

"""
Used for the creation of "questions" for the user,
along with the expected answer (that is, the result of the operation)

Some examples of "questions" and their "answers":

"+2-4" ,        "-2"
"(-2)(+7)",     "-14"
"-1.60-2.04",   "-3.64"

The program should be aimed specifically at teaching
the very basics of addition or multiplication of integers or decimals,
in a scaling difficulty.

Exercises that deviate from those specific concepts should be avoided.
Examples of what should NOT be implemented:

"2-4",          # Deviates (slightly) since it also teaches that 2 == +2
"-2(+7)",       # Deviates (same as example above)
"+2-4(-5)",     # Deviates since it combines addition and multiplication

"""

import decimal
import random
import operator
from collections import namedtuple

MAX_ABS_VALUE = 10

def rand_int_term(max_val=MAX_ABS_VALUE):
return random.randint(0, max_val)

def rand_float_term(max_val=MAX_ABS_VALUE):
return random.random() * max_val

def create_term(term_without_sign):
"""
Creates a single term.

:param term_without_sign:
:return: (num)
"""
return term_without_sign * random.choice([-1, 1])

DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP = [
dict(
terms_count=2,
terms_type=rand_int_term
),
dict(
terms_count=3,
terms_type=rand_int_term
),
dict(
terms_count=2,
terms_type=rand_float_term
)
]

class Terms(object):

def __init__(self, difficulty):
self.terms_count = difficulty['terms_count']
self.terms_type =  difficulty['terms_type']

def all_terms(self):
return [ create_term(term_without_sign=self.terms_type())
for _ in range(self.terms_count)]

Operation = namedtuple('Operation', 'name symbol func neutral format')

OPERATIONS_TYPES = {
Operation('multiplication', '*', operator.mul, 1, '{}'),
}

def round_single_term_2_decimals(float_arg):
num = decimal.Decimal(str(float_arg))
return num.quantize(decimal.Decimal('.01'), decimal.ROUND_HALF_UP)

def term_as_string(t):
if t > 0:
return '+{}'.format(t)
elif t == 0:
random_sign = random.choice(['+', '-'])
return '{sign}{term}'.format(sign=random_sign, term=t)
else:
return str(t)

"""
Based on difficulty and operation type,
creates terms (either float or ints) which are then rounded to allow
specific number of decimals.
"""

def __init__(self, difficulty, op_type):
self.terms_as_numbers = Terms(difficulty=difficulty).all_terms()
self.op_type = op_type

def terms_to_rounded_numbers(self):
"""
Ensures all terms have an appropriate number of decimals.

:return: (list)
"""
return [t if isinstance(t, int) else round_single_term_2_decimals(float_arg=t)
for t in self.terms_as_numbers]

def terms_as_strings(self):
return [term_as_string(t) for t in self.terms_to_rounded_numbers()]

def operation_str(self):
"""
Creates the operation string presented to the user.

:return: (str)
"""
terms_as_strings = self.terms_as_strings()
return ''.join(self.op_type.format.format(t) for t in terms_as_strings)

op = self.op_type
result = op.neutral
for t in self.terms_to_rounded_numbers():
result = op.func(result, t)
return result

if __name__ == '__main__':

random.seed(42)  # Temporal addition from Josay to have same results on different runs
newline = '\n'+'-'*80

# --------------------------------------------------
# all_terms()
print(newline)
print('TERMS')

# (tests all difficulties)
for i, difficulty in enumerate(DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP, start=1):
print('\nDifficulty {}'.format(i))
for _ in range(3):
print(Terms(difficulty=difficulty).all_terms())

# --------------------------------------------------
print(newline)
print('OPERATION STRING')
for i, difficulty in enumerate(DIFFICULTY_TO_TERMS_COUNT_AND_OP_TYPE_MAP, start=1):
print('\nDifficulty: {}'.format(i))
for operation in OPERATIONS_TYPES:
for _ in range(3):

• I'm using PyCharm and thankfully it guides me in the PEP8 direction most of the time; i do agree that some of my empty lines are redundant though. The namedtuple() suggestion is amazing since it forces specific keys and allows easy "lookup", and i think can be used for the DIFFICULTY_MAP elements as well. Unused vars and duplicate code was an issue as you pointed out. I do have some objections on string join() though, comprehensions instead of for loops, and converting DIFFICULTY_MAP to a list. It feels like premature optimization in some cases and [..TO BE CONTINUED] – user Jul 22 '16 at 17:22
• ... going to somewhat less readable code. E.g. my top priority is having readable code which string concatenation accomplishes better than join(). Although I do agree that in general the latter will be faster, but specifically for my use case I doubt any of the Term-creation functionality would be a bottleneck (additionally user will be spending a lot of time between requesting new terms). – user Jul 22 '16 at 17:28
• I m uncomfortable with DIFFICULTY_MAP suggestion since it contains the implicit assumption that difficulties are ordered, e.g. DIFFICULTY_MAP[0] corresponds to difficulty_lvl==1. – user Jul 22 '16 at 17:37


text:
[Reader’s Note. Some of our articles are applied and some of our articles are more theoretical. The following article is more theoretical, and requires fairly formal notation to even work through. However, it should be of interest as it touches on some of the fine points of cross-validation that are quite hard to perceive or discuss without the notational framework. We thought about including some “simplifying explanatory diagrams” but so many entities are being introduced and manipulated by the processes we are describing we found equation notation to be in fact cleaner than the diagrams we attempted and rejected.]

• Picking hyper-parameters, fitting a model, and then evaluating the model.
• Variable preparation/pruning, fitting a model, and then evaluating the model.

In each case you are building a pipeline where “y-aware” (or outcome aware) choices and transformations made at each stage affect later stages. This can introduce undesirable nested model bias and over-fitting.

Our current standard advice to avoid nested model bias is either:

• Split your data into 3 or more disjoint pieces, such as separate variable preparation/pruning, model fitting, and model evaluation.
• Reserve a test-set for evaluation and use “simulated out of sample data” or “cross-frame”/“cross simulation” techniques to simulate dividing data among the first two model construction stages.

The first practice is simple and computationally efficient, but statistically inefficient. This may not matter if you have a lot of data, as in “big data”. The second procedure is more statistically efficient, but is also more complicated and has some computational cost. For convenience the cross simulation method is supplied as a ready to go procedure in our R data cleaning and preparation package vtreat.

What would it look like if we insisted on using cross simulation or simulated out of sample techniques for all three (or more) stages?

Hyperbole and a Half copyright Allie Brosh
(use allowed in some situations with attribution)

We mentioned two possible nested tasks to emphasize that nested model bias is not merely an issue of our own invention (despite our writings on variable selection and variable preparation). The issue also occurs with hyper-parameter tuning, model selection, and dimension reduction.

As we have said: if you have enough data you can split your data into a disjoint set for each stage (often called train/test, or calibration/train/test) and wish most of the problem away. However, if you are not feeling “data rich” (and this rapidly happens with complex models, rare features, and un-balanced target classes) or your training data is expensive to produce (very true for many high-value data science projects) then you may want to be more statistically efficient. However, there is a reason to always reserve a portion of data for the last-stage test (as we usually advise): it ensures you are testing properties of the actual model you are proposing to put into production (whereas cross-procedures mostly test the expected quality of your procedures, not the realized quality of your single model).

It is still an interesting problem: how do you properly organize nested cross simulation procedures so no additional data splitting is required? We are going to describe one such method here which is a generalization of k-way cross validation. We call the whole family of methods “nested cross simulation” (to emphasize both the multi-stage nature, and also that scoring or validation is not the only task we are removing bias from).

## Notation/Definitions

“It’s all a question of notation” (“A Bridge too Far”, 1977, Copyright United Artists).

Suppose we are drawing supervised training examples from an arbitrary data schema (a schema that includes possibly numeric, categorical and logical columns or variables) called $$\mathbb{S}$$. We have an indexed list of training examples $$T = ((s_i,y_i) \;|\; i = 1, \cdots m)$$ where $$i$$ is the example name, $$s_i \in \mathbb{S}$$ is a vector of input or independent variables, and $$y_i$$ is the outcome (numeric, but can be zero-one representing a categorization target).

We define some functions:

• $$buildF()$$: takes a sequence of training examples $$(s_i,y_i)$$ (as described above) and returns a map $$f: \mathbb{S} \rightarrow \mathbb{R}^n$$. $$f$$ is a “data treatment” or preparation map (mapping examples to vectors in $$\mathbb{R}^n$$) and $$buildF$$ is the data treatment designer. Think of $$buildF()$$ designing things like one-hot encoders, or (more to our point) building various outcome sensitive or $$y$$-aware transforms (such as found in vtreat).
• $$buildG()$$: takes a sequence of tuples $$(x_i,y_i)$$ where $$i$$ is the example name, $$x_i \in \mathbb{R}^n$$, and $$y_i$$ is an outcome. Think of these as encoded or treated training examples. $$buildG()$$ returns a map $$g:\mathbb{R}^n \rightarrow \mathbb{R}$$ mapping inputs to estimated outputs. $$buildG()$$ is a model training procedure (such as linear regression, gradient boosted trees, and so on) and $$g()$$ is the returned model.
• loss(): takes two numeric vectors $$\widehat{y}$$ and $$y$$ (built up from the $$y_i$$) and returns a loss calculation or model quality score. Examples loss functions include sum of mean square error ($$loss(y,\widehat{y}) = \frac{1}{m} \sum_{i=1}^{m} (\widehat{y}_i - y_i)^2$$) for regression or per-example normalized deviance ($$loss(y,\widehat{y}) = -2 \frac{1}{m} \sum_{i=1}^{m} (y_i \log(\widehat{y}_i) + (1-y_i) \log(1-\widehat{y}_i)$$) for classification (the deviance is proportional to a cross-entropy).

### The naive method

The naive (not recommended) modeling method uses the same data over and over for data treatment design, model training, and scoring. In our notation this looks like:

• $$T = ((s_i,y_i) \;|\; i = 1, \cdots m)$$ (training data)
• $$f = buildF(T)$$ (design the variable treatments)
• $$g = buildG((f(s_i),y_i) \;|\; i = 1, \cdots m))$$ (build the model on treated data)
• $$\widehat{y}_j = g(f(s_j)) ,\; j = 1, \cdots m$$ (build the model predictions)
• Compute $$loss(y,\widehat{y})$$ (evaluate performance on training data).

In the above method we expect both over-fit and an upwardly biased assessment of quality. This is because the same data rows are used in many stages of the training and scoring, which is something that will not be true for future test or application data. This is a standard criticism, so we won’t go into it here.

To avoid the over-fit and assessment bias we try more sophisticated data handling as we will illustrate below.

## The cross-frame or cross simulation method

The vtreat documentation recommends using a separate held-out set for testing. It then recommends either using separate portions of the training set for variable treatment design and model training or using cross-frame methods to try to break some of the data-reuse driven information leakage. This scheme when used in “leave-one-out” mode looks like the following. (For convenience in this writeup we add the additional assumption that the $$m$$ items in $$T$$ are in random order, so a segment of them is a sample picked uniformly at random.)

• $$Train = ((s_i,y_i) \;|\; i = 1, \cdots k)$$ (training data)
• $$Test = ((s_i,y_i) \;|\; i = k+1, \cdots m)$$ (test data)
• $$f_i = buildF( (s_j,y_j) \;|\; j = 1, \cdots k ,\; j \neq i )), \; i = 1, \cdots k$$ (build the cross-frame or data that is treated using treatments designed and data disjoint from the data being treated)
• $$g = buildG((f_i(s_i),y_i) \;|\; i = 1, \cdots k))$$ (build the model using the cross-frame or cross simulated treated data)
• $$f = buildF( (s_j,y_j) \;|\; j = 1, \cdots k))$$ (design a final data treatment using all the data)
• $$\widehat{y}_j = g(f(s_j)) ,\; j = k+1, \cdots m$$ (evaluate the model on test data, treated using the final data treatment)
• Compute $$loss(y_{j=k+1, \cdots m},\widehat{y}_{j=k+1, \cdots m})$$ (score the model only on test data).

The important points are:

• $$f_i$$ the treatment plan applied to point $$s_i$$ is built without ever looking at $$(i,s_i,y_i)$$, so $$(f_i(s_i),y_i)$$ should be distributed as it would be for data not seen during $$f_i$$ construction. Thus $$buildG()$$ is built training data that statistically looks disjoint from the data determining the $$f()$$. This addresses the issue of nested over-fitting.
• Disjoint, uniformly selected at random, held out test data is used for scoring. this addressed the issue of model evaluation bias.

This is the system recommended in the vtreat documentation and examples. We are trying to prevent the components of over-fit driven by the data treatment by introducing the $$f_i()$$. $$g$$ is fit in a standard (not cross-simulated) manner and we depend on the model fitting procedures themselves to avoid over-fit. The usefulness of this procedure depends on the estimation procedures being somewhat stable and easy to stitch together (an issue for procedures with symmetries such as principal components analysis).

We use the held-out test set to try and detect over-fit issues.

I think this formulation is hits a real sweet-spot in sensibleness and data re-use. The fact that the actual model to be used is evaluated is a real plus.

## The nested cross simulation method

We can go further. Set up the nested cross simulation method as follows.

• $$T = ((s_i,y_i) \;|\; i = 1, \cdots m)$$ (training data)
• $$f_c = buildF((s_j,y_j) \;|\; j = 1, \cdots m ,\; j \not\in c )) ,\; c \subseteq \{1, \cdots m \} \;\wedge\; |c| \in \{1,2\}$$ (build many cross-frames or cross simulated data maps for use in different contexts)
• $$g_j = buildG((f_{\{j,i\}}(s_i),y_i) \;|\; i = 1, \cdots m ,\; i \neq j)) ,\; j = 1, \cdots m$$ (build many models to cross validate)
• $$\widehat{y}_j = g_j(f_{\{j\}}(s_j)) ,\; j = 1, \cdots m$$ (evaluate the models only on points and treatments disjoint form the point we are evaluating)
• Compute $$loss(y,\widehat{y})$$ (score the model on all data).

Notice we are building a lot of different data treatments $$f_*()$$ (one for every distinct $$i,j$$ and one for each $$j$$) and models (one for each $$j$$). This can be mitigated by treating each datum as a block of observations (chosen randomly) and noticing this converts “leave-one-out” cross validation to “$$m$$-fold cross validation” (where $$m$$ is now how many blocks we have).

The important points are:

• $$g_j$$ is built without ever looking at $$(j,s_j,y_j)$$, and using only $$f_{\{j,i\}}(s_i)$$ where $$f_{\{j,i\}}()$$ has looked at neither $$(j,s_j,y_j)$$ nor $$(i,s_i,y_i)$$. Thus from $$f_{\{j,i\}}()$$’s point of view both of these points are statistically exchangable with future data. So $$f_{\{j,i\}}()$$ is not “over fit” for either of these points, as it never saw them. $$f_{\{j,i\}}(s_i)$$ behaves as $$f_{\{j,i\}}()$$ would on a novel point, meaning $$buildG()$$ sees training data that looks disjoint from the data determining the $$f()$$ (what $$buildF()$$ sees) and the $$f_{c}()$$ should behave during training as they will on future test or application data. This addresses the issue of nested over-fitting.
• In the assignment “$$\widehat{y}_j = g_j(f_{\{j\}}(s_j))$$” by design both $$g_j()$$ and $$f_{\{j\}}()$$ are built without having seen the datum $$(j,s_j,y_j)$$. So this datum remains statistically exchangable with future test or application data (addressing the issue of model evaluation bias).

There is also the issue of what treatment plan and function to put into production. This is essentially re-running the process without the loss scoring stage (removing one level of nesting), so we can take the results $$f$$ and $$g$$ from the previous cross simulation method as our data treatment and model to put into production. The extra work in this section is all just trying to get an unbiased estimate of the quality of the modeling process without splitting the data.

Despite the heavy notation the above is all a bit informal (all the “never sees … therefore …” bits; generalizing cross validation is fun- but the notation is laborious). A fine point is exchangeability and information hiding only holds for each row individually: a process that looks at many rows can in fact over-fit. That is: a row that is processed “without seeing such and such” must behave as if it has no information about what it did not see when taken along; however when combined with a seemingly harmless other piece of information (such as a grand mean) it may be the the become informative (the usual issue: u and v each being singly independent of y does not imply y is independent of the joint fact (u, v)). This is why stacking/super-learner style proofs don’t work on independence of information but instead use typical PAC-style arguments.

However, my claim is: the nested cross simulation method is sound in practice and we could expand the above into a formal argument. The method can be generalized to more stages- but obviously we start running over larger and larger sets of points to be simultaneously excluded in the earlier stages (so the method will get expensive). We also must take care to note for all its complexity the nested cross simulation method is measuring the quality of the modeling procedure, not measuring the quality of the actual model returned.

# Conclusion

Our plan throughout has been to prevent over-fit with respect to a single data point by hiding that data point from the training and fitting procedures. The hope is such care (realized by the complicated bookkeeping and subscripting above) will preserve, in part, statistical exchangeability between training data and future test or application data (if it was there in the first place). As such we can mitigate over-fit and upward evaluation bias.

Obviously this is all quite a lot of trouble to directly work with, which is why recommend using the simple (not nested) cross simulation procedure and this process is wrapped and automated in vtreat.

I feel it is well worth knowing how to work the theory to collect evidence we are settled on a good recommendation. In this document we are mostly just laying down notation to discuss theory later. Our group, Win-Vector LLC, has found for our consulting clients: certain problems and domains (for example time series) benefit greatly from properly designed domain specific cross simulation procedures (please see arXiv:1611.09477 stat.AP Section 4 for such an example).

format: plain


text:
# Conditional Independence - Bayesian Network

May the probability distribution $P(A,B,C,D)$ given as:

$P(A,B,C,D) = P(A)P(B)P(C|A,B)P(D|C)$

The task is to show that this holds $A \bot B | \emptyset$ and $A\bot D|C$.

First thing I'd like to know is, if this - drawn as a Bayesian Network - looks like this:

and the second thing - of course - is how I can show those conditions.

Assuming that the network looks like the graphic shows I can see, that $A \bot B | \emptyset$ and $A\bot D|C$ should apply to this distribution.

Do I have to show that $P(A,B,C,D) = P(A)P(B)$ and $P(A,B,C,D) = P(A)P(C|A)P(D|C)$? And if so: How can I show this?

I can not assume that $P(C|A,B) = \frac{P(A,B,C)}{P(A,B)} = P(C)$ and $P(D|C) = P(D)$ such that $P(A,B,C,D) = P(A,B,C,D) \Leftrightarrow P(A,B) = P(A,B)$ because this would mean, that all events are independet, right?

How can I show that?

$P(A,B) = \int\int P(A,B,C,D)dDdC = \int\int P(A)P(B)P(C|A,B)P(D|C)dDdC = \int P(A)P(B)P(C|A,B)\int P(D|C)dDdC = \int P(A)P(B)P(C|A,B)1dC = P(A)P(B)\int P(C|A,B)dC = P(A)P(B)1 = P(A)P(B)$ from which the definition of independence is evidently true.
$P(A,D|C) = \int P(A,D,B|C)dB = \int P(A)P(B)P(C|A,B)P(D|C)/P(C) dB = \int P(A,B,C)P(D|C)dB/P(C) = \int P(A,C)P(B|A,C)P(D|C)dB/P(C) = P(A,C)P(D|C)\int P(B|A,C)dB / P(C) = P(A,C)P(D|C)/P(C) = P(A|C)P(D|C)$ from which the definition of conditional independence is evident.
The hypothesis is that $P(A,B,C,D) = P(A)P(B)P(C|A,B)P(D|C)$ $(\ast)$, which implies $P(A,B,C,D) = P(A,B,C)P(D|C)$ $(\ast\ast)$.
• Summing $(\ast)$ over every $(C,D)$ yields $P(A,B)=P(A)P(B)$. This proves that $A$ and $B$ are independent.
• Summing $(\ast\ast)$ over every $B$ yields $P(A,C,D)=P(A,C)P(D|C)$. Dividing both sides by $P(C)$ yields $P(A,D|C)=P(A|C)P(D|C)$. This proves that $A$ and $D$ are independent conditionally on $C$.
• This makes sense, but could you explain to me when I can assume that $P(C|A,B) = P(C)$? If I am allowed to do so, I'd end up with $P(A,B,C,D) = P(A)P(B)P(C)P(D)$. I would like to know when I can assume e.g. $P(C|A,B) = P(C)$ – displayname Nov 11 '13 at 14:59
• And we "see" that $P(C)$ is dependent because of what is given, right? So the graphic of the network is also correct? What kind of notation allows one to show that $P(C|A,B) = P(C)$ and P(C|A,B) \new P(C) \$? That means, that I always have to remember which term describes which part of the network such that I don't eliminate factors be accident, doesn't it? – displayname Nov 11 '13 at 15:11


text:
# Finding the nth term of a quadratic sequence

Look again at the sequence of square numbers:

The diagram shows that:

• the first term is ( )
• the second term is ( )
• the third term is ( )
• the fourth term is ( )

So the term is .

Whenever a sequence has a second difference of , it will be connected to the sequence of square numbers and the term will have something to do with .

Question

What is the term of the sequence , , , , ... ?

The second difference is , so the term has something to do with .

The sequence of square numbers is: , , , , ...

Our sequence is: , , , , ...

Can you see what the difference is?

Each term is higher than the corresponding term in the sequence of square numbers, so the rule for the term is .

Question

What is the term of the sequence , , , , ...?

The second differences are , so the formula has something to do with .

The sequence of square numbers is: , , , , ...

Our sequence is: , , , , ...

Each term in this sequence is less than the corresponding term in the sequence of square numbers, so the rule for the term is .


text:
# algebro-geometric properties of morphisms between algebraic groups

Do morphisms of algebraic groups have any special properties? I am mainly interested in morphisms between algebraic groups preserving the group structure; but I am also interested in arbitrary morphisms between algebraic groups. For example,

What can be said about the morphism $x^n: G \rightarrow G$, $x$ goes into $x^n$: is it necessary proper? finite? when is it étale? what if $G$ is commutative but not necessarily an abelian variety?

In fact, I am rather looking for a reference which describes such properties in full generality: that is, between arbitrary (finite dimensional), possibly commutative, algebraic groups in arbitrary characteristic.

• It is certainly not true that this map is proper for $\textbf{GL}_r$. The fiber over the identity is the same as the space of direct sum decompositions of an $r$-dimensional vector space indexed by the $\text{n}^{\text{th}}$ roots of unity. – Jason Starr Jul 7 '11 at 15:47
• I think it's true that any identity-preserving morphism $G \to {\mathbb G}_m$, for $G$ reductive, is a homomorphism. Certainly this is easy to prove for ${\mathbb G}_m$ itself. – Allen Knutson Jul 7 '11 at 19:54

These kinds of questions seem to be treated only in scattered papers over many years. Concerning power maps, see two related papers:

Chatterjee, Pralay, On the surjectivity of the power maps of semisimple algebraic groups. Math. Res. Lett. 10 (2003), no. 5-6, 625–633.

Steinberg, Robert, On power maps in algebraic groups. Math. Res. Lett. 10 (2003), no. 5-6, 621–624.

Both papers investigate when the map is surjective, as do two more recent papers by Chatterjee focusing on local fields. Steinberg's paper works in arbitrary characteristic. In both cases algebraic groups need to be connected.

I suspect there is no comprehensive paper of the kind wanted. The interaction between morphisms and algebraic group structure has been studied over many decades, but not definitively. As Allen remarks, an old theorem of Rosenlicht shows for example that for connected groups an identity-preserving morphism to the multiplicative group is a character. There are several simple modern proofs, one being readily accessible online:

Broughton, S. A., A note on characters of algebraic groups. Proc. Amer. Math. Soc. 89 (1983), no. 1, 39–40.

ADDED: In a somewhat complementary framework, there is also a lot of literature concerning group homomorphisms between linear algebraic groups which are not assumed to be morphisms; the most comprehensive and influential paper is the paper by Borel and Tits:

Borel, Armand; Tits, Jacques, Homomorphismes “abstraits” de groupes algebriques simples. Ann. of Math. (2) 97 (1973), 499–571.


text:
www lon-capa-cvs@mail.lon-capa.org
Wed, 14 Apr 2004 18:31:51 -0000

www		Wed Apr 14 14:31:51 2004 EDT

Modified files:
Course_Parameter_Levels.tex
Docs_Supplemental.tex
Log:
Typos.

--- loncom/html/adm/help/tex/Authentication.tex:1.1	Wed Aug 20 12:17:40 2003
+++ loncom/html/adm/help/tex/Authentication.tex	Wed Apr 14 14:31:50 2004
@@ -3,7 +3,7 @@
LON-CAPA ships with support for LON-CAPA specific passwords, authentication
using the UNIX authentication scheme on the server (assuming that
-user has a user account on that system), and Kerberous 4 and 5. It
+user has a user account on that system), and Kerberos 4 and 5. It
is easy to add other external authentication types to integrate with
whatever your campus may use, and there are institutions doing this.

@@ -7,7 +7,7 @@
\item At the \textbf{User Role} screen, select the role of Course Coordinator for the course.
\item Click \textbf{PARM} on the remote control.
\item At the \textbf{Set Course Parameters} screen, click \textbf{Set Course Environment}.
-\item Scroll down to each Feedback type and enter a comma seperated list of
+\item Scroll down to each Feedback type and enter a comma separated list of
"username:domain", for example, "fred:msu,susie:ohiou". This will specify who
gets which feedback messages.
\item Check the \textbf{set} field if not checked.
--- loncom/html/adm/help/tex/Course_Parameter_Levels.tex:1.1	Mon Jul 14 16:36:23 2003
+++ loncom/html/adm/help/tex/Course_Parameter_Levels.tex	Wed Apr 14 14:31:50 2004
@@ -16,7 +16,7 @@
\textbf{Map Level}: If you select \textbf{Map level} from the
Parameter pull down menu a table or tables will append to the page
showing the set defaults for all the resources in a map or folder in
-the course. The map or folder displayd in the tables depends on which
+the course. The map or folder display in the tables depends on which
map or folder you select from the enclosing map or folder pull down
menu. The table or tables have three columns: \textbf{Parameter Name},
\textbf{Default Value}, and \textbf{Parameter in Effect}. The
--- loncom/html/adm/help/tex/Docs_Supplemental.tex:1.4	Tue Sep  2 14:28:36 2003
+++ loncom/html/adm/help/tex/Docs_Supplemental.tex	Wed Apr 14 14:31:50 2004
@@ -1,8 +1,8 @@
Supplemental Course Documents are auxiliary files the course
necessarily part of the course, such as reference material, handouts,
-ect. This is also useful for files that may not be directly viewable
-or usable in a browser, such as PowerPoint pesentations and Word
+etc. This is also useful for files that may not be directly viewable
+or usable in a browser, such as PowerPoint presentations and Word
documents. Supplemental documents differ in how the material is
presented to the student. The student will not see the supplemental
documents unless they click DOCS on the remote control. Manipulating


text:
The following example requires MOSEK or GPPOSY, or any nonlinear solver such as FMINCON, SNOPT or IPOPT. The solvers GPPOSY is a dedicated geometric programming solvers but slightly outdated. With MOSEK, YALMIP automatically rewrites the problem to an [exponential cone program]((tutorial/exponentialcone). With a general nonlinear solver, it is possible tell YLMIP to rewrite the geometri program to its convex form.

## Posynomial forms

A general signomial problem has the following form.

Geometric programming solvers are capable of solving a sub-class where $$c\geq 0$$ and $$t\geq 0$$, so called posynomial geometric programming. The following example is taken from the MOSEK manual. Note that there has to be explicit positivity constraint on all involved variables in the model.

Assuming MOSEK or GPPOSY is available, we can solve the following model.

sdpvar t1 t2 t3

obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
C = [(1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 <= 1, [t1 t2 t3]>=0];
optimize(C,obj);

If the geometric program violates the posynomial assumption, an error will be issued.

optimize(C + [t1-t2 <= 1],obj)
Warning: Solver not applicable
ans =
yalmiptime: 0.0600
solvertime: 0
info: 'Solver not applicable'
problem: -4

YALMIP will automatically convert some simple violations of the posynomial assumptions, such as lower bounds on monomial terms and maximization of negative monomials. The following small program maximizes the volume of a box, under constraints on the floor and wall area, and constraints on the relation between the height, width and depth (example from [Boyd et al. 2007]).

sdpvar h w d

Awall  = 1;
Afloor = 1;

C = [0.5 <= h/w <= 2,  0.5 <= d/w <= 2, h>=0, w>=0];
C = [C, 2*(h*w+h*d) <= Awall, w*d <= Afloor];

optimize(C,-(h*w*d))

### Generalized geometric programming

Some geometric programs, although not given in standard form, can still be solved using a standard geometric programming solver after some some additional variables and constraints have been introduced. YALMIP has built-in support for some of these conversion.

To begin with, nonlinear operators can be used also in geometric programs, as in any other optimization problems (as long as YALMIP can prove convexity and find a suitable graph representation)

sdpvar t1 t2 t3

obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);

C = [max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) <= min(t1,t2), t1>=0, t2>=0, t3>=0];
optimize(C,obj);

Powers of posynomials are allowed in generalized geometric programs. YALMIP will automatically take care of this and convert the problems to a standard geometric programs. Note that the power has to be positive if used on the left-hand side of a <=, and negative otherwise.

sdpvar t1 t2 t3

obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);

C = [max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) <= min((t1+0.5*t2)^-1,t2)];
C = [C, (2*t1+3*t2^-1)^0.5 <= 2, t1>=0, t2>=0, t3>=0];

optimize(C,obj);

To understand how a generalized geometric program can be converted to a standard geometric program, the reader is referred to [Boyd et al 2007].

### Using standard nonlinear solvers

The posynomial geometric programming problem is not convex in its standard formulation. The presence of multiple singularities due to the negative powers does not make matters ny easier. Hence, if a general nonlinear solver is applied to the problem, it will typically fail. However, by performing a suitable logarithmic variable transformation, the problem is rendered convex. YALMIP has built-in support for performing this variable change, and solve the problem using a nonlinear solver such as FMINCON. To invoke this module in YALMIP, use the solver tag fmincon-geometric’.

sdpvar t1 t2 t3
obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
C = [(1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 <= 1, t1>=0, t2>=0, t3>=0];
optimize(C,obj,sdpsettings('solver','fmincon-geometric'));

### Mixed integer geometric programming

The mixed-integer branch and bound solver in YALMIP is built in a modular fashion that makes it possible to solve almost arbitrary convex mixed integer programs. The following example is taken from [Boyd et al 2007]. To begin with, define the data for the example.

a     = ones(7,1);
alpha = ones(7,1);
beta  = ones(7,1);
gamma = ones(7,1);
f = [1 0.8 1 0.7 0.7 0.5 0.5]';
e = [1 2 1 1.5 1.5 1 2]';
Cout6 = 10;
Cout7 = 10;

Introduce symbolic expressions used in the model.

x = sdpvar(7,1);

C = alpha+beta.*x;
A = sum(a.*x);
P = sum(f.*e.*x);
R = gamma./x;

D1 = R(1)*(C(4));
D2 = R(2)*(C(4)+C(5));
D3 = R(3)*(C(5)+C(7));
D4 = R(4)*(C(6)+C(7));
D5 = R(5)*(C(7));
D6 = R(6)*Cout6;
D7 = R(7)*Cout7;

Define the objective function and constraints, and solve the problem.

% Constraints
F = [x >= 1, P <= 20, A <= 100];

% Objective
D = max([(D1+D4+D6),(D1+D4+D7),(D2+D4+D6),(D2+D4+D7),(D2+D5+D7),(D3+D5+D6),(D3+D7)]);

% Solve!
optimize([F, integer(x)],D)
value(D)
ans =
8.3333

An alternative model is discussed in the paper, and is just as easy to define.

T1 = D1;
T2 = D2;
T3 = D3;
T4 = max(T1,T2)+D4;
T5 = max(T2,T3) + D5;
T6 = T4 + D6;
T7 = max([T3 T4 T5]) + D7;
D = max(T6,T7);
optimize([F,integer(x)],D)
value(D)

### Known issues

Confusion can occur in the reformulation engine if you have convex quadratic constraints in your geometric program. To avoid this problem, use sdpsettings('convertconvexquad',0). To avoid some other known issues, it is advised to explicitly tell YALMIP that the problem is a geometric problem by specifying the solver to 'gpposy', 'mosek-geometric' or 'fmincon-geometric'`.

Never use the commands sqrt and cpower when working with geometric programs, i.e. always use the ^ operator. The reason is implementation issues in YALMIP. The commands sqrt and cpower are meant to be used in optimization problems where a conic second-order cone model is meant to be derived.


text:
# Confused with the definition of Random process

In wikipedia page, a random process is a collection of random variables defined on a common probability space $$(\Omega,\mathcal{F},P)$$ , all take values in the same mathematical space S measurable with respect to $$\sigma$$-algebra $$\Sigma$$.

So to my understanding, that means we have a set with element $$X:(\Omega,\mathcal{F},P)\rightarrow(S,\Sigma)$$. I am quite confident with this part of my understanding. However, I don't quite get what does it mean that the collection of the random variable is indexed by some set $$T$$, all take values in the same mathematical space $$S$$.

I always understand the indexation as a kind of 1-1 function $$I$$, in this example, we have $$I: T\rightarrow \mathcal{X}$$ where $$\mathcal{X}$$ is the collection of all $$X$$

Up to this point, if I were to write the mathematical expression of a stochastic process, I will write: $$\mathcal{X}=\{X_i:i\in T\}$$

However, I am very confused with the difference between a random vector and a stochastic process, in a random vector, we have a series of $$X_i,i\in1,2,...,n$$ and we will define $$X=(X_1,X_2,X_3,...,X_n)$$ as a random vector. I know they are definitely not the same thing but I cannot really tell what makes them different. In some textbook, they give notation for stochastic process $$X(\omega,t)$$ which seems to tell the difference. This means $$X$$ is not only a function of $$\omega$$ but also a function of $$t$$. However, I don't know how to incorporate this way of explanation into my pre-established understanding of a random variable, which as I have explained, is $$X:(\Omega,\mathcal{F},P)\rightarrow(S,\Sigma)$$.

Sorry if you find my question silly. I have very limited exposure to rigorous mathematics but I'd like to be introduced to all necessary concepts to understand this term. Thank you so much!

• Suppose, a Random Experiment(say tossing a coin) is repeated infinitely many times. And each time/ each trial we are interested in observing the outcome as head(1) and tail(0) . If this outcome is denoted by $X_i$ for the i-th trial then the sequence $X_1,X_2,\dots,$ will be a stochastic process. The beauty of the topic is such that if we now define $$Y_n=f(X_1,\dots,X_n)$$ then $Y_n$ will also form a sequence of random variables which should be Stochastic Process.
– FAM
Apr 28 '21 at 20:45
• You can definitely view a random vector in $\mathbb{R}^n$ as a stochastic process indexed by $\{1,2,\ldots, n\}$. Vice versa, a stochastic process indexed by $\mathbb{N}$ is an infinite dimensional random vector. Apr 28 '21 at 20:52
• And to add a remark. The index set doesn't need to be countable. In the generic setting of continuous-time stochastic processes your index set will rather be $[0,T]$ or $[0,\infty)$. Apr 28 '21 at 20:55
• random vectors and random processes are things completely different, the first is a vector-valued random variable and the second an indexed collection of random variables (vector-valued or whatever) Apr 28 '21 at 23:06

In the general case, the index set $$T$$ needs not be countable. For instance, a stochastic process $$X(\omega, t)$$ with $$t \in T = [0, 1]$$ could not be expressed as a random vector.
• realizations of $X(\omega,t)$ could be for example in $L^2([0,1])$ though? Apr 29 '21 at 11:37


text:
# Shuffling decks of cards where not all cards are distinguishable

Suppose a deck of cards consists of $a_1+a_2+\cdots+a_k$ cards of $k$ types, where there are $a_i$ indistinguishable cards of each type. How many shuffles does it take, on average, to randomize the deck? For example, $a_i=4$ and $k=13$ gives a standard deck of playing cards; $a_i=4$ for $1\le i\le9$, $i_{10}=16$, $k=10$ gives the cards for blackjack.

In general I would expect that this would be an easier task than shuffling a deck where all cards are indistinguishable. A standard deck has about 226 bits of entropy, while the same deck without suits has only 166 bits of entropy.

Consider a standard deck of 52 playing cards. Bayer & Diaconis (famously) showed that, under a certain model, it takes 7 riffle shuffles to sufficiently randomize the deck. Salem applies a different methodology and gets 6 idealized riffle shuffles. Mann uses a much stricter measurement and determines 11.7 as the expected stopping time for the riffle unshuffle (and thus the riffle shuffle) to randomize the deck.

In particular, Mann gives a formula: $$E(\mathbf{T})=\sum_{k=0}^\infty\left[1-{2^k\choose n}\frac{n!}{2^{nk}}\right]$$ which lends itself to generalization nicely.

I'm partial to Mann's method, but my question applies broadly.

[1] David Aldous and Persi Diaconis, "Shuffling cards and stopping times", The American Mathematical Monthly 93:5 (1986), pp. 333-348.

[2] Dave Bayer and Persi Diaconis, "Trailing the dovetail shuffle to its lair", The Annals of Applied Probability 2:2 (1992), pp. 294-313. JSTOR: 2959752

[3] Brad Mann, How many times should you shuffle a deck of cards?

[4] Michael P. Salem, How many shuﬄes are necessary to randomize a standard deck of cards?

-
The famous result about 7 riffle shuffles is actually due to Bayer and Diaconis here: jstor.org/stable/2959752 –  Mark Meckes Jun 2 '10 at 13:22
Also, depending on what you mean by "sufficiently", one might just as well say Bayer and Diaconis showed it takes 10 riffle shuffles. See Table 1 in the paper I linked to (assuming you have access to JSTOR). –  Mark Meckes Jun 2 '10 at 13:26
Thanks, Mark! I actually read their paper, but in my sleepy haze last night I misattributed it. Thanks for clearing that up, I'm sure that would have confused others. –  Charles Jun 2 '10 at 14:07
Strangely, I corrected the same misattribution on a well-known blog recently. –  Mark Meckes Jun 2 '10 at 15:20
My mistake was misreading reference 1 for reference 2 in Mann's paper; perhaps the blog author did the same thing? –  Charles Jun 2 '10 at 16:58


text:
## js-Unicode-Selector – A tool to have a closer look at Unicode Symbols

Yesterday, I had to prepare for an exam at the University but instead of learning for it I wrote a small tool to browse the unicode characters. You can have a look at it on http://pklaus.github.com/js-Unicode-Selector. It's fun...

## The Programming Language C

### Operators in C

Operators in C and C++: http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

C supports a rich set of operators, which are symbols used within an expression to specify the manipulations to be performed while evaluating that expression. C has operators for:

• arithmetic (+, -, *, /, %)
• equality testing (==, !=)
• order relations (<, <=, >, >=)
• boolean...

• Press [Ctrl]-[Shift]-[u]
• Press [Space] or [Enter] to confirm your input.


text:
# Tag Info

21

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.

20

In Shamir's scheme is a secret sharing scheme, that is, someone that has fewer shares than is required get no information about the secret. For example, if we have a system where we require 3 shares to reveal the shared secret, then someone with 2 shares cannot be able to reconstruct it. This is true if we make the shared secret the zero-th coefficient; ...

12

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process ...

8

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...

7

Actually, there are also other reasons why one wants to use safe primes in the RSA setting (when working with hidden order groups in cryptographic protocols). When choosing the RSA modulus $n=pq$ to be the product of safe primes $p=2p'+1$ and $q=2q'+1$, then we also have the following: The subgroup of $Z_n^*$ of qadratic residues is cyclic and has order $... 7 Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's$p-1$factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the$p+1$method, and strong primes also stop them. The ... 7 I am not quite sure why you are looking for the kind you have mentioned in your question. But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy. 7 Full disclosure: In 2007 I founded an association aiming at voting transparency. I'm proud that my efforts may have had some role, however small, in the fact that the number of French cities using electronic voting machines for political elections, then growing, has been declining since then. The book defining the protocol of the question is made freely ... 7 Another way to look at it informally is this; If it is perfectly hiding, then you cannot tell what made the final value. It could equally be any combination. If it is perfectly binding, then there is only one combination that produces the final value, essentially binding the final value to that one combination. Let's say we are talking about addition, and ... 7 Here's one more way in which a dishonest participant can mess with Shamir's secret sharing: Let's briefly review how secret reconstruction in Shamir's$(k,n)$secret sharing works. Given the$x$-coordinates of$k$participants$(x_1, x_2, \dots, x_k)\$, one way to reconstruct the secret is to compute the Lagrange basis polynomials: $$\ell_j(x) = \prod_{1 \... 7 This (k,n) scheme works, but isn't very interesting. Effectively, it is: For each set of k participants out of n, construct a (k,k) threshold scheme, and distribute those shares to the participants in the set. For example, in a (2, 3) scheme, if z is the secret, we'd generate \binom{3}{2} = 3 indepedent (2,2) threshold schemes (r_1, z-r_1 ... 7 Let's recall Shamir's Secret Sharing. We work in a finite field \mathbb{F}_q of cardinal q. The secret to share is s; we want n shares with a threshold t. We suppose that n < q (otherwise, the scheme does not work). We conventionally name n non-zero values of \mathbb{F}_q: x_1, x_2... x_n. Exactly how we choose them is unimportant, ... 6 I too had to go through this decision some time back and did a comparative study of both schemes. Shamir's scheme is used for the majority of works in the area of threshold secret sharing. This is because of the foremost reason of the number of primes required in both the schemes. Asmuth-Bloom's scheme require n+1 (n being the number of shares) prime ... 6 There is one theoretical difference between Shamir's scheme and Asmuth and Bloom's scheme. Shamir can be done in an informationally secure manner; specifically, if the nonconstant polynomial coefficients were chosen in a random manner (that is, from a uniform probability distribution that's uncorrelated to anything else the attacker can see), then someone ... 6 I believe there is strong enough precedence for using the term threshold decryption for the second. The abstract of this paper states: A threshold decryption scheme is a multi-party public key cryptosystem that allows any sufficiently large subset of participants to decrypt a ciphertext, but disallows the decryption otherwise. Sounds to me like what ... 6 Here's an easy way to do it: Take your secret S, and select a random value R of the same size, and compute T = S \oplus R Give the accountant the value R Use a (k-1, n-1) secret sharing method to share T to the other parties. The accountant plus any set of k-1 other parties can reconstruct the secret. And, any smaller subset cannot get any ... 6 It would appear that (for example) Shamir's original threshold secret sharing scheme would meet the requirements of 'post-quantum' (that is, remain secure even if that attacker has access to a Quantum computer). Let us assume that the shares were generated using a truly random stream; in that case, someone with N-1 shares (where N is the threshold) does ... 6 I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field? They have equivalent security; however the nice thing about GF(2^8) is that everything ends up to be an integral number of byte. We could use (say) GF(257), however when the shares will end up being slightly larger than 1 byte, and ... 5 A threshold, additively homomorphic cryptosystems (such as the threshold variant of paillier) would work just fine for this sort of system. Each voter would need to prove that their vote was in the set \{-1,0,1\} instead of the typical \{0,1\}. All of this could be done using the thep library. There is a page on dealing with negative numbers. An ... 5 Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from t+1 shares will yield the same result as reconstructing the secret from t+2 shares. Reconstructing it from t-1 will however (always) yield a completely different result. Reconstructing the secret from t-2 or fewer shares will ... 5 I don't believe that, in the example you gave, you can reconstruct the secret using two shares. d + \alpha m_0 is in the range [0, 2431); using the two shares 1 \bmod 11 and 3 \bmod 19, you can determine that it is one of 155, 364, 573, 782, 991, 1200, 1409, 1618, 1827, 2036, 2245, however you have no further information about which it might be. ... 5 Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)? The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent. As for the speed benefits being marginal, well, normally we use secret sharing as a part of ... 5 To be a little more formal, consider the notation provided by Iftach. Assume a commitment scheme (S,R) is statistically hiding. This means that a computationally unbounded R is unable to get any information about m from the commitment c. Since the process of computing a commitment is known to both parties, this means that there must exist (m,d)\... 5 In your example, let's assume the secret sharing scheme is a (k,n)-threshold sharing scheme with k = \frac{n + 1}{2}, as you say only an 'honest majority' can construct the secret. If then n protocol-following parties release their information to the group, an adversarial participant can then construct the whole secret, as they have a share, without ... 4 The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field being used. The "Dlog security" column in the linked page is the size of the finite extension field. Its security used to be comparable to the corresponding RSA ... 4 The way to prove this is to follow the same proof that Shamir's secret sharing is perfectly secret. Specifically, given any two points all secrets are possible since there is a polynomial going through every possible secret and the two given points. Since the polynomial is random, all of these polynomials have the same probability. The same thing is ... 3 Shamir's scheme is the most widely used scheme in such things as multi-party computation, threshold cryptography and oblivious transfer. Honestly I don't really know of any real everyday use of secret sharing based on CRT. As Artjom said Asmuth and Bloom's scheme takes some time to setup. The dealer must choose pairwise relatively prime integers m_0 < ... 3 Threshold (robust) m-of-n variant of Schnorr signature scheme is known: Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could ... 3 I assume you say on the threshold encryption scheme, in which a dealer generates (PK,SK_1,\dots,SK_n) and distributes the secret keys to users indexed by 1,\dots,n, and if a combiner obtains t partially-decrypted ciphertexts, it can retrieve a plaintext. Dodis and Katz showed a generic construction of CCA-secure threshold encryption scheme from a ... 3 Apart from the slightly unusual nomenclature, this is Shamir's secret-sharing scheme with n=6 and k=3 (i.e., the secret is shared into six pieces, any three of which can be combined to retrieve the secret). In this case, the pieces are as follows:$$\begin{align}(x_0, y_0) &= (10, 25) \\ (x_1, y_1) &= (20, 405) \\ (x_2, y_2) &= (30, 272) \\ ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
×

# Iterated Integral

Can anybody do the following integral?

$\int\limits_1^2\int\limits_{x^3}^{x}e^{y/x}dydx$

Note by Esraa Ibrahim
3 years, 2 months ago

Sort by:

You start by evaluating the inner integral

$$\int_1^2 \! \int_{x^3}^{x} \! e^{\frac{y}{x}} \, dy \, dx = \int_1^2 \! [xe^{\frac{y}{x}}]_{x^3}^{x} \, dx = \int_1^2 \! (ex-xe^{x^2}) \, dx$$

You then follow by evaluating the outer integral

$$\int_1^2 \! (ex-xe^{x^2}) \, dx = [ \frac{e}{2} x^2 - \frac{1}{2} e^{x^2} ]_1^2 = ( 2e - \frac{1}{2} e^{4} ) - ( \frac{1}{2} e - \frac{1}{2} e ) = \boxed{\frac{1}{2} e (4 - e^{3})}$$ · 3 years, 2 months ago

thanks alot ^^ · 3 years, 1 month ago

Aw... i know the answer but i dont know how to explain it in this website.... · 3 years, 2 months ago


text:
Elementary and Intermediate Algebra: Concepts & Applications (6th Edition)

$a^2b^2-c^2d^4$
Using $(a+b)(a-b)=a^2-b^2$ or the product of the sum and difference of like terms, the given expression, $(ab+cd^2)(ab-cd^2) ,$ simplifies to \begin{array}{l}\require{cancel} (ab)^2-(cd^2)^2 \\\\= a^2b^2-c^2d^4 .\end{array}